蓝桥杯------------2n皇后----（回溯法，Java)

短命女 2022-06-05 05:39 215阅读 0赞

一、2n皇后问题

问题描述：  
　　给定一个n\*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。  
输入格式  
　　输入的第一行为一个整数n，表示棋盘的大小。  
　　接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。  
输出格式  
　　输出一个整数，表示总共有多少种放法。  
样例输入  
4  
1 1 1 1  
1 1 1 1  
1 1 1 1  
1 1 1 1  
样例输出  
2

二、解题思想

实现解题的三步走：

1)第一步，从第一行的第一个进行放置皇后（先放黑或白都可以），然后首先要进行的是对当前位置能否放置皇后的判断，若是1，则可以放；若是0，则不能放。如果是0，则进行第一行的第二个的位置判断。如果是1，则进行第二步。

2)第二步，是在满足当前位置的值为1的情况下，进行“同一行、同一列或同一条对角线上，任意的两个白（黑）皇后都不在同一行、同一列或同一条对角线上”的判断，而判断的顺序为当前位置的上面，左对角线，右对角线是否有已经放过的白（黑）皇后，若有，则返回值为false，即该点不能进行白（黑）皇后的放置。则进行了同一行的下一位置的判断，依然是第一步和第二步的判断。若没有，则返回true，即该点可以放置，进行第三步操作。

3)第三步，在经过前两步的判断过后，则需要对通过判断的位置进行皇后的放置，白皇后用2表示，黑皇后用3表示，即对通过前两步判断的位置进行2或3的赋值。然后进行下一行第一个位置的放置。然后是**回溯法的重点，当完成所有的放置，或满足不了放置的条件则需要将放置了皇后的点的值改变为原来的1。**如果四个白皇后都放置完了，则进行黑皇后的放置，而黑皇后也满足了皇后个数的放置则表示找到了一种方法，计数变量进行加一操作**。**若过程中没有满足皇后的个数，进行上一步的回溯，下一位置继续进行判断，以此类推。

下面给出Java解题代码：

import  java.util.*;  
      
    public class 二N皇后问题  
    {  
        static int n,count=0;                  //n表示棋盘的大小，count则为上文提到的计数变量记录放置方法的个数
        static int map[][];                    //二维数组表示棋盘
        public static void main(String args[])  
        {  
            Scanner cn=new Scanner(System.in);  
            n=cn.nextInt();                    //相关变量的录入 
            map=new int[n][n];  
            for(int i=0;i<n;i++)               //棋盘具体值的录入（0或1）
                for(int j=0;j<n;j++)  
                    map[i][j]=cn.nextInt();  
            Put(0,2);                          //从第一行开始进行白皇后的放置，2代表白，3代表黑
            System.out.println(count);         //当所有的方法都寻找完成后，输出找到的方法个数
        }  
        public static void Put(int t,int s)    //放置皇后的函数
        {  
            if(t==n)                           //进行当前类型皇后的放置数量是否达到要求，即是否到了棋盘的最后一行
            {  
                if(s==2)Put(0,3);              //如果白皇后放置成功，则进行黑皇后的放置
                else count++;                  //放置方法招到了一种，计数变量进行值加一
                return ;                       //当前整体放置过程结束，进行程序的回溯
            }  
            for(int i=0;i<n;i++)               //对每一行的值逐个进行操作
            {             
                if(map[t][i]!=1)continue;      //当前位置是否为1的判断
                if(Check(t,i,s)){map[t][i]=s;} //是否满足题目要求判断，满足赋值
                else continue;                 //不满足，同一行的下一个位置
                Put(t+1,s);                    //下一行皇后的放置
                map[t][i]=1;                   //回溯法的关键      
            }  
            return ;                           //进行相应的回溯
        }  
        public static boolean Check(int t,int i,int s)   //满足题目要求的判断函数
        {  
            for(int q=t-1;q>=0;q--)                      //当前位置上方是否进行了相同皇后的放置 这行以下的还没放不检查  
            {  
                if(map[q][i]==s)return false;  
            }         
            for(int q=t-1,w=i-1;q>=0&&w>=0;q--,w--)      //检查左对角线 这行以下的还没放不检查  
            {  
                if(map[q][w]==s)return false;  
            }  
            for(int q=t-1,w=i+1;q>=0&&w<=n-1;q--,w++)    //检查右对角线 这行以下的还没放不检查  
            {  
                if(map[q][w]==s)return false;  
            }  
            return true;                                 //都满的情况下，则可以进行当前皇后的放置
        }  
    }

代码段中的Check();方法没有对同一行之前的位置进行判断，是因为同一行是从左到右依次放置的，若前面放了则直接是下一行的判断，不会是相邻右侧的位置进行放置，则不需要进行判断，同理右侧，下方都不用，因为还没有进行皇后的放置，本题是回溯法经典的应用，递归的思想。若想深刻的领悟，应该跟着程序一步步的进行解读，进行逐渐的理解，掌握递归的思想，回溯的精髓。若有疑问可留言。