八皇后问题

八皇后

1. 第一个皇后先放第一行第一列
2. 第二个皇后放在第二行第一列、然后判断是否OK， 如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适
3. 继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解
4. 当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到.
5. 然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4的步骤

存储棋盘的数组为一维数组，例如arr[7 1 3 0 6 4 2 5 ]表示第一行第八列，第二行第2列，第三行第四列.......

import javax.sound.midi.Soundbank;

public class EightQueens {
    public static int MAX=8;
    public static int[] arr=new int[MAX];
    public static void main(String[] args) {

        System.out.println();
        recursion(0);

    }



    public static  void recursion(int n){
        //递归退出条件 达到棋盘最大值时
        if (n==MAX){
            for (int i : arr) {
                System.out.print(i+" ");
            }
            System.out.println();
            return ;
        }
        //对第n行的第i列进行判断 符合条件进行存储，不符合回朔
        for (int i = 0; i < MAX; i++) {
            arr[n]=i;
            if (judgment(n)){
                recursion(n+1);
            }
        }

    }

    /**
     * 判断是否符合条件
     * @param n
     * @return
     */
    public static boolean judgment(int n){
       for (int i=0;i<n;i++){
           //判断是否属于同一列或同一斜线
           if (arr[n]==arr[i]||Math.abs(n-i)==Math.abs(arr[n]-arr[i])){
               return false;
           }
       }
       return true;
    }

}

八皇后问题

原文：https://www.cnblogs.com/huangshen/p/13268975.html