N-Queens II

描述

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

分析

只需要输出解的个数，不需要输出所有解，代码要比上一题简化很多。设一个全局计数器，每找到一个解就增1。

代码1

  1. // N-Queens II
  2. // 深搜+剪枝
  3. // 时间复杂度O(n!*n)，空间复杂度O(n)
  4. public class Solution {
  5.     public int totalNQueens(int n) {
  6.         this.count = 0;
  8.         int[] C = new int[n]; // C[i]表示第i行皇后所在的列编号
  9.         dfs(C, 0);
  10.         return this.count;
  11.     }
  13.     void dfs(int[] C, int row) {
  14.         final int n = C.length;
  15.         if (row == n) { // 终止条件，也是收敛条件，意味着找到了一个可行解
  16.             ++this.count;
  17.             return;
  18.         }
  20.         for (int j = 0; j < n; ++j) {  // 扩展状态，一列一列的试
  21.             final boolean ok = isValid(C, row, j);
  22.             if (!ok) continue;  // 剪枝：如果合法，继续递归
  23.             // 执行扩展动作
  24.             C[row] = j;
  25.             dfs(C, row + 1);
  26.             // 撤销动作
  27.             // C[row] = -1;
  28.         }
  29.     }
  30.     /**
  31.      * 能否在 (row, col) 位置放一个皇后.
  32.      *
  33.      * @param C 棋局
  34.      * @param row 当前正在处理的行，前面的行都已经放了皇后了
  35.      * @param col 当前列
  36.      * @return 能否放一个皇后
  37.      */
  38.     private static boolean isValid(int[] C, int row, int col) {
  39.         for (int i = 0; i < row; ++i) {
  40.             // 在同一列
  41.             if (C[i] == col) return false;
  42.             // 在同一对角线上
  43.             if (Math.abs(i - row) == Math.abs(C[i] - col)) return false;
  44.         }
  45.         return true;
  46.     }
  47.     private int count; // 解的个数
  48. }

代码2

  1. // N-Queens II
  2. // 深搜+剪枝
  3. // 时间复杂度O(n!)，空间复杂度O(n)
  4. public class Solution {
  5.     public int totalNQueens(int n) {
  6.         this.count = 0;
  7.         this.columns = new boolean[n];
  8.         this.main_diag = new boolean[2 * n - 1];
  9.         this.anti_diag = new boolean[2 * n - 1];
  11.         int[] C = new int[n]; // C[i]表示第i行皇后所在的列编号
  12.         dfs(C, 0);
  13.         return this.count;
  14.     }
  16.     void dfs(int[] C, int row) {
  17.         final int N = C.length;
  18.         if (row == N) { // 终止条件，也是收敛条件，意味着找到了一个可行解
  19.             ++this.count;
  20.             return;
  21.         }
  23.         for (int j = 0; j < N; ++j) {  // 扩展状态，一列一列的试
  24.             final boolean ok = !columns[j] &&
  25.                     !main_diag[row - j + N - 1] &&
  26.                     !anti_diag[row + j];
  27.             if (!ok) continue;  // 剪枝：如果合法，继续递归
  28.             // 执行扩展动作
  29.             C[row] = j;
  30.             columns[j] = main_diag[row - j + N - 1] =
  31.                     anti_diag[row + j] = true;
  32.             dfs(C, row + 1);
  33.             // 撤销动作
  34.             // C[row] = -1;
  35.             columns[j] = main_diag[row - j + N - 1] =
  36.                     anti_diag[row + j] = false;
  37.         }
  38.     }
  40.     private int count; // 解的个数
  41.     // 这三个变量用于剪枝
  42.     private boolean[] columns;   // 表示已经放置的皇后占据了哪些列
  43.     private boolean[] main_diag; // 占据了哪些主对角线
  44.     private boolean[] anti_diag; // 占据了哪些副对角线
  46.     public static void main(String[] args) {
  47.         Solution s = new Solution();
  48.         s.totalNQueens(1);
  49.     }
  50. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/dfs/n-queens-ii.html