1176. Every Way to Place the Queens

Place n queens on an n by n board so that no two attack each other. Two queens attack each other when they share a row, a column, or a diagonal. Print every arrangement.

4 -> 2 4 1 3 . Q . . . . Q . 3 1 4 2 . . . Q Q . . . Q . . . . . . Q . . Q . . Q . .

Problem 228 counts the arrangements. This prints them, which is the harder job, because a count can be accumulated while the arrangements themselves have to be produced one at a time.

## What most people try first

Choose n cells out of n * n and test every pair. At n = 8 that is C(64, 8), about 4.4 * 10^9 choices, to find 92 arrangements.

The first real idea removes almost all of that: no two queens share a row, so exactly one queen stands in each row. That turns the search into "which column in row 0, which in row 1, and so on", and the 64-choose-8 collapses to 8^8, which is 1.7 * 10^7. Adding "no two share a column" collapses it again to the permutations of the columns, 8! or 40320.

## The method

Walk the rows. For each row try every column, and keep three sets recording what is already taken:

go(r): if r == n: record cur; return for c in 0 .. n-1: if col[c] or diagDown[r + c] or diagUp[r - c + n]: continue mark all three; cur.push(c) go(r + 1) cur.pop(); unmark all three

The two diagonal indices are the whole trick. Cells on the same down-right diagonal share r + c; cells on the same up-right diagonal share r - c. Both are constant along their diagonal, so a diagonal conflict is one array lookup rather than a scan over the queens already placed. The + n shifts r - c, which ranges from -(n-1) to n-1, into a non-negative index.

## Why it is correct

An arrangement with no two queens in the same row is exactly a choice of one column per row, which is what the search builds. A column is offered only when it is unused and both of its diagonals are unused, and those three marks are maintained exactly: set at the push, cleared at the undo, so at any node they describe precisely the queens in cur and nothing else. So a leaf is reached exactly when the n chosen columns are pairwise non-attacking. Trying the columns in increasing order at every row makes the lines come out in lexicographic order with no sorting afterwards.

## The output convention

Exactly one piece stands in each row, so an arrangement is described by the COLUMN of the piece in row 1, then row 2, and so on, with single spaces between them and 1-based numbering. Arrangements are printed one per line and compared position by position numerically, so the lines come out in lexicographic order. If no arrangement exists, print none.

## The settled boundaries

n = 1 has one arrangement. n = 2 and n = 3 have none at all, so they print none. Those two are the only sizes above zero with no arrangement, and both are in the tests.

## Cost

The search visits far fewer than n! nodes because the diagonal marks prune early: at n = 8 it examines about two thousand partial arrangements to find 92. Printing is O(n) per arrangement.

Constraints - `1 ≤ n ≤ 8`