八皇后问题

1来源

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任****意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

2思路

2.1构建思路

构建一个int【8】的数组，i是x，arr【i】是y，这样就形成了坐标

2.2检测冲突

直线就是arr【i】与arr【i-1】.。。arr【0】这些值是否相等，斜线就是x的变化值与y的变化值是否相等即i-j==arr【i】-arr【j】

1
2
3
4
5
6
7
8
9
public static boolean check(int[] arr,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;
    }

2.3放旗子思路

从第0个位置开始放就是arr【i】==0开始，用for写到8，如果不冲突就放下一个，也是for从0到8，当i==8就是放完了就返回到上一个，看把arr【i】往后移动会不会也成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void put(int max,int n,int[] arr){
        if (n==max){
            print(arr);

            //System.out.println(count);
            System.out.println();
            return;
        }
        for (int i = 0; i < max; i++) {
            arr[n]=i;//先放在第一位在后裔
            if (check(arr,n)){
                put(max,n+1,arr);
            }
        }
    }

3完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class 八皇后 {
    public static void main(String[] args) {
        int max=8;
        int[] arr=new int[max];
        put(max,0,arr);
    }

    public static boolean check(int[] arr,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;
    }
    public static void put(int max,int n,int[] arr){
        if (n==max){
            print(arr);

            //System.out.println(count);
            System.out.println();
            return;
        }
        for (int i = 0; i < max; i++) {
            arr[n]=i;//先放在第一位在后裔
            if (check(arr,n)){
                put(max,n+1,arr);
            }
        }
    }
    public static void print(int[] arr){
        for (int i = 0; i <arr.length ; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}