八皇后

女爷i 2022-07-29 10:52 205阅读 0赞

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

# 算法中检测冲突方法的分析 #

NxN棋盘，用a\[m\]=n（m <= N, n<=N）来表示第m个皇后在棋盘上的n行m列。  
1 每个皇后的索引m都不同，皇后在同一列发生冲突的情况不存在。  
2 判断皇后是否在同一行n  
3 判断皇后是否在两个对角线方向

// 只检查第1列到第n列（n <= N），因为n列以后还没有进行皇后位置排布，不必检查
    public static boolean  Check(int a[], int n) { 
        for (int i = 1; i < n; i++) {
            // 只检测皇后是否在两个对角线方向和是否在同一行
            if (Math.abs(a[i]-a[n])==Math.abs(i-n) || a[i] == a[n])
                return false;
        }
        return true;
    }

# 算法的实现 #

// 简单粗暴的算法
    public class eightQueens {
        
        public static void main(String[] args) {
            int a[] = new int [9];
            int i, t = 1;
    
            // a[m] = n 即把第m个皇后放在第n列
            for (a[1] = 1; a[1] < 9; a[1]++) {
                for (a[2] = 1; a[2] < 9; a[2]++) {
                    if (!Check(a, 2)) continue;
                    for (a[3] = 1; a[3] < 9; a[3]++) {
                        if (!Check(a, 3)) continue;
                        for (a[4] = 1; a[4] < 9; a[4]++) {
                            if (!Check(a, 4)) continue;
                            for (a[5] = 1; a[5] < 9; a[5]++) {
                                if (!Check(a, 5)) continue;
                                for (a[6] = 1; a[6]< 9; a[6]++) {
                                    if (!Check(a, 6)) continue;
                                    for (a[7] = 1; a[7] < 9; a[7]++) {
                                        if (!Check(a, 7)) continue;
                                        for (a[8] = 1; a[8] < 9; a[8]++) {
                                            if (!Check(a, 8)) continue;
                                            else {
                                                System.out.format("第%d种解法:\n", t++);
                                                for (i=1; i < 9; i++)
                                                    System.out.format("第%d个皇后：%d\n", i, a[i]);
                                                System.out.println("\n");
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
    
                }
            }
    
        }
    
        // 只检查第1列到第n列，因为n列以后还没有进行皇后位置排布，不必检查
        public static boolean  Check(int a[], int n) { 
            for (int i = 1; i < n; i++) {
                if (Math.abs(a[i]-a[n])==Math.abs(i-n) || a[i] == a[n])
                    return false;
            }
            return true;
        }
    }

// 回溯法
    // a[m]=n 表示第m个皇后在棋盘的第n行
    public class eightQueens2 {
        public static void main(String[] args) {
            int a[] = new int[256]; // 数组默认初始化为0
            int j, N, t = 1;
            System.out.println("请输入皇后个数：");
            Scanner sc = new Scanner(System.in);
            N = sc.nextInt();
    
            int i = 1; // 第i个皇后
            while (i > 0) { // 当所有的位置被找出来后，表示皇后i为-1,结束循环
                for (a[i]++; a[i] <= N; a[i]++) {
                    if(Check(a, i)) // 检查前i列有有无冲突
                        break;
                }
                if (a[i] <= N) {
                    if (i == N) { // 找出一组解输出
                        System.out.format("第%d种解法：\n", t++);
                        for (j = 1; j <= N; j++) {
                            System.out.format("第%d个皇后：%d\n", j, a[j]);
                        }
                        System.out.println("");
                    } else { // 未找完
                        i++;
                        a[i] = 0; 
                    }
                } else { // 回溯，回到上一个皇后的情况，重新给上一个皇后找合适的位置
                    i--;
                }
            }
        }
    
        // 只检查第1列到第n列，因为n列以后还没有进行皇后位置排布，不必检查
        public static boolean  Check(int a[], int n) { 
            for (int i = 1; i < n; i++) {
                if (Math.abs(a[i]-a[n])==Math.abs(i-n) || a[i] == a[n])
                    return false;
            }
            return true;
        }
    }

// 使用递归方式
    public class eightQueens3 {
        static int a[]  = new int[20];
        static int N, i, j, t =1;
    
        public static void main(String [] args) {
            System.out.println("几皇后？ N=");
            Scanner sc = new Scanner(System.in);
            N = sc.nextInt();
            Try(1);
        }
    
        // 每个皇后都检测是否与前面的皇后冲突，当都不冲突时，继续找下一个皇后的位置，找到最后一个皇后时，打印所有皇后位置，
        public static void Try(int i) {
            int j, k;
            for (j = 1; j <= N; j++) {
                a[i] = j;
                if (Check(a, i)) {
                    if (i < N) 
                        Try(i+1); // 该皇后与前面的皇后不冲突，则找下一个皇后的位置
                    else {
                        System.out.format("第%d种解法：\n", t++);
                        for (k = 1; k <= N; k++) 
                            System.out.format("第%d个皇后：%d\n", k, a[k]);
                        System.out.println("");
                    }
                }
            }
        }
    
        // 只检查第1列到第n列，因为n列以后还没有进行皇后位置排布，不必检查
        public static boolean  Check(int a[], int n) { 
            for (int i = 1; i < n; i++) {
                if (Math.abs(a[i]-a[n])==Math.abs(i-n) || a[i] == a[n])
                    return false;
            }
            return true;
        }
    }
    
    
    /* 递归：递好找，重点是归
     * 嵌套函数的调用，包括同名函数的调用，主要是栈的使用
     * 如果是同名函数的嵌套调用又叫递归
     * 数据结构中栈的应用：先进后出的理念
     * 
     */