1178. Kings That Do Not Touch
Place k kings on an r by c board so that no two are in touching cells. Two
cells touch when they differ by at most 1 in the row and at most 1 in the
column, so a king conflicts with up to eight neighbours. Print every placement.
3 3 4 -> 1 3 7 9
The only way to fit four kings on a three by three board is the four corners.
## What most people try first
Treat it like problem 1176 and put one king per row. That works for queens and
rooks because they attack along their whole row, so a row holds at most one. A
king only reaches one column either side, so a row can hold several kings, and
the row-by-row shape silently forbids most placements. On a 1 by 4 board the
answers include 1 3, 1 4 and 2 4, all of which put two kings in the same
row.
So the search has to choose CELLS, not one cell per row. That makes it a subset
problem: choose k of the r * c cells, which is the search of problem 1152
with a conflict test added.
## The method
Number the cells in row-major order and extend by cells of increasing number:
go(i):
if size(cur) == k: record cur; return
if size(cur) + (m - i) < k: return # not enough cells left
for j in i .. m-1:
if j touches any cell in cur: continue
cur.push(j); go(j + 1); cur.pop()
Two prunes, both familiar. The count test is the one from problem 1152. The conflict test is the push-time check from problem 1163, except that it compares against every chosen cell rather than only the last one, because touching is not a constraint between neighbours in the sequence.
## Why it is correct
Every placement is a set of k cells, which is exactly one increasing sequence
of cell numbers, and the search builds each such sequence once. A cell is pushed
only when it touches none of the cells already chosen, so a leaf has no touching
pair among the cells in the order they were added, which is the same as having
no touching pair at all, since touching is symmetric and every pair is tested
when its later cell is pushed.
That last clause explains why the test has to scan cur and not just look at
its last element: the cell numbered j may touch a cell chosen several steps
earlier, for instance cell 1 and cell 4 on a 3 by 3 board. Comparing only with
the previous choice would accept them.
## 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 exactly one placement, the empty one, printed as empty. A k
larger than the board can hold gives none, and so does k = 2 on a 2 by 2
board, where all four cells touch each other.
## Cost
The search visits at most C(m, k) nodes, which is C(16, 4) = 1820 at the
stated limits, and the conflict test costs O(k) per attempted push.
Constraints - `1 ≤ r ≤ 4` - `1 ≤ c ≤ 4` - `0 ≤ k ≤ 4`
Input
A single line containing three integers r, c and k.
Output
Print every placement on its own line, as the occupied cell numbers in increasing order separated by single spaces, the lines in lexicographic order. Print empty for the empty placement and none if no placement exists.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.