八皇后是递归算法中很经典的案例 下面分享一下八皇后具体实现方法

算法思路

1. 第一个皇后先放在第一行第一列
2. 第二个皇后放在第二行第一列，然后判断是否ok，如果不OK 就放在第二列、第三列…依次把所有列放完 找到一个合适
3. 继续第三个皇后，还是先放第一列、第二列 依次类推 直到第八个皇后也放在了一个不冲突的地方，就算是找到了一个正确解
4. 当得到一个正确解的时候 在栈回退到上一个栈时，就会开始回溯，即将第一个皇后放在第一列的所有正确解 全部得到
5. 然后回头继续第一个皇后放第二列 后面继续循环执行1.2.3.4的步骤
   说明：理论上应该创建一个二维数组来表示棋盘 但是实际上可以通过算法用一个一维数组即可解决问题，arr[8]={0,4,7,5,2,6,1,3}对应arr小标 表示第几行 即第几个皇后，arr[i]=val,val表示第i+1个皇后，放在第i+1行的第val+1列

下面是代码实现

首先写一个判断是否冲突的方法

//判断我们的放置第n个皇后，就去检查皇后是否和前面的已经摆放后皇后冲突
    private boolean judge(int n)
    {
        for (int i = 0; i <n ; i++) {
            /*因为是一维数组所以直接排除了同一行的可能情况
            array[i]==array[n]判断是否在同一列：array[i]=val的值代表列
            Math.abs(n-i)==Math.abs(array[n]-array[i])
            可以看成是n-i行差等于array[n]-array[i]列差即斜率为1
            斜率为1即为同一斜线
            */
            if (array[i]==array[n]||Math.abs(n-i)==Math.abs(array[n]-array[i])){
                return false;
            }
        }
        return  true;
    }

然后写一个递归放置的方法

    public void check(int n){
         if(n==max)//当n=8时说明已经将八个皇后放好了
         {
             print();
             return;
         }
        for (int i = 0; i < max; i++) {
            //先把当前的这个皇后n,放到该行的第一列
            array[n]=i;
            //判断当放置第n个皇后到i列时，是否冲突
            if (judge(n)){//不冲突
                //接着放n+1个皇后，即开始递归
                check(n+1);
            }
            //如果冲突就会继续执行array[n]=i,即将第n个皇后放在本行的后一个位置
        }
    }
    //打印数组的print方法
       public void print(){
        count++;
        System.out.printf("第%d种解法",count);
        for (int item:array){

            System.out.printf(" "+item);
        }
        System.out.println();
    }

最后调用测试一下

public class Queen8 {
    int max = 8;
    int count=0;
    int []array=new int[max];
    public static void main(String[] args) {
        Queen8 queen8=new Queen8();
        queen8.check(0);

    }

结果如下