nQueens

Hard · Recursion · 3 test cases

The N-Queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other. Given an integer N, return the number of distinct solutions to the N-Queens puzzle.

Examples

nQueens(4) → 2
nQueens(1) → 1

Starter code

function nQueens(n) {

}

Complexity of the optimal solution

Time O(n!), space O(n). This problem is solved using backtracking. The algorithm explores possible queen placements row by row. While it prunes many branches, the upper bound on the number of possibilities is n!, making it factorial time complexity. The space is determined by the recursion depth and the sets, which is O(n).

Solve nQueens in the browser