这是是一个古老而著名的问题，是回溯算法的典型案例。

简介

八皇后问题是一个以国际象棋为背景的问题：
如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后。
为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。

解答

思路是按行来规定皇后，第一行放第一个皇后，第二行放第二个。
通过遍历所有列，来判断下一个皇后能否放在该列。
直到所有皇后都放完，或者放哪都不行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
public class Queen {
	/* 同栏是否有皇后，1表示有 */
	private int[] column;
	/* 右上至左下是否有皇后 */
	private int[] rup;
	/* 左上至右下是否有皇后 */
	private int[] lup;
	/* 解答 */
	private int[] queen;
	/* 解答编号 */
	private int num;

	public Queen() {
		column = new int[8 + 1];
		rup = new int[(2 * 8) + 1];
		lup = new int[(2 * 8) + 1];
		for (int i = 1; i <= 8; i++)
			column[i] = 0;
		for (int i = 1; i <= (2 * 8); i++)
			rup[i] = lup[i] = 0; /* 初始定义全部无皇后 */

		queen = new int[8 + 1];
	}

	public void backtrack(int i) {
		if (i > 8) {
			showAnswer();
		} else {
			for (int j = 1; j <= 8; j++) {
				if ((column[j] == 0) && (rup[i + j] == 0)
						&& (lup[i - j + 8] == 0)) {
					/* 若无皇后 */
					queen[i] = j;
					/* 设定为占用 */
					column[j] = rup[i + j] = lup[i - j + 8] = 1;
					backtrack(i + 1); /* 递归 */
					column[j] = rup[i + j] = lup[i - j + 8] = 0;
				}
			}
		}
	}

	protected void showAnswer() {
		num++;
		System.out.println("\n解答" + num);
		for (int y = 1; y <= 8; y++) {
			for (int x = 1; x <= 8; x++) {
				if (queen[y] == x) {
					System.out.print("Q");
				} else {
					System.out.print("-");
				}
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		Queen queen = new Queen();
		queen.backtrack(1);
	}
}

拓展

八皇后问题可以拓展为N皇后问题。
这时棋盘的大小变为 n1 × n1，而皇后个数也变成 n2。
显然仅当 n1 ≥ 4 或者 n2 ≥ 1 时问题有解。

其实本质和八皇后一样，但是需要先判断是否有解。

END…