51. N-Queens
n 皇后問題是一個在 n x n 棋盤上放置 n 個皇后，使得任何兩個皇后之間都不能互相攻擊的問題。
給定一個整數 n，返回所有 n 皇后問題的不同解法。你可以以任意順序返回答案。
每個解法包含一個 n 皇后放置的棋盤配置，其中 'Q' 表示皇后，'.' 表示空位。
範例 1：
輸入：n = 4 輸出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解釋：如上圖所示，共有兩種不同的解法。
Python
from typing import List
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def backtrack(row: int):
if row == n:
board = ["".join(row) for row in board_state]
result.append(board)
return
for col in range(n):
if col in cols or (row - col) in pos_diags or (row + col) in neg_diags:
continue
# Place the queen
board_state[row][col] = 'Q'
cols.add(col)
pos_diags.add(row - col)
neg_diags.add(row + col)
# Move to the next row
backtrack(row + 1)
# Remove the queen and backtrack
board_state[row][col] = '.'
cols.remove(col)
pos_diags.remove(row - col)
neg_diags.remove(row + col)
result = []
board_state = [['.'] * n for _ in range(n)]
cols = set()
pos_diags = set()
neg_diags = set()
backtrack(0)
return result
16.98MB, 34ms
C++
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> result;
vector<string> board(n, string(n, '.'));
unordered_set<int> cols, posDiags, negDiags;
backtrack(0, n, board, cols, posDiags, negDiags, result);
return result;
}
private:
void backtrack(int row, int n, vector<string>& board, unordered_set<int>& cols,
unordered_set<int>& posDiags, unordered_set<int>& negDiags,
vector<vector<string>>& result) {
if (row == n) {
result.push_back(board);
return;
}
for (int col = 0; col < n; ++col) {
if (cols.find(col) != cols.end() || posDiags.find(row - col) != posDiags.end()
|| negDiags.find(row + col) != negDiags.end()) {
continue;
}
// Place the queen
board[row][col] = 'Q';
cols.insert(col);
posDiags.insert(row - col);
negDiags.insert(row + col);
// Move to the next row
backtrack(row + 1, n, board, cols, posDiags, negDiags, result);
// Remove the queen and backtrack
board[row][col] = '.';
cols.erase(col);
posDiags.erase(row - col);
negDiags.erase(row + col);
}
}
};
12.43MB, 11ms
Javascript
/**
* @param {number} n
* @return {string[][]}
*/
var solveNQueens = function(n) {
const result = [];
const board = Array.from({ length: n }, () => '.'.repeat(n));
const cols = new Set();
const posDiags = new Set();
const negDiags = new Set();
const backtrack = (row) => {
if (row === n) {
result.push([...board]);
return;
}
for (let col = 0; col < n; col++) {
if (cols.has(col) || posDiags.has(row - col) || negDiags.has(row + col)) {
continue;
}
// Place the queen
board[row] = board[row].substring(0, col) + 'Q' + board[row].substring(col + 1);
cols.add(col);
posDiags.add(row - col);
negDiags.add(row + col);
// Move to the next row
backtrack(row + 1);
// Remove the queen and backtrack
board[row] = board[row].substring(0, col) + '.' + board[row].substring(col + 1);
cols.delete(col);
posDiags.delete(row - col);
negDiags.delete(row + col);
}
};
backtrack(0);
return result;
};
