N-Queens: Count the Boards

Place n queens on an n × n chessboard so that no two attack each other: no two share a row, a column or a diagonal. Return how many ways there are.

Examples

Example 1

Input:  n = 4
Output: 2

. Q . .      . . Q .
. . . Q      Q . . .
Q . . .      . . . Q
. . Q .      . Q . .