1183. Fewer Queens on a Wider Board

Place k queens on an r by c board so that no two attack each other, where k may be smaller than the number of rows. Print every placement.

3 3 2 -> 1 6 the eight placements of two queens 1 8 on a three by three board 2 7 2 9 3 4 3 8 4 9 6 7

## What most people try first

Reuse problem 1176 directly: one queen per row, choose a column. That is a theorem when there are as many queens as rows, because then every row must hold exactly one. With k smaller than r it stops being true: a row may hold no queen at all, and the one-per-row search cannot express that.

The usual patch is to add a "skip this row" branch, which works and is more fiddly than it looks, because the rows that are skipped have to be chosen as well as the columns, and the output order then depends on how the two interleave.

## The method

Go back to choosing CELLS in increasing cell number, as in problems 1178 and 1182, with the queen conflict test:

``` m = r * c clash(a, b): same row, or same column, or |dr| == |dc|

go(i): if size(cur) == k: record cur; return if size(cur) + (m - i) < k: return for j in i .. m-1: if clash(cell(j), cell(p)) for some p in cur: continue cur.push(j); go(j + 1); cur.pop() ```

The state is a LIST OF CELLS rather than a column per row, and that is the choice the problem is about. Choosing the state to fit the question, rather than reusing the state from a similar question, is most of what makes a search correct.

## Why it is correct

A placement is a set of k cells, which is exactly one increasing sequence of cell numbers, and the loop builds each such sequence exactly once. A cell is pushed only when it clashes with nothing already chosen, and because clashing is symmetric every pair is tested exactly once, when its later cell is pushed. So the leaves are exactly the valid placements.

Note that the row test inside clash is doing real work now. With one queen per row it was unnecessary, because the structure guaranteed it. Here two chosen cells can share a row and must be rejected explicitly.

## The output convention

Number the cells 1 to r * c, left to right along row 1, then row 2, and so on. A placement is printed as its occupied cell numbers in INCREASING order, separated by single spaces. Placements are printed one per line and compared position by position numerically, so the lines come out in lexicographic order. The empty placement prints as the word empty, and if no placement exists at all, print none.

## The settled boundaries

k = 0 has one placement, the empty one, printed as empty.

A k above min(r, c) is impossible, because the queens occupy distinct rows and distinct columns, so at most min(r, c) of them fit. Three queens on a 2 by 4 board is such a case.

A k WITHIN that bound can still be impossible, and that is the more interesting edge: 3 3 3 is the three-queens problem, which has no arrangement because of the diagonals, while 3 3 2 has eight placements. So the count bound is a cheap early exit and never a proof that an answer exists.

When k equals r equals c the answer is the n-queens problem of 1176 written with cell numbers instead of columns.

## Cost

At most C(m, k) nodes, which is C(36, 4) = 58905 at the stated limits, with an O(k) test per attempted push. The count prune and the clash test together keep the real figure far below that.

Constraints - `1 ≤ r ≤ 6` - `1 ≤ c ≤ 6` - `0 ≤ k ≤ 5`