#188HardBacktracking· N-Queens with Bitmask Pruning

Museum Guard Placements

A museum floor is an `n x n` grid of tiles. The curator wants to place exactly `n` security guards, one per tile, so that no two guards can see each other. A guard sees along the full length of his row, his column and both diagonals through his tile, and nothing blocks the view. Return the number of different ways to place the guards. Two placements are different if some tile holds a guard in one of them and not in the other.

Input format

`n`: the side length of the floor.

Output format

An integer: the number of valid placements.

Examples

Input: n = 4

Output: 2

On a 4 x 4 floor exactly two placements work: they are mirror images of each other.

Input: n = 1

Output: 1

A single tile holds the single guard.

Input: n = 3

Output: 0

Three guards cannot be placed on a 3 x 3 floor without two of them seeing each other, so the count is 0.

Constraints

1 <= n <= 12

Study first

Recursion and Divide and Conquer

#backtracking
#bit-manipulation
#recursion
#counting