深搜回溯解决n皇后的优化--对称优化

因为有镜面对称，那么可以让第一行放的皇后只放在左半边，其他行的皇后都能任意放

需要注意的是当奇数棋盘时，如果第一行的皇后放在中间，那么左右对称中会重复，那么就需要将第二行的皇后也只放左半边即可。

自己在写时对于列这个边界参数出错了。。。因为自己写的是从下标0开始，没有太在意这个和在遍历列时的<= 所以浪费了很多时间。

public class n皇后对称优化 {
   static int n;
   static int cnt;//计算有多少种放法
   static int[] rec;
   public static void main(String[] args) {
           n = 5;
            rec = new int[n];
            dfs(0,(n+1)/2); //注意下标是从0开始
            System.out.println(cnt*2);//结果X2
   }


   //传入行因为每一行只能有一个   rec[row] = ？来表示这行的皇后放在第几列比如 rec[0]=1 表示第1行的皇后放在第2列
   //y表示放置行数的边界的只能放第1列到第y-1列因为for循环是小于 <y
   public static void dfs(int row,int y) {
       if(row==n) {
           cnt++;//到了边界就++
           return;//return 继续找其他可能
       }

       //依次尝试把皇后放在边界的每一列
       for(int col=0;col<y;col++) { //<y 一开始写成<=y 那么当传入n时就会出现 col = n的情况了
           if(check(row,col)) {
               rec[row] = col; //表示row这行的皇后放在col列

               //当棋盘为奇数时，第一行的皇后放在中间位置时第二行的皇后必须放在左半边区域
               if(n%2!=0 && row==0 && col==(n+1)/2-1) //要-1是因为下标从0开始
                   dfs(row+1,(n+1)/2-1);
               else
                   dfs(row+1,n); //否则第二行开始可以放在任何一列


               //这里其实不回溯也可以初步想的是因为不用检查行所以不设置为0也没有关系

           }
       }
   }

   //检查该列有没有皇后和正反对角线有没有皇后
   //不需要检查行有没有皇后，因为是从第一行开始往下深搜放，那么新的一行肯定是没放的
   //检查正反对角线可以画出一个3X3的图可发现正对角线如果有放皇后那么其坐标行列相减肯定与本次要放的相等i-rec[i] = row-col
   //如果反对角线的某个位置放了皇后那么行列相加肯定相等 i+rec[i] = row+col;
   private static boolean check(int row, int col) {
       //从第0检查到row-1 因为row和大于row的行数肯定都是还没有皇后的所以只需要检查其前面的每一行有没放到同一个列的皇后
       for(int i=0;i<row;i++) {
           if(rec[i]==col||i+rec[i]==row+col||i-rec[i]==row-col)
               return false;
       }
       return true;
   }
}

对于check()函数还可以进行优化，可以用数组来记录表示该正反斜线和列是否有皇后，那么每次就不需要遍历来检查，直接访问数组记录的值来看是否记录过

深搜回溯解决n皇后的优化--对称优化

相关推荐