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. class Solution {
  5. public:
  6. int totalNQueens(int n) {
  7. this->count = 0;
  8. vector<int> C(n, 0); // C[i]表示第i行皇后所在的列编号
  9. dfs(C, 0);
  10. return this->count;
  11. }
  12. private:
  13. int count; // 解的个数
  14. void dfs(vector<int> &C, int row) {
  15. const int N = C.size();
  16. if (row == N) { // 终止条件,也是收敛条件,意味着找到了一个可行解
  17. ++this->count;
  18. return;
  19. }
  20. for (int j = 0; j < N; ++j) { // 扩展状态,一列一列的试
  21. const bool 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. bool isValid(const vector<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 (abs(i - row) == abs(C[i] - col)) return false;
  44. }
  45. return true;
  46. }
  47. };

代码2

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

相关题目

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