经典n皇后问题java代码实现

问题描述：在n*n的二维表格，把n个皇后在表格上，要求同一行、同一列或同一斜线上不能有2个以上的皇后。

例如八皇后有92种解决方案，五皇后有10种解决方案。

public class TestQueen {

	int n; //皇后的个数
	int num = 0; // 记录方案数
	int[] queenCol; // 记录n个皇后所占用的列号
	boolean[] col; // 列安全标志
	boolean[] diagonal; // 对角线安全标志
	boolean[] undiagonal; // 反对角线安全标志

	public TestQueen(int n) {
		this.n = n;
		queenCol = new int[n];
		col = new boolean[n];
		diagonal = new boolean[2 * n - 1];
		undiagonal = new boolean[2 * n - 1];
		for (int i = 0; i < n; i++)
			// 置所有列为安全
			col[i] = true;
		for (int t = 0; t < (2 * n - 1); t++)
			// 置所有对角线为安全
			diagonal[t] = undiagonal[t] = true;
	}

	public void run() {
		solve(0);
		if (num == 0) {
			System.out.println(n + "皇后无解！");
		}
	}

	// 从i行开始，把之后的皇后放好
	private void solve(int i) {
		for (int j = 0; j < n; j++) {
			if (col[j] && diagonal[i - j + n - 1] && undiagonal[i + j]) {
				// 表示第i行第j列是安全的可以放皇后(i,j从0开始)
				queenCol[i] = j;
				col[j] = false; // 修改安全标志
				diagonal[i - j + n - 1] = false;
				undiagonal[i + j] = false;
				if (i < n - 1) // 判断是否放完n个皇后
				{
					solve(i + 1); // 未放完n个皇后则继续放后面的
				} else // 已经放完n个皇后
				{
					num++;
					System.out.println("皇后摆放第" + num + "种方案:");
					System.out.print("行分别为");
					for (int k = 0; k < n; k++)
						System.out.print(k + " ");
					System.out.print("\n");
					System.out.print("列分别为");
					for (int k = 0; k < n; k++)
						System.out.print(queenCol[k] + " ");
					System.out.print("\n");
				}
				col[j] = true; // 修改安全标志，回溯
				diagonal[i - j + n - 1] = true;
				undiagonal[i + j] = true;
			}
		}
	}

	public static void main(String[] args) {
		TestQueen q = new TestQueen(5);
		q.run();
	}
} 

输出结果：

皇后摆放第1种方案:
行分别为0 1 2 3 4
列分别为0 2 4 1 3
皇后摆放第2种方案:
行分别为0 1 2 3 4
列分别为0 3 1 4 2
皇后摆放第3种方案:
行分别为0 1 2 3 4
列分别为1 3 0 2 4
皇后摆放第4种方案:
行分别为0 1 2 3 4
列分别为1 4 2 0 3
皇后摆放第5种方案:
行分别为0 1 2 3 4
列分别为2 0 3 1 4
皇后摆放第6种方案:
行分别为0 1 2 3 4
列分别为2 4 1 3 0
皇后摆放第7种方案:
行分别为0 1 2 3 4
列分别为3 0 2 4 1
皇后摆放第8种方案:
行分别为0 1 2 3 4
列分别为3 1 4 2 0
皇后摆放第9种方案:
行分别为0 1 2 3 4
列分别为4 1 3 0 2
皇后摆放第10种方案:
行分别为0 1 2 3 4
列分别为4 2 0 3 1