Problems178
Search for a command to run...
Initialization
Place exactly one queen per row, working downwards. Only the rows above matter when testing a square, so safety is checked straight up and along the two upward diagonals.
Backtracking
1function isSafe(board, row, col) {2 let r = row, c = col;3 4 // Upper-left diagonal5 while (r >= 0 && c >= 0) {6 if (board[r][c] === 'Q') return false;7 r--; c--;8 }9 10 // Straight up11 r = row; c = col;12 while (r >= 0) {13 if (board[r][c] === 'Q') return false;14 r--;15 }16 17 // Upper-right diagonal18 r = row; c = col;19 while (r >= 0 && c < board[0].length) {20 if (board[r][c] === 'Q') return false;21 r--; c++;22 }23 //n: 4solutions: 024 return true;25}26 27function func(row, ans, board) {28 // Every row filled29 if (row === board.length) {30 ans.push(board.map(r => r.join("")));31 return;32 }33 34 for (let col = 0; col < board[0].length; col++) {35 if (isSafe(board, row, col)) {36 board[row][col] = 'Q';37 func(row + 1, ans, board);38 board[row][col] = '.';39 }40 }41}42 43function solveNQueens(n) {44 const ans = [];45 const board = Array.from({ length: n }, () => Array(n).fill('.'));46 func(0, ans, board);47 return ans;48}