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`