8皇后问题解答---海康威视研究院大数据技术部大数据算法工程师一面手撕

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

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

以下是我的解法，程序最终运行结果告诉我们，一共有92种答案。
​
public class Queue8 {
    int max =  8; // 定义一个max 表示共有多少个皇后
    int[] array =  new int[max]; // 定义数组array 保存皇后放置的结果，比如arr={0 4 7 5 2 6 1 3}
    static int count = 0;
​
    public static void main(String[] args ){
        Queue8 queue8 =  new Queue8();
        queue8.check(0);
        System.out.println("一共有" +count +"种解法 。");
​
    }
​
    private void check(int n ){
        if(n==max){
            print();
            return;
        }
        for(int i=0;i<max;i++ ){
            array[n] = i;
            if(judge(n)){
                check(n+1);
            }
        }
    }
​
    private boolean judge(int n ){
        for(int i=0;i<n;i++){
            if(array[i] == array[n] || Math.abs( array[i]-array[n] ) ==  Math.abs(i-n) ){
                return false;
            }
        }
        return true;
    }
​
    
    // 写一个方法，可以将皇后摆放的位置输出
    private void print(){
        count ++ ;
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]+"  ");
        }
        System.out.println();
    }
}

​