LeetCode 51: N-Queens (Backtracking with Column/Diagonal Constraints)
LeetCode 51BacktrackingConstraint SearchToday we solve LeetCode 51 - N-Queens.
Source: https://leetcode.com/problems/n-queens/
English
Problem Summary
Place n queens on an n x n chessboard so that no two queens attack each other. Return all distinct board configurations.
Key Insight
We place queens row by row. For each row, we only try columns that are not already used, and whose diagonals are also free. This turns brute-force placement into aggressive pruning.
Brute Force and Limitations
Trying all board combinations is exponential with huge waste. Most partial boards fail early, so we should detect conflicts immediately instead of waiting until the board is full.
Optimal Algorithm Steps (Backtracking)
1) Keep three sets/arrays: used columns, used main diagonals (row-col), used anti-diagonals (row+col).
2) DFS from row 0.
3) For each column in current row, skip if any constraint is occupied.
4) Place queen, mark constraints, recurse next row.
5) On return, undo marks (backtrack).
6) If row reaches n, convert board to strings and record a solution.
Complexity Analysis
Time: roughly O(n!) in worst case (pruned heavily in practice).
Space: O(n) recursion depth and constraint bookkeeping (excluding output).
Common Pitfalls
- Forgetting diagonal indexing offsets (especially row - col + n style mapping).
- Not undoing marks during backtracking.
- Mutating shared row buffers incorrectly when generating output strings.
- Returning one solution instead of all solutions.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> ans = new ArrayList<>();
char[][] board = new char[n][n];
for (char[] row : board) Arrays.fill(row, '.');
boolean[] col = new boolean[n];
boolean[] diag1 = new boolean[2 * n]; // row - col + n
boolean[] diag2 = new boolean[2 * n]; // row + col
dfs(0, n, board, col, diag1, diag2, ans);
return ans;
}
private void dfs(int r, int n, char[][] board, boolean[] col, boolean[] diag1, boolean[] diag2,
List<List<String>> ans) {
if (r == n) {
List<String> one = new ArrayList<>();
for (int i = 0; i < n; i++) one.add(new String(board[i]));
ans.add(one);
return;
}
for (int c = 0; c < n; c++) {
int d1 = r - c + n;
int d2 = r + c;
if (col[c] || diag1[d1] || diag2[d2]) continue;
board[r][c] = 'Q';
col[c] = diag1[d1] = diag2[d2] = true;
dfs(r + 1, n, board, col, diag1, diag2, ans);
board[r][c] = '.';
col[c] = diag1[d1] = diag2[d2] = false;
}
}
}func solveNQueens(n int) [][]string {
ans := [][]string{}
board := make([][]byte, n)
for i := 0; i < n; i++ {
board[i] = make([]byte, n)
for j := 0; j < n; j++ {
board[i][j] = '.'
}
}
col := make([]bool, n)
diag1 := make([]bool, 2*n) // row - col + n
diag2 := make([]bool, 2*n) // row + col
var dfs func(int)
dfs = func(r int) {
if r == n {
one := make([]string, n)
for i := 0; i < n; i++ {
one[i] = string(board[i])
}
ans = append(ans, one)
return
}
for c := 0; c < n; c++ {
d1, d2 := r-c+n, r+c
if col[c] || diag1[d1] || diag2[d2] {
continue
}
board[r][c] = 'Q'
col[c], diag1[d1], diag2[d2] = true, true, true
dfs(r + 1)
board[r][c] = '.'
col[c], diag1[d1], diag2[d2] = false, false, false
}
}
dfs(0)
return ans
}class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> ans;
vector<string> board(n, string(n, '.'));
vector<bool> col(n, false), diag1(2 * n, false), diag2(2 * n, false);
dfs(0, n, board, col, diag1, diag2, ans);
return ans;
}
void dfs(int r, int n, vector<string>& board, vector<bool>& col,
vector<bool>& diag1, vector<bool>& diag2, vector<vector<string>>& ans) {
if (r == n) {
ans.push_back(board);
return;
}
for (int c = 0; c < n; c++) {
int d1 = r - c + n;
int d2 = r + c;
if (col[c] || diag1[d1] || diag2[d2]) continue;
board[r][c] = 'Q';
col[c] = diag1[d1] = diag2[d2] = true;
dfs(r + 1, n, board, col, diag1, diag2, ans);
board[r][c] = '.';
col[c] = diag1[d1] = diag2[d2] = false;
}
}
};class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
ans = []
board = [['.'] * n for _ in range(n)]
col = [False] * n
diag1 = [False] * (2 * n) # row - col + n
diag2 = [False] * (2 * n) # row + col
def dfs(r: int) -> None:
if r == n:
ans.append([''.join(row) for row in board])
return
for c in range(n):
d1, d2 = r - c + n, r + c
if col[c] or diag1[d1] or diag2[d2]:
continue
board[r][c] = 'Q'
col[c] = diag1[d1] = diag2[d2] = True
dfs(r + 1)
board[r][c] = '.'
col[c] = diag1[d1] = diag2[d2] = False
dfs(0)
return ans/**
* @param {number} n
* @return {string[][]}
*/
var solveNQueens = function(n) {
const ans = [];
const board = Array.from({ length: n }, () => Array(n).fill('.'));
const col = Array(n).fill(false);
const diag1 = Array(2 * n).fill(false); // row - col + n
const diag2 = Array(2 * n).fill(false); // row + col
const dfs = (r) => {
if (r === n) {
ans.push(board.map(row => row.join('')));
return;
}
for (let c = 0; c < n; c++) {
const d1 = r - c + n;
const d2 = r + c;
if (col[c] || diag1[d1] || diag2[d2]) continue;
board[r][c] = 'Q';
col[c] = diag1[d1] = diag2[d2] = true;
dfs(r + 1);
board[r][c] = '.';
col[c] = diag1[d1] = diag2[d2] = false;
}
};
dfs(0);
return ans;
};中文
题目概述
在 n x n 棋盘上放置 n 个皇后，要求任意两个皇后都不能互相攻击，返回所有不同的可行棋盘方案。
核心思路
按“行”递归放置皇后。每一行只尝试当前不冲突的列，并通过列、主对角线、副对角线三类约束做剪枝，快速跳过无效分支。
基线解法与不足
如果直接枚举所有摆法，组合数量爆炸且大量分支会很早失败。更好的做法是在每一步放置前就立即检查冲突，提前剪枝。
最优算法步骤（回溯 + 约束剪枝）
1）维护三组状态：列是否占用、主对角线 (row-col) 是否占用、副对角线 (row+col) 是否占用。
2）从第 0 行开始 DFS。
3）枚举当前行每一列，若任一约束冲突则跳过。
4）放置皇后并标记约束，递归到下一行。
5）递归返回后撤销标记（回溯）。
6）当行号到达 n，将棋盘转成字符串数组加入答案。
复杂度分析
时间复杂度：最坏约 O(n!)（实际因剪枝通常明显更快）。
空间复杂度：O(n) 递归深度与约束状态（不含输出结果）。
常见陷阱
- 对角线下标映射写错（尤其是 row-col+n 偏移）。
- 回溯时忘记撤销占用标记。
- 生成结果时误用共享可变结构导致结果被后续修改。
- 只返回一种解，漏掉其余可行解。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> ans = new ArrayList<>();
char[][] board = new char[n][n];
for (char[] row : board) Arrays.fill(row, '.');
boolean[] col = new boolean[n];
boolean[] diag1 = new boolean[2 * n]; // row - col + n
boolean[] diag2 = new boolean[2 * n]; // row + col
dfs(0, n, board, col, diag1, diag2, ans);
return ans;
}
private void dfs(int r, int n, char[][] board, boolean[] col, boolean[] diag1, boolean[] diag2,
List<List<String>> ans) {
if (r == n) {
List<String> one = new ArrayList<>();
for (int i = 0; i < n; i++) one.add(new String(board[i]));
ans.add(one);
return;
}
for (int c = 0; c < n; c++) {
int d1 = r - c + n;
int d2 = r + c;
if (col[c] || diag1[d1] || diag2[d2]) continue;
board[r][c] = 'Q';
col[c] = diag1[d1] = diag2[d2] = true;
dfs(r + 1, n, board, col, diag1, diag2, ans);
board[r][c] = '.';
col[c] = diag1[d1] = diag2[d2] = false;
}
}
}func solveNQueens(n int) [][]string {
ans := [][]string{}
board := make([][]byte, n)
for i := 0; i < n; i++ {
board[i] = make([]byte, n)
for j := 0; j < n; j++ {
board[i][j] = '.'
}
}
col := make([]bool, n)
diag1 := make([]bool, 2*n) // row - col + n
diag2 := make([]bool, 2*n) // row + col
var dfs func(int)
dfs = func(r int) {
if r == n {
one := make([]string, n)
for i := 0; i < n; i++ {
one[i] = string(board[i])
}
ans = append(ans, one)
return
}
for c := 0; c < n; c++ {
d1, d2 := r-c+n, r+c
if col[c] || diag1[d1] || diag2[d2] {
continue
}
board[r][c] = 'Q'
col[c], diag1[d1], diag2[d2] = true, true, true
dfs(r + 1)
board[r][c] = '.'
col[c], diag1[d1], diag2[d2] = false, false, false
}
}
dfs(0)
return ans
}class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> ans;
vector<string> board(n, string(n, '.'));
vector<bool> col(n, false), diag1(2 * n, false), diag2(2 * n, false);
dfs(0, n, board, col, diag1, diag2, ans);
return ans;
}
void dfs(int r, int n, vector<string>& board, vector<bool>& col,
vector<bool>& diag1, vector<bool>& diag2, vector<vector<string>>& ans) {
if (r == n) {
ans.push_back(board);
return;
}
for (int c = 0; c < n; c++) {
int d1 = r - c + n;
int d2 = r + c;
if (col[c] || diag1[d1] || diag2[d2]) continue;
board[r][c] = 'Q';
col[c] = diag1[d1] = diag2[d2] = true;
dfs(r + 1, n, board, col, diag1, diag2, ans);
board[r][c] = '.';
col[c] = diag1[d1] = diag2[d2] = false;
}
}
};class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
ans = []
board = [['.'] * n for _ in range(n)]
col = [False] * n
diag1 = [False] * (2 * n) # row - col + n
diag2 = [False] * (2 * n) # row + col
def dfs(r: int) -> None:
if r == n:
ans.append([''.join(row) for row in board])
return
for c in range(n):
d1, d2 = r - c + n, r + c
if col[c] or diag1[d1] or diag2[d2]:
continue
board[r][c] = 'Q'
col[c] = diag1[d1] = diag2[d2] = True
dfs(r + 1)
board[r][c] = '.'
col[c] = diag1[d1] = diag2[d2] = False
dfs(0)
return ans/**
* @param {number} n
* @return {string[][]}
*/
var solveNQueens = function(n) {
const ans = [];
const board = Array.from({ length: n }, () => Array(n).fill('.'));
const col = Array(n).fill(false);
const diag1 = Array(2 * n).fill(false); // row - col + n
const diag2 = Array(2 * n).fill(false); // row + col
const dfs = (r) => {
if (r === n) {
ans.push(board.map(row => row.join('')));
return;
}
for (let c = 0; c < n; c++) {
const d1 = r - c + n;
const d2 = r + c;
if (col[c] || diag1[d1] || diag2[d2]) continue;
board[r][c] = 'Q';
col[c] = diag1[d1] = diag2[d2] = true;
dfs(r + 1);
board[r][c] = '.';
col[c] = diag1[d1] = diag2[d2] = false;
}
};
dfs(0);
return ans;
};
Comments