N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行、不同列，也不在同一条斜线上。
给定一个整数n，返回n皇后的摆法有多少种。
举例： n=1，返回1。
n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0。
n=8，返回92。

  2. public class Code09_NQueens {
  4.     public static int num1(int n) {
  5.         if (n < 1) {
  6.             return 0;
  7.         }
  8.         int[] record = new int[n]; // record[i] --> i 行的皇后放在了第几列
  9.         return process1(0, record, n);
  10.     }
  12.     // i：表示来到了第几行
  13.     // record：之前摆放的皇后，都在这个数组中，即之前 i-1 行的皇后的摆放位置
  14.     // n：表示整体一共多少行
  15.     // 返回值是：摆完所有的皇后，合理的摆法有多少种
  16.     public static int process1(int i, int[] record, int n) {
  17.         if (i == n) {
  18.             return 1;
  19.         }
  20.         int res = 0;
  21.         // 在 i 行，尝试所有的列：j
  22.         for (int j = 0; j < n; j++) {
  23.             // 当前i行的皇后，放在第j列，会不会和之前（0...i-1）的皇后共行/共列/共斜线
  24.             if (isValid(record, i, j)) {
  25.                 // 如果是，则认为该位置是无效的
  26.                 // 如果不是，则认为该位置是有效的
  27.                 record[i] = j;
  28.                 res += process1(i + 1, record, n);
  29.             }
  30.         }
  31.         return res;
  32.     }
  34.     public static boolean isValid(int[] record, int i, int j) {
  35.         for (int k = 0; k < i; k++) {
  36.             if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
  37.                 return false;
  38.             }
  39.         }
  40.         return true;
  41.     }
  43.     public static int num2(int n) {
  44.         if (n < 1 || n > 32) {
  45.             return 0;
  46.         }
  47.         int upperLim = n == 32 ? -1 : (1 << n) - 1;
  48.         return process2(upperLim, 0, 0, 0);
  49.     }
  51.     // colLim : 列的限制，1的位置不能放皇后，0的位置可以（采用二进制来计算）
  52.     // leftDiaLim ：左斜线的限制，1的位置不能放皇后，0的位置可以（采用二进制来计算）
  53.     // rightDiaLim ：右斜线的限制，1的位置不能放皇后，0的位置可以（采用二进制来计算）
  54.     public static int process2(int upperLim, int colLim, int leftDiaLim,
  55.             int rightDiaLim) {
  56.         if (colLim == upperLim) {
  57.             return 1;
  58.         }
  59.         int pos = 0;
  60.         int mostRightOne = 0;
  61.         // 所有候选的皇后位置都在 pos 上，1为可选位置，0为不可选位置
  62.         pos = upperLim & (~(colLim | leftDiaLim | rightDiaLim));
  63.         int res = 0;
  64.         while (pos != 0) {
  65.             mostRightOne = pos & (~pos + 1);
  66.             pos = pos - mostRightOne;
  67.             res += process2(upperLim, colLim | mostRightOne,
  68.                     (leftDiaLim | mostRightOne) << 1,
  69.                     (rightDiaLim | mostRightOne) >>> 1);
  70.         }
  71.         return res;
  72.     }
  74.     public static void main(String[] args) {
  75.         int n = 14;
  77.         long start = System.currentTimeMillis();
  78.         System.out.println(num2(n));
  79.         long end = System.currentTimeMillis();
  80.         System.out.println("cost time: " + (end - start) + "ms");
  82.         start = System.currentTimeMillis();
  83.         System.out.println(num1(n));
  84.         end = System.currentTimeMillis();
  85.         System.out.println("cost time: " + (end - start) + "ms");
  87.     }
  88. }

二 采用回溯法

  1. /**
  2.  * 算法：回溯法
  3.  * 问题：八皇后 
  4.  * @author win
  5.  */
  6. public class EightQueen {
  8.     public static int num = 0;//累计方案
  9.     public static final int MAXQUEEN = 8;
  10.     public static int[] cols = new int[MAXQUEEN];//定义cols数组，表示八列棋子摆放的位置
  12.     /***
  13.      * 
  14.      * @param n 填第n列的皇后
  15.      */
  16.     public void getCount(int n){
  17.         boolean [] rows = new boolean[MAXQUEEN];//记录每列每个方格是否可以放皇后。为true表示不能放
  18.         for(int m =0;m<n;m++){
  19.             rows[cols[m]] = true;
  20.             int d = n - m;//斜对角
  21.             //正斜方向
  22.             if(cols[m] - d>=0){
  23.                 rows[cols[m] - d] = true;
  24.             }
  25.             //反斜方向
  26.             if((cols[m]+d)<=MAXQUEEN-1){
  27.                 rows[cols[m] + d] = true;
  28.             }
  29.         }
  30.         //到此知道了哪些位置不能放皇后
  31.         for(int i = 0;i<MAXQUEEN;i++){
  32.             if(rows[i]){
  33.                 //不能放
  34.                 continue;
  35.             }
  36.             cols[n] = i;
  37.             if(n<MAXQUEEN-1){
  38.                 getCount(n+1);
  39.             }else{
  40.                 //如果n = MAXQUEEN-1;表示找到了一套完整的方案
  41.                 num++;
  42.                 printQueen();
  43.             }
  44.             //下面可能仍有合法位置
  45.         }
  46.     }
  49.     private void printQueen() {
  50.         System.out.println("第"+num+"种方案");
  51.         for(int i = 0;i<MAXQUEEN;i++){
  52.             for(int j=0;j<MAXQUEEN;j++){
  53.                 if(i == cols[j]){
  54.                     System.out.print("0 ");
  55.                 }else{
  56.                     System.out.print("+ ");
  57.                 }
  58.             }
  59.             System.out.println();
  60.         }
  61.     }
  66.     public static void main(String[] args) {
  67.         EightQueen eightQueen = new EightQueen();
  68.         eightQueen.getCount(0);
  69.     }
  70. }