递归解决八皇后回溯算法

ゝ一世哀愁。 2023-07-08 02:51 56阅读 0赞

**问题简述：八皇后问题是一个古来而著名的问题，该问题是19世纪著名的数学家高斯同学提出来的。在8\*8的国际象棋上摆放八个皇后，使其不能互相的攻击，也就是说，任意的两个皇后不能放在同一行或则是同一个列或者是同一个对角线上，问有多少个摆放的方法**

代码：

package com.yg.recursion;/*
    @author  GeQiLin
    @date    2020/2/24  20:30
    求解8皇后问题
    */
    
    public class Queen8 {
        /*
         * arr[i]=value代表第i+1个皇后在第value+1个位子，
         * */
        private int MAX=8;
        private int[] arr=new int[MAX];//存放皇后的位置
        private int count=0;
        public static void main(String[] args) {
            Queen8 queen=new Queen8();
            queen.check(0);
            System.out.println("共有"+queen.count+"种摆法");
        }
    
    //放置第n个皇后
        private void check(int n){
            //此时8个皇后已经存放完成，应为n是从0开始
            if(n==MAX){
                printfArr();
                return;
            }
            /*
            * for循环作用
            * 1.冲突时，用于移动位置使得不冲突
            * 2.不冲突时配合递归，可以依次摆放下一个皇后的位置
            * 3.当出现一种摆法后，从最后一个皇后的位置开始改变尝试新的摆法
            * */
            for (int i = 0; i <MAX; i++) {
                arr[n]=i;//用于移动皇后的位置
                if(!judge(n)){
                    //不冲突,摆放下一个皇后
                    check(n+1);
                }
            }
    
        }
    
        /*
        判断是否冲突
        * 每一个皇后不能在同一行，同一列，同一斜线
        * n为第几个皇后
        * */
        private boolean judge(int n){
            //判断地n个皇后与前面第n+1个皇后位置是否冲突
            for (int i = 0; i < n; i++) {
               //判断是不是在同一列，或者一条斜线上
                if(arr[i]==arr[n] || Math.abs(i-n)==Math.abs(arr[i]-arr[n])){
                    return true;
                }
            }
            return false;
        }
    
        //打印皇后位置
        private void printfArr(){
            count++;
            for (int i = 0; i < MAX; i++) {
                System.out.print(arr[i]+" ");
            }
            System.out.println();
        }
    }