回溯算法解决八皇后问题思路详解（java实现）

回溯算法框架

回溯算法所做的事情就是进行穷举。 解决一个回溯问题，实际上就是一个决策树的遍历过程。 只需要考虑以下三个问题： 1、路径：也就是已经做出的选择。 2、选择列表：也就是你当前可以做的选择。 3、结束条件：也就是到达决策树底层，无法再做选择的条件。

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择       //树的前序遍历位置
        backtrack(路径, 选择列表)   
        撤销选择    //树的后序遍历位置

这个框架的核心部分就是for循环里的递归，在递归调用之前做选择，调用之后撤销选择。也就是在树的前序遍历位置和后序遍历位置做一些操作

决策树

[2] 就是「路径」，记录你已经做过的选择；[1,3] 就是「选择列表」，表示你当前可以做出的选择；「结束条件」就是遍历到树的底层，在这里就是选择列表为空的时候。

参考自：

基本思路分析

1.第一个皇后先放在第一行第一列 2.第二个皇后放在第二行第一列，然后判断是否满足条件，如果不满足，则继续放在第二列、第三列，直到找到一个合适的位置 3.继续放第三个皇后，还是从第一列开始，逐个寻找合适的位置 4.当得到一个正确解时，在栈（递归，所以会使用到栈）回退到上一个栈时，就会开始回溯，即回溯到第七个皇后位置，再次寻找满足条件的第八个皇后的新位置，一直回溯，直到将第一个皇后，放到第一列的所有正确解全部得到。 5.然后回头继续第一个皇后放到第二列，继续循环执行1,2，3,4的步骤。

小知识点

1.不需要创建二维数组，使用一个一维数组即可解决问题。array[8] = {0,4，7,5，2,6，1,3}，使用数组下标表示棋盘的行数，下表对应的值表示列数。 2.只需判断皇后是否在同一列或者是同一条对角线上即可。当数组值相等时即在同一列上，array[i] == array[n];当两个皇后之间的行的差的绝对值等于列的差的绝对值时在同一条对角线上，Math.abs(n-i)==Math.abs(array[n]-array[i])。

实现代码

public class NQueues {
    int max = 8;
    int[] array = new int[max];  //数组下标表示行数，数组值表示列数

    static int judgeCount = 0;
    static int count = 0;

    public static void main(String[] args) {
        NQueues queues = new NQueues();  //创建八皇后对象
        queues.check(0);  //从第1个皇后开始
        System.out.println("判断次数为："+judgeCount);
        System.out.println("有效解法为："+count);
    }

    private void check(int n){  //n代表第几个皇后
        if(n==max){  //满足条件时，直接打印结束
            print();
            return;
        }

        for (int i = 0; i < max; i++) {   //i代表列数，每行都有8个选择
            array[n] = i;  //把值赋给array[i]，可以进行判断该点是否有效
            if(!isValid(n)){   //如果不满足条件，则继续寻找下一列
                continue;
            }
            check(n+1);  //进入下一个决策，则第（n+1）个皇后的位置
        }
    }

    private boolean isValid(int n){    //判断该点是否满足条件
        judgeCount++;  //记录判断次数
        for (int i = 0; i < n; i++) {
            /*
                1.判断两个皇后是否在同一列,array[i]表示第i个皇后所在的列数
                2.判断是否在同一条对角线上
                3.每次都会自动进入下一行，不用判断是否在同一行
             */
            if(array[i]==array[n] || Math.abs(n-i)==Math.abs(array[n]-array[i]))
                return false;
        }
        return true;
    }

    private void print(){
        count++;      //解法个数
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+"");
        }
        System.out.println();
    }

}