Count Ways to Place N Queens
You have an n x n chess board and n queens.
A queen attacks every cell in its row, its column and both of its diagonals.
Return the number of different ways to place all n queens on the board so that no two queens attack each other.
Note
Two placements are different if at least one cell has a queen in one placement and not in the other. Placements that are rotations or mirror images of each other are still counted separately.
Each row must hold exactly one queen. Place them row by row. For each row, try every column that is not attacked yet, and go back (backtrack) when no column is free. Keep three sets: used columns, used row - col diagonals and used row + col diagonals.
Examples
Example 1
- Input:
- 4
- Output:
- 2
On a 4 x 4 board there are exactly two safe placements. One has queens in columns 1, 3, 0, 2 (row by row), and the other is its mirror image: 2, 0, 3, 1.
Example 2
- Input:
- 1
- Output:
- 1
One queen on a 1 x 1 board has nothing to attack, so there is one way.
Example 3
- Input:
- 3
- Output:
- 0
On a 3 x 3 board every placement of three queens has two queens on the same row, column or diagonal, so there is no way.
Constraints
1 <= n <= 10
Run checks your code against the 3 examples. Submit checks it against all 13 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.