1 问题概述
在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。计算机发明后，有多种计算机语言可以编程解决此问题。
2 代码实现
/*** @author huwenlong* @date 2019/12/15 23:12* 第一个皇后放在第一行第一列* 第二个皇后放在第二行第一列,判断是否OK,不OK,则放在第二行第二列、第三列……* ……* 第n个皇后放在第n行第一列,判断是否OK,不OK,则放在第n行第二列、第三列……* 直到第八个皇后放到适当位置得到一个解* 得到一个正解时回退到上一个栈,就会开始回溯,即将第一个皇后放在第一行第一列的所有正解回溯出来* 然后将第一个皇后放在第一行第二列、第三列……*/
public class EightQueen {/*** 数组下标代表行,数组下标对应的值代表列*/private int[] queens;private int queenNum = 8;private int num;private int judgeNum;@Beforepublic void init() {queens = new int[queenNum];}/*** 在第n行放置皇后** @param n*/private void setQueen(int n) {if (n == queenNum) {num++;System.out.println(Arrays.toString(queens));return;}// 在0-queenNum列依次放入皇后,并判断是否冲突for (int i = 0; i < queenNum; i++) {queens[n] = i;if (judge(n)) {// 如果不冲突则放置下一行的皇后setQueen(n + 1);}}}/*** 放置第n个皇后的时候判断是否和前面的皇后冲突** @param n* @return*/private boolean judge(int n) {judgeNum++;for (int i = 0; i < n; i++) {// queens[i] == queens[n] 表示判断第n个皇后和前面n-1个皇后在同一列// Math.abs(n - i) == Math.abs(queens[n] - queens[i])判断是否在同一斜线if (queens[i] == queens[n] || Math.abs(n - i) == Math.abs(queens[n] - queens[i])) {return Boolean.FALSE;}}return Boolean.TRUE;}@Testpublic void test() {long startTime = System.currentTimeMillis();setQueen(0);System.out.println(num + " " + judgeNum + " " + (System.currentTimeMillis() - startTime));}
}
输出：92 15720 16
共有92种解法，15720次判断