N-Queens

Place n chess queens on an n × n board so that no two attack each other (no two share a row, column or diagonal). Print every solution.

Input: one integer n.

Output:

• line 1: the number of solutions k
• then the k boards, each preceded by an empty line. A board is n lines of n characters: Q for a queen, . for an empty square.

Order the solutions by the queen's column in row 1, then in row 2, and so on (smaller column first) — the order you get by trying columns left to right.

Constraints: 1 ≤ n ≤ 9.

Think about it: place one queen per row. Track used columns and both diagonals (row − col and row + col are constant along them) in sets or boolean arrays, so each check is O(1).