51. N-Queens
Tags:
Hard
Skills:
backtrack
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán N-Queens yêu cầu đặt N quân hậu lên bàn cờ N x N sao cho không có hai quân hậu nào tấn công lẫn nhau (không cùng hàng, cột hoặc đường chéo). Đây là một bài toán điển hình sử dụng thuật toán backtrack
Approach
Time and space complexity
Solution
1function solveNQueens(n: number): string[][] {
2 const solutions: string[][] = [];
3 const board: string[][] = Array.from({length: n}, () => Array(n).fill('.'))
4 const cols = new Set<number>();
5 const diag1 = new Set<number>(); // row + col
6 const diag2 = new Set<number>(); // row - col
7
8 function backtrack(row: number): void {
9 if(row === n) {
10 solutions.push(board.map(r => r.join('')));
11 return;
12 }
13
14 for(let col = 0; col < n; col++) {
15 if(cols.has(col) || diag1.has(row + col) || diag2.has(row - col)) {
16 continue;
17 }
18
19 board[row][col] = 'Q';
20 cols.add(col);
21 diag1.add(row + col);
22 diag2.add(row - col);
23
24 backtrack(row + 1);
25
26 board[row][col] = '.';
27 cols.delete(col);
28 diag1.delete(row + col);
29 diag2.delete(row - col);
30 }
31 }
32
33 backtrack(0);
34 return solutions
35};