八皇后问题（回溯法）

目录

什么是八皇后

八皇后问题怎么解决？

什么是回溯法

回溯法的模板

八皇后问题的核心代码

判断皇后位置是否可行

总体实现代码

每日一句：

种一棵树的最好时间是十年前，其次是现在。

什么是八皇后

八皇后问题（英文：Eight queens），是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。

问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。

八皇后问题怎么解决？

八皇后的解决办法有很多种，我们这里采取回溯法解决。

什么是回溯法

回溯法的处理思想类似于枚举搜索，我们枚举出每一种情况，然后在根据条件进行筛选，找到满足期望的值。我们把求解过程分为多个阶段，每个阶段我们都会面临一个十字路口，我们随便找一条路，走不通后，就回到上一个十字路口，选择另一个十字路口进行下一步，知道遍历完整个枚举情况。

回溯法的模板

在面临较简单的回溯问题是可以使用以下模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

八皇后问题的核心代码

int []Queen=new int[8];//存取皇后所在列的位置
    public void eightQueen(int row){

        if (row==8){//当row等于8时说明八个皇后都放置好了
            printQueens(Queen);//打印八皇后
            return;
        }
        for (int column = 0; column < 8; column++) {
           if (isOk(row,column)){//这里判断是否可以放在这个位置
               Queen[row]=column;//放置皇后
               eightQueen(row+1);
           }
        }
    }

 那么有小伙伴就迷惑了，八皇后不应该是八行八列吗，为什么数组只是一个一维数组。这里就用到了回溯法的思想，把八行八列分成了八行，每一行都独立，而一维数组则只用来存取皇后的列坐标，行坐标由数组的下标代替。

判断皇后位置是否可行

public boolean isOk(int row,int column){
        int leftup=column-1,rightup=column+1;
        for (int i = row-1; i >=0 ; --i) {
            if (Queen[i]==column) return false;//看垂直方向是否有皇后
            if (leftup>=0){
                if (Queen[i]==leftup) return false;//看左上角斜线是否有皇后
            }
            if (rightup<8){
                if (Queen[i]==rightup) return false;//看右上角斜线是否有皇后
            }
            --leftup;
            ++rightup;
        }
        return true;
    }

判断位置可行的条件是，是否存在有皇后处在同一列，同一行（同一行的情况不存在，因为row一直加1），同一斜线。 

那么判断同一列我们只要看一维数组中是否有值与将要放置的皇后的列一致，如果一致我们为判断false;

那么如何判断是否在同一条斜线，

假设一个点A AA的坐标是[ a , b ] [a,b][a,b]，那么和该点在同一斜线上的点A 有四种,分别是
[ a + x , b + x ] 、 [ a − x , b − x ] 、 [ a + x , b − x ] 、 [ a − x , b + x ] 

而我们只考虑左右上角的位置是否存在同一条斜线,那么为什么不考虑下角是否存在呢，因为我们的皇后还没排到左右下角，所以只考虑 [ a − x , b + x ] 和[ a − x , b − x ]这两种情况。

我们通过让x等于1时来达到，当处于同一斜线时，斜线分为四十五度，则行和列相等时，在同一斜线上，判断为false.

八皇后总体实现代码

public static void main(String[] args) {
        Solution1 solution=new Solution1();
        solution.eightQueen(0);
    }
    int []Queen=new int[8];
    int count=0;
    public void eightQueen(int row){

        if (row==8){
            count++;
            printQueens(Queen);
            return;
        }
        for (int column = 0; column < 8; column++) {
           if (isOk(row,column)){

               Queen[row]=column;
               eightQueen(row+1);
           }
        }
    }
    public boolean isOk(int row,int column){
        int leftup=column-1,rightup=column+1;
        for (int i = row-1; i >=0 ; --i) {
            if (Queen[i]==column) return false;//看垂直方向是否有皇后
            if (leftup>=0){
                if (Queen[i]==leftup) return false;//看左上角斜线是否有皇后
            }
            if (rightup<8){
                if (Queen[i]==rightup) return false;//看右上角斜线是否有皇后
            }
            --leftup;
            ++rightup;
        }
        return true;
    }
    private void printQueens(int []Queen){
        for (int row = 0; row < 8; row++) {
            for (int column = 0; column < 8; column++) {
                if (Queen[row]==column) System.out.print("   Q   ");
                else System.out.print("   *   ");
            }
            System.out.println();
        }
        System.out.print(count);
        System.out.println();
    }
}

每日一句：

种一棵树的最好时间是十年前，其次是现在。