228. N Queens
Place n queens on an n by n board so that no two attack each other.
A queen attacks along its row, its column, and both diagonals.
Print how many arrangements exist.
This is the problem backtracking was invented for. Place a queen in row 0, move to row 1, and if no square there is safe, go back and move the queen in row 0. Going back is the whole technique.
Two things make it fast enough. Placing exactly one queen per row removes rows
from the problem entirely. And a square is unsafe if its column, its
row - col, or its row + col is already used, so checking safety is three
lookups rather than a scan of the board.
Constraints - `1 ≤ n ≤ 12`
Input
A single line containing one integer n.
Output
Print one integer, the number of distinct arrangements.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.