LeetCode in TypeScript
52. N-Queens II
Hard
The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return the number of distinct solutions to the n-queens puzzle.
Example 1:
Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.
Example 2:
Input: n = 1
Output: 1
Constraints:
1 <= n <= 9
Solution
function totalNQueens(n: number): number {
function solve(r: number, cols: boolean[], diag: boolean[], antiDiag: boolean[]): number {
if (r === n) {
return 1
}
let count = 0
for (let c = 0; c < n; c++) {
if (!cols[c] && !diag[r + c] && !antiDiag[r - c + n - 1]) {
cols[c] = diag[r + c] = antiDiag[r - c + n - 1] = true
count += solve(r + 1, cols, diag, antiDiag)
cols[c] = diag[r + c] = antiDiag[r - c + n - 1] = false
}
}
return count
}
return solve(0, new Array(n).fill(false), new Array(2 * n - 1).fill(false), new Array(2 * n - 1).fill(false))
}
export { totalNQueens }