1179. Bishops With No Shared Diagonal
Place k bishops on an n by n board so that no two share a diagonal. A
bishop attacks along both diagonals for the whole length of the board, so two
bishops conflict exactly when the absolute difference of their rows equals the
absolute difference of their columns. Print every placement.
2 2 -> 1 2 . B B . . . . .
1 3 . B , B . , B B , B B
2 4
3 4
## What most people try first
Put one bishop per row, as in problem 1176. That is a theorem for queens and it
is false here for the same reason as in problem 1178: a bishop does not attack
along its row, so a row can hold several bishops. On a 2 by 2 board, cells
1 2 is a valid placement with both bishops in row 1.
So choose cells, in increasing cell number, and test the diagonal rule against everything already placed.
## The method and the invariant worth seeing
go(i):
if size(cur) == k: record cur; return
if size(cur) + (m - i) < k: return
for j in i .. m-1:
if |row(j) - row(p)| == |col(j) - col(p)| for some p in cur: continue
cur.push(j); go(j + 1); cur.pop()
The conflict test can be made a lookup rather than a scan, exactly as in problem
1176, by noticing that row + col is constant along one diagonal and
row - col is constant along the other. Keeping a used flag per value of each
turns O(k) per push into O(1), and it is the same observation that makes the
queens search fast. At k up to 4 the scan is fine; the invariant is the thing
to remember.
## Why it is correct
A placement is a set of k cells, which is exactly one increasing sequence of
cell numbers, built exactly once by the loop. A cell is pushed only when it
shares no diagonal with anything chosen, and because the relation is symmetric
every pair is tested exactly once, when its later cell is pushed. So a leaf is
a placement with no two bishops on a shared diagonal, and every such placement
is reached.
## 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. The most bishops
that fit on an n by n board is 2n - 2 for n at least 2, because there are
2n - 1 diagonals in each direction and the two corner diagonals of one
direction cannot both be used; so asking for more than that gives none. On a
2 by 2 board three bishops already give none, which matches 2n - 2 = 2.
## Cost
At most C(m, k) nodes, which is C(25, 4) = 12650 at the stated limits, with
an O(k) test per attempted push.
Constraints - `1 ≤ n ≤ 5` - `0 ≤ k ≤ 4`
Input
A single line containing two integers n 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.