1180. The First Arrangement of the Queens

Place n queens on an n by n board so that no two attack each other, and print only the FIRST such arrangement in lexicographic order. If none exists, print none.

8 -> 1 5 8 6 3 7 2 4

## What most people try first

Produce every arrangement, as problem 1176 does, sort them, and print the first. That is correct and it is the wrong amount of work: at n = 12 there are 14200 arrangements and the answer is one of them.

Worse, it is correct only by accident at the small sizes. The whole point of asking for the first is that the search already produces them in order, so the first one it reaches IS the answer and everything after it is waste.

## The method

Run the search of problem 1176 and stop the moment a complete arrangement is found. Stopping means returning all the way out, not merely recording:

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

The second test, after the recursive call, is what actually stops the search. Without it the recursion unwinds one level, sees the answer flag, and returns, which is the same thing at every level, so it works too; what does NOT work is recording the answer and continuing, because the loop then keeps marking and unmarking its way through the rest of the tree for no reason.

## Why it is correct

The search tries the columns in increasing order at every row, so it visits the complete arrangements in lexicographic order of their column sequences. Hence the first complete arrangement it reaches is the lexicographically smallest one. The marks are maintained exactly, as in problem 1176, so every arrangement it reaches is valid and none is skipped.

## 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.

Here exactly one line is printed, so the ordering rule only decides WHICH line.

## The settled boundaries

n = 1 prints 1. n = 2 and n = 3 have no arrangement and print none. Every n of 4 or more has at least one, so none appears only at those two sizes.

## Cost

The search stops at the first solution, so for the sizes here it examines a few thousand partial arrangements at most: at n = 12 the first solution is reached without anything like the 14200 complete ones existing being enumerated. The worst case is still exponential in theory, which is why n is capped at 12 rather than left open.

Constraints - `1 ≤ n ≤ 12`