经典算法回顾 (Java版)—— 八皇后问题

时间:2022-12-18 11:10:21

前几天关注的CSDN公众号推送了一篇文章是讲八皇后问题的,作为经典DFS算法,当时看到文章的时候就点开回顾了一下。

我这里贴 链接 算是在帮公众号做推广吗...好吧不废话了。我觉得文章里画的图解真的很详细易懂,本来想截图,然后一张张地用Java语言再解释一遍,但是担心涉及到知识产权和版权问题,出于尊重的原因。还是只贴链接吧。建议大家可以先看一下链接里的思路解释,对于理解下面的代码实现就会容易很多了。

我们先以8*8的棋盘为例,进行八皇后问题的实现:

一、如果只对总方案数进行计算:

public class Main {
	static int[] queens = new int[8]; // 记录每一行的皇后位置
	static int count = 0;// 记录方案总数

	static void dfs(int row) {
		if (row == 8) { 
			count++;
			return;
		}
		for (int column = 0; column < 8; column++) {
			queens[row] = column; // 在该行的第column列上放置皇后
			if (conflict(row) == false) 
				dfs(row + 1); 
		}
	}

	static boolean conflict(int row) {
		for (int x = 0; x < row; x++) { // 第row行上的皇后与前面row-1个皇后比较
			if (queens[x] == queens[row]) // 两个皇后在同一行上
				return true;
			if (Math.abs(queens[x] - queens[row]) == (row - x)) // 两个皇后在同一对角线上
				return true;
		}
		return false;
	}

	public static void main(String[] args) {
		dfs(0);
		System.out.println(count);
	}
}


输出:92


二、如果需要打印出各个方案:

public class Main {
	static int[] queens = new int[8]; 
	static int count = 0;

	static void dfs(int row) {
		if (row == 8) { 
			count++;
			System.out.println("方案" + count + ":"); //打印方案
			print();
			return;
		}
		for (int column = 0; column < 8; column++) {
			queens[row] = column; 
			if (conflict(row) == false) 
				dfs(row + 1); 
		}
	}

	static boolean conflict(int row) {
		for (int x = 0; x < row; x++) { 
			if (queens[x] == queens[row]) 
				return true;
			if (Math.abs(queens[x] - queens[row]) == (row - x)) 
				return true;
		}
		return false;
	}


	static void print() { //打印方案的函数
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				if (queens[i] == j)
					System.out.print("1 "); //表示皇后位置
				else
					System.out.print("0 ");
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		dfs(0);
		System.out.println(count);
	}
}



输出:
方案1:
1 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 1 
0 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 1 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 
方案2:
1 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 1 
0 0 1 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 1 0 0 0 0 
0 1 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
方案3:
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
0 0 1 0 0 0 0 0 
......
以下省略


那么如果推广到n*n的棋盘呢?

情况大同小异。为了能够解释清楚,我这里用一道题目来具体化。

经典算法回顾 (Java版)—— 八皇后问题

经典算法回顾 (Java版)—— 八皇后问题

其实n*n的棋盘,并不需要改动任何核心的DFS算法,只需要按照题意改动一下输出方式即可,本题只要求输出前三个解。

下面附代码:

import java.util.Scanner;

public class Main {
	static int[] queens; 
	static int count = 0;
	static int n;

	static void dfs(int row) {
		if (row == n) { 
			count++;
			if (count <= 3) { //按照题意输出
				for (int i = 0; i <= n - 2; i++) {
					System.out.print((queens[i] + 1) + " "); //注意+1

				}
				System.out.println(queens[n - 1] + 1);
			}
			return;
		}
		for (int column = 0; column < n; column++) {
			queens[row] = column; 
			if (conflict(row) == false) {
				dfs(row + 1); 
			}
			queens[row] = 0;
		}
	}

	static boolean conflict(int row) {
		for (int x = 0; x < row; x++) { 
			if (queens[x] == queens[row]) 
				return true;
			if (Math.abs(queens[x] - queens[row]) == (row - x)) 
				return true;
		}
		return false;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		queens = new int[n];
		dfs(0);
		System.out.println(count);
	}
}

输入:6
输出:
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4