八皇后问题 DFS Java版

八皇后问题 DFS Java版

看了不同的博客，有用一维数组来解决的，也有用二维数组来解决的，思路基本上都是一致的。

八皇后问题—Java—递归回溯_南疆晚歌的博客-CSDN博客【图解回溯算法】如何用回溯算法来解决8皇后问题？_hixiaoxiaoniao的专栏-CSDN博客_八皇后问题，可以检验你代码结果对不对，多测试几个即可（我测试了几个都没问题）

N皇后问题解法及解的个数_张小帅的专栏-CSDN博客_n皇后问题有多少解【图解回溯算法】里有动图，很直观地反映了八皇后问题的解决过程。一维数组，index表示当前行，arr[index]表示第index行的皇后存放在arr[index]列。在if语句check的时候，不存在修改原来arr的值，因为直接下一次for循环会直接覆盖。但是对于二位数组来说，没有记录具体的列，只是这一项被赋值为1，所以在DFS回溯的时候要把当前“地图上”这一项换成0。

在check函数的编写上，一维数组和二维数组也不同。

不管是哪一个check函数，都是为了检查在当前行这个位置摆放皇后是否合适，下面的行都还没有进行摆放，所以不用管，只需检查上面的行的摆放情况就好。

check函数需要检查两个：

①同一列上，是否已经摆放过皇后

②斜对角线上是否已经摆放过皇后，斜对角线包括两个方向，一个是平行于y=x的斜对角线，一个是平行于y=-x的斜对角线

现在按照上面的两种情况，现在来解释一下两个check函数

①一维数组的check函数，一维数组，index记录行数，arr[index]记录列数

第一个括号内的就是检查是否在同一列上，第二个括号内就是检查两个斜对角线的情况，因为使用了abs函数，所以正斜对角线和负斜对角线都可以囊括在内

(arr[i] == arr[n]) || (Math.abs(n - i) == Math.abs(arr[n] - arr[i])

②二维数组的check函数，二维数组表示布局，即元素为1的位置表示皇后的摆放位置

check函数中的第一个for循环，是检查同一列上是否已经摆放过皇后，第二个while循环是检查与y=x平行的那条对角线是否摆放过皇后，第三个while循环是检查y=-x平行的那条对角线是否摆放过皇后，后面两个while循环在编写的时候要注意循环条件！

代码中的maxn代表n皇后问题的n。

一维数组代码

public class Main {int[] arr;int cnt;int maxn;
//    int flag = 0;public static void main(String[] args) {new Main().solve();}private void solve() {//用一维数组记录八皇后的摆放问题，数组的index表示第几行，数组的value表示当前行的皇后摆在第几列maxn = 9;arr = new int[maxn];cnt = 0;dfs(0);System.out.println(cnt);}private void dfs(int n) {if (n == maxn) {//表示8个皇后已经全部放置完毕cnt++;
//            if (flag == 0) {
//                for (int i = 0; i < maxn; i++) {
//                    for (int j = 0; j < maxn; j++) {
//                        //arr[i]表示第i行摆在哪一列
//                        if (arr[i] != j) {
//                            System.out.print("0");
//                        } else {
//                            System.out.print("1");
//                        }
//                    }
//                    System.out.println();
//                }
//                flag = 1;
//            }return;}//每一列去摆放皇后for (int i = 0; i < maxn; i++) {//先放置，再判断//就我个人理解，这里必须把赋值操作放在外面，是因为这里使用一维数组来记录，没有过多的信息来判断//判断的是，在第n行的这个位置是否合适//如果想要把赋值语句拿到if里面，那么必须向check函数再传递一个参数，即你假设把当前这个皇后放在哪arr[n] = i;if (check(n)) {dfs(n + 1);}//            arr[n] = i;
//            if (check(n, i)) {
//                dfs(n + 1);
//            }}}private boolean check(int n) {for (int i = 0; i < n; i++) {if ((arr[i] == arr[n]) || (Math.abs(n - i) == Math.abs(arr[n] - arr[i]))) {return false;}}return true;}private boolean check(int n, int index) {for (int i = 0; i < n; i++) {if ((arr[i] == index) || (Math.abs(n - i) == Math.abs(index - arr[i]))) {return false;}}return true;}
}

二位数组代码

public class Main {int maxn = 2;int[][] arr = new int[maxn][maxn];int cnt;public static void main(String[] args) {new Main().solve();}private void solve() {cnt = 0;dfs(0);System.out.println(cnt);}private void dfs(int n) {if (n == maxn) {cnt++;return;}for (int i = 0; i < maxn; i++) {
//            arr[n][i] = 1;
//            if (check(n, i)) {
//                dfs(n + 1);
//            }
//            arr[n][i] = 0;if (check(n, i)) {arr[n][i] = 1;dfs(n + 1);arr[n][i] = 0;}//这两种方式思路其实是一样的。//就下面这种来说，首先判断这个点的位置是否满足，如果满足的话，把这个位置设置为1，继续去下一行找合适的位置//下一行如果没有位置是满足的，回退到这一行，这个位置重新设置成0，再往后找合适的位置}}private boolean check(int n, int m) {//当前这个点在第n行，第m列//第0行到该行for (int i = 0; i < n; i++) {//同一列上有if (arr[i][m] == 1) {return false;}}int n1 = n - 1;int m1 = m - 1;while (n1 >= 0 && m1 >= 0) {if (arr[n1][m1] == 1) {return false;}n1--;m1--;}n1 = n - 1;m1 = m + 1;while (n1 >= 0 && m1 < maxn) {if (arr[n1][m1] == 1) {return false;}n1--;m1++;}return true;}}