51. N 皇后
皇后的摆放规则
- 行(横)方向不能有两个
- 列(竖)方向不能有两个
- 对角线不能有两个
代码
import java.util.Arrays;
public class eightQueen {
static int nQueen = 8; //n皇后
static int count = 0; //记录有多少种摆法
public static void main(String[] args) {
System.out.println("hello world");
int[] result = new int[nQueen]; //存放结果
place(0,result);
System.out.println("总共有 ： " + count + "种摆法");
}
/* 放置8皇后， 存入当前放置的对应的行， */
public static void place(int row, int[] result) {
if (row >= nQueen) {
//当row是第8个行， 能放第8行， 排完了。 完成
System.out.println(Arrays.toString(result));
System.out.println("------------------------------");
count++;
return;
}
// 遍历当前row的所有col元素是否满足
for (int col = 0; col<nQueen; col++) {
//如果可以，就再判断下一轮， 这个时候，row + 1， 然后又从col = 0 开始遍历
if (isOK(row, col, result)) {
result[row] = col;
place(row + 1, result);//递归到下一行
}
}
}
// 规则 :
// 1.当前格子的对应的行上，都没有，因为每次放都是新的一行， 所以这个情况不用判断。
// 2.当前格子的对应的列上，都没有。
// 3.当前格子的对应的对角线上， 都没有。
public static boolean isOK(int row , int col, int[] result) {
//值得注意的是：
// result存放的结果是 result[0]对应的是第1行的col值
// result存放的结果是 result[1]对应的是第2行的col值
// ....
// 所以，这里对比存放的结果的时候， 查看的是for (int i = 0; i< row; i++)的条件。
// 对于result后面的值就不需要关心了，因为row+1行的值不关心，只关心前面已经存过的值
if (row == 0 && col == 0 ) return true;
for (int i = 0; i< row; i++) {
//列方向不能有相同的两个
if (result[i] == col ) return false;
//对角线方向不能有相同的两个
if (Math.abs(result[i] - col) == Math.abs(row - i) ) return false;
}
return true;
}
}
递归 + 回溯 分析
// 遍历当前row的所有col元素是否满足
for (int col = 0; col<nQueen; col++) {
//如果可以，就再判断下一轮， 这个时候，row + 1， 然后又从col = 0 开始遍历
if (isOK(row, col, result)) {
result[row] = col;
place(row + 1, result);//递归到下一行
}
}
-
因为是从第0行开始的， place(0,result); 会针对第0行的所有的col做情况筛选， 也就是遍历每一列。第0行总会有满足的条件， 所以就会递归到下一行。
-
如果接下来的某一行的col都不满足， 也就是当前这一行的情况不满足， 就会回到往上一级回溯， 也就是回到row-1行， 直到第0行。
-
只要第0行有满足的条件， 就会再次递归到下一行
执行结果 ：
4皇后结果
[1, 3, 0, 2]
------------------------------
[2, 0, 3, 1]
------------------------------
总共有 ： 2种摆法
4皇后结果
PS ：
[1, 3, 0, 2] 值是代码中的数组的索引的值， 从0开始计算。
4皇后4列对应的是0，1，2，3.
8皇后结果
[0, 4, 7, 5, 2, 6, 1, 3]
------------------------------
[0, 5, 7, 2, 6, 3, 1, 4]
------------------------------
[0, 6, 3, 5, 7, 1, 4, 2]
------------------------------
[0, 6, 4, 7, 1, 3, 5, 2]
------------------------------
....（.中间太多了，可以自己打印试试）
------------------------------
[7, 2, 0, 5, 1, 4, 6, 3]
------------------------------
[7, 3, 0, 2, 5, 1, 6, 4]
------------------------------
总共有 ： 92种摆法
也可以对比执行其他皇后情况 ： 5皇后， 6皇后.....
更多优化 ：
public static boolean isOK(int row , int col, int[] result) {
if (row == 0 && col == 0 ) return true;
for (int i = 0; i< row; i++) {
//列方向不能有相同的两个
if (result[i] == col ) return false;
//对角线方向不能有相同的两个
if (Math.abs(result[i] - col) == Math.abs(row - i) ) return false;
}
return true;
}
这里每次都要做一次for循环的比较， 可以优化到O(1)级别。
回头看规则 ：
- 行(横)方向不能有两个
- 列(竖)方向不能有两个
- 对角线不能有两个
定义三个数组，
- 一个保存行(横)方向的结果集，数组大小为n
- 一个保存 列(竖)方向的结果集，数组大小为n
- 一个保存对角线方向的结果集，数组大小为2n-1
关于对角线数组
对角线
对角线
对角线公式参考 ：八皇后||算法
每次递归+回溯的时候， 满足条件递归就赋值， 不满足条件回溯的时候就重置原来的值。
下一次做isOK比价的时候就直接取对应的值来做比较。可以优化到O(1)级别。
网友评论