八皇后问题

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

问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

public class Queue8 {
    int max=8;
    int[] arr=new int[max];
    static int count=0;

    public static void main(String[] args) {
        Queue8 q8=new Queue8();
        q8.put(0);
        System.out.println(count);
    }

   //放棋子
    private void put (int n){
        if(n==max)
        {
            count++;
            print();
            return;
        }
        for(int i=0;i<max;i++){
            arr[n]=i;
            if(judge(n))
                put(n+1);
        }
    }

    //判断所放棋子是否有效
    private boolean judge(int n){
        for(int i=0;i<n;i++){
            if(arr[i]==arr[n]||Math.abs(n-i)==Math.abs(arr[n]-arr[i]))
                return false;
        }
        return true;
    }

    //打印
    public void print(){
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+"");
        }
        System.out.println();
    }
}

用一维数组arr表示棋子的放置位置，例如arr[0]=0表示的就是第一个棋子放置在第一行的第一列

put（）方法就是递归方法，除此之外还有一个judge（）方法判断所放棋子位置是否正确

在judge（）方法中要注意的是：arr[i]==arr[n]是判断棋子n是否跟之前的棋子在同一列；而Math.abs(n-i)==Math.abs(arr[n]-arr[i])则可以判断是否在同一斜线上

如果在同一斜线上，那么势必出现棋子行间距（n-i）与棋子列间距（arr[n]-arr[i]）相等，注意：间距是绝对值

另外，递归的终止判断标识就是放置的棋子是否到了第九颗（即n=8），这意味着前面的8颗都已经放置好了

结果是92种不同的放置方法

继续想一下，如果要计算N皇后问题，只需要将max赋为N即可