专业建站/国家提供的免费网课平台

算法描述

摘自百度：

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

解题思路

采用递归+回溯的方式进行求解。

给出一个二维数组，遍历所有行，在每一行中找到一个合适的值，如果满足条件就把该位置设置成1，并继续遍历下一行，如果能持续的遍历到最后一行并且找到满足条件的点，则成功找到一组解。
找到一组解之后，再进行回溯，因为一行中可能有多个点满足条件，所以要把一行中所有的点都进行判断，最终找到所有满足条件的解。

代码实现

int queueCount = 0;void queue(int[][] array, int row) {if (row >= array.length) {print(array);queueCount ++;return;}for (int i=0; i<array[row].length; i++) {if (!check(array, row, i)) { // 检查是否满足条件continue;}array[row][i] = 1;queue(array, row + 1); // 遍历下一行的每一列array[row][i] = 0; // 回溯}
}boolean check(int[][] array, int row, int column) {for (int i=0; i<array.length; i++) {// 检查是否在同一列if (array[i][column] == 1) {return false;}// 检查主对角线int a1 = row - i;int a2 = column - i;if (a1 >= 0 && a2 >= 0) {if (array[a1][a2] == 1) {return false;}}// 检查副对角线a1 = row - i;a2 = column + i;if (a1 >= 0 && a2 < array[a1].length) {if (array[a1][a2] == 1) {return false;}}}return true;
}

最终结果

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,
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, 0, 1, 0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 1, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 0, 0,
0, 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, 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, 0, 1, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 1, 0,
0, 0, 0, 0, 1, 0, 0, 0,

queue count 92

TIPS

最开始考虑通过其他方式保存上一次递归的结果，但是后来想到其实每一次递归总会得出一个结果，如果不满足则不用输出，如果满足则可以在递归的最深一层输出。
而且递归各个分支的结果相互不影响，所以可以采用回溯的方式在一个分支完成后重置结果，避免针对每一个分支都单独保存一份中间执行结果。