1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
|
const totalNQueens = function(n) { let res = [] let board = [] for (let i = 0; i < n; i++) { board.push('.'.repeat(n)) } backtrack(n, res, board) return res.length }
const backtrack = function(n, res, board = [], row = 0) { if (row === n) { return res.push([...board]) } for (let col = 0; col < n; col++) { if (isValid(board, row, col, n)) { board[row] = board[row].substr(0, col) + 'Q' + board[row].substr(col + 1) backtrack(n, res, board, row + 1) board[row] = board[row].substr(0, col) + '.' + board[row].substr(col + 1) } } }
const isValid = function(board, r, c, n) { for (let i = 0; i < r; i++) { if (board[i][c] === 'Q') { return false } } for (let i = r - 1, j = c - 1; i >= 0 && j >= 0; i--, j--) { if (board[i][j] === 'Q') { return false } } for (let i = r - 1, j = c + 1; i >= 0 && j < n; i--, j++) { if (board[i][j] === 'Q') { return false } } return true }
|