HHot 100C++ 图解

51. N 皇后

一句话套路逐行放皇后,cols / 两条 diag 三个标记

题目描述

按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。

 

示例 1:

输入:n = 4
输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释:如上图所示,4 皇后问题存在两个不同的解法。

示例 2:

输入:n = 1
输出:[["Q"]]

 

提示:

  • 1 <= n <= 9

思路

时间O(n!)
空间O(n)

思路

一行放一个 -> 决策树只有 n 层,每层枚举列。

冲突检查三件事

同列、同主对角线(i-j)、同副对角线(i+j)。

用三个 bool 数组把检查降到 O(1):cols[j] / diag1[i-j+n-1] / diag2[i+j]。

变体

Q52 只要方案数 -> 不必存棋盘;位运算版本可以再快几倍。

图解

. 0 Q 1 . 2 . 3 . . . Q Q . . . . . Q . 任意两个皇后不在同一行列对角线
逐行放皇后,col / 两条对角线判冲突。回溯:放不下就换一列;一种解是一棵搜索树的叶子。

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/10_backtracking.cpp32 行
namespace lc0051 {
class Solution {
 public:
  vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> ans;
    if (n <= 0) return ans;  // 否则 2*n-1 = -1 会变成巨大的 vector<bool> 尺寸
    vector<string> board(n, string(n, '.'));
    vector<bool> cols(n, false), diag1(2 * n - 1, false), diag2(2 * n - 1, false);
    dfs(n, 0, board, cols, diag1, diag2, ans);
    return ans;
  }

 private:
  static void dfs(int n, int row, vector<string>& board, vector<bool>& cols, vector<bool>& d1,
                  vector<bool>& d2, vector<vector<string>>& ans) {
    if (row == n) {
      ans.push_back(board);
      return;
    }
    for (int col = 0; col < n; ++col) {
      int k1 = row - col + n - 1;  // 主对角线编号(平移成非负)
      int k2 = row + col;          // 副对角线编号
      if (cols[col] || d1[k1] || d2[k2]) continue;
      board[row][col] = 'Q';
      cols[col] = d1[k1] = d2[k2] = true;
      dfs(n, row + 1, board, cols, d1, d2, ans);
      board[row][col] = '.';  // 撤销
      cols[col] = d1[k1] = d2[k2] = false;
    }
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q51_n_queens11 行
lc0051::Solution s;
auto g4 = s.solveNQueens(4);
vector<vector<string>> want4{{"..Q.", "Q...", "...Q", ".Q.."}, {".Q..", "...Q", "Q...", "..Q."}};
sort(g4.begin(), g4.end());
sort(want4.begin(), want4.end());
CHECK_EQ(g4, want4);
CHECK_EQ(s.solveNQueens(1), vector<vector<string>>({{"Q"}}));
CHECK_EQ(s.solveNQueens(2).size(), (size_t)0);  // 2、3 皇后无解
CHECK_EQ(s.solveNQueens(3).size(), (size_t)0);
CHECK_EQ(s.solveNQueens(8).size(), (size_t)92);
CHECK_EQ(s.solveNQueens(0).size(), (size_t)0);  // n=0 时 2*n-1 = -1,不守卫会抛 length_error

↑↓ 选择↵ 打开/ 随时唤起