1182. Knights That Do Not Attack

Place k knights on an r by c board so that no two attack each other. A knight attacks the cells two away in one direction and one away in the other, so two cells conflict exactly when their row difference and column difference are 1 and 2 in some order. Print every placement.

2 2 4 -> 1 2 3 4

All four cells of a 2 by 2 board are mutually safe, because no two of them are a knight's move apart: the largest difference available is 1 in each direction.

## What most people try first

Any of the previous searches, unchanged. Each one carries an assumption that fails here.

One piece per row, as in problem 1176, is wrong because a knight does not attack along its row: the 2 by 2 board holds four knights.

Comparing only against the LAST chosen cell, as problem 1163 does, is wrong because the knight relation skips: in row-major numbering on a 3 by 3 board, cell 1 attacks cell 6 and cell 8, which are not its neighbours in number.

The third and most interesting assumption is the one from problem 1168 and 1154: that a failure at some point means failure for everything after it, so the loop can break. The knight relation is not monotone in cell number at all, since a cell may conflict with cell 6 and be fine with cell 7, so only continue is available.

## The method

``` m = r * c attacks(a, b): (|dr|, |dc|) is (1, 2) or (2, 1)

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

## 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 attacks nothing already placed. The relation is symmetric, so each pair is tested exactly once, when its later cell is pushed, and therefore a leaf has no attacking pair at all.

The count prune is sound because each step consumes at least one cell of the suffix, so no descendant can have more than size(cur) + (m - i) cells.

## 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. On a 1 by 4 board no two cells are a knight's move apart at all, since the row difference is always 0, so every pair of cells is a valid placement. And a k larger than the board holds gives none.

## Cost

At most C(m, k) nodes, which is C(16, 4) = 1820 at the stated limits, with an O(k) test per attempted push.

Constraints - `1 ≤ r ≤ 4` - `1 ≤ c ≤ 4` - `0 ≤ k ≤ 4`