1181. Completing an Arrangement Around One Queen
One queen is already standing on an n by n board, in row r and column c.
Print every arrangement of n non-attacking queens that keeps it there.
5 3 3 -> 2 5 3 1 4
4 1 3 5 2
Both arrangements have their third queen in column 3, which is where the fixed queen stands.
## What most people try first
Produce every arrangement with the search of problem 1176 and keep the ones
whose row r holds column c. That is correct and it does n times the work
it needs, because only about one arrangement in n has its row-r queen in any
given column.
## The method
The fixed queen does not need a filter, it needs a SMALLER LOOP. At row r
there is exactly one column to try:
go(row):
if row == n: record cur; return
lo, hi = 0, n-1
if row == r: lo = hi = c # the only choice in this row
for cc in lo .. hi:
if col[cc] or diagDown or diagUp is taken: continue
mark; cur.push(cc); go(row + 1); cur.pop(); unmark
Nothing else changes. The three conflict arrays, the push and the undo are exactly as in problem 1176.
## Why it is correct
The search builds the same arrangements as problem 1176 except that at row r
it offers only column c, so its leaves are exactly the valid arrangements whose
row-r queen is in column c, which is what was asked. Trying the columns in
increasing order at every other row keeps the output in lexicographic order.
A detail worth stating: the fixed queen is checked against the conflict arrays like any other, so if it is attacked by a queen already placed in an earlier row the branch dies there. It is not exempt from the rules, it is simply the only option in its row.
## 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.
## When the answer is empty
Fixing a queen can make the task impossible even when the board has
arrangements. A 4 by 4 board has two arrangements, 2 4 1 3 and 3 1 4 2, and
neither puts a queen in the corner, so fixing row 1 column 1 gives none.
That is the first sample, and it is the case a solution that assumes the filter
always leaves something gets wrong.
## Cost
Proportional to the arrangements found times O(n) to print, plus the pruned
branches. The fixed row cuts the search by roughly a factor of n compared with
generating everything and filtering.
Constraints - `1 ≤ n ≤ 8` - `1 ≤ r ≤ n` - `1 ≤ c ≤ n`
Input
A single line containing three integers n, r and c, the board size and the 1-based row and column of the fixed queen.
Output
Print every arrangement containing the fixed queen on its own line, as the 1-based column of the queen in each row from row 1 to row n, separated by single spaces, the lines in lexicographic order. Print none if no arrangement exists.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.