51. N-Queens

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};