Chess Avoidance

The queens of an earlier chapter shared a single power and an unbroken board. Erich Friedman’s chess-avoidance puzzles loosen both. A whole army is to be placed, bishops and knights and the rest mixed together, on a board with squares cut out of it, and the one rule is that no piece may stand on a square another piece attacks. A bishop must not see a knight, a knight must not reach a bishop, and the holes in the board change every line of fire. The queens chapter asked how one kind of piece keeps clear of itself; this asks how five kinds keep clear of each other.

The puzzle

The board is the irregular shape of Figure 60.1: three rows and five columns, but the top row keeps only its middle two squares, the other three having been cut away, so twelve squares remain. On it we must place four bishops and two knights, no two pieces attacking each other. A bishop attacks along both diagonals to any distance, a knight to the eight squares a chess knight leaps to. Where can the six pieces stand?

The model

Give every square of the board a row and column, and let the holes simply be absent from the list of squares. For each square $c$ and each piece type $k$ (queen, bishop, knight, rook, king) introduce a binary $x_{c,k}=1$ when a piece of type $k$ stands on $c$, and let $a_c=\sum_k x_{c,k}$ record that $c$ is occupied. A square holds at most one piece, and the army has a fixed roster, $$a_c \le 1 \ \ (\text{each square } c), \qquad \sum_{c} x_{c,k} = n_k \ \ (\text{each type } k),$$ with $n_{\text{bishop}}=4$, $n_{\text{knight}}=2$ and the rest zero.

The whole puzzle is in the last rule, and it has one clean shape. For any square $p$, any type $k$, and any square $q$ that a type-$k$ piece standing on $p$ would attack, the two cannot both be in force, $$x_{p,k} + a_q \le 1 .$$ If a $k$-piece is on $p$ then $a_q=0$, so $q$ is empty; if $q$ is occupied then no $k$-piece sits on any square attacking it. One family of inequalities covers all five pieces, because only the relation $p$ attacks $q$ changes from piece to piece: a rook shares a rank or file, a bishop a diagonal, a queen either, a knight an $L$, a king a neighbouring square. The published model reaches the same end through auxiliary “is attacked by a queen” variables and a big constant; the pairwise form needs neither, and says exactly what the puzzle says.

The solver

from ortools.sat.python import cp_model

DIS = {(1, 1), (1, 4), (1, 5)}    # the three holes
CELLS = [(r, c) for r in range(1, 4)
         for c in range(1, 6) if (r, c) not in DIS]
TYPES = ["Q", "B", "N", "R", "K"]

def attacks(k, p, q):             # type-k piece on p hits q?
    if p == q:
        return False
    dr, dc = abs(p[0] - q[0]), abs(p[1] - q[1])
    if k == "B":
        return dr == dc
    if k == "N":
        return {dr, dc} == {1, 2}
    if k == "R":
        return dr == 0 or dc == 0
    if k == "Q":
        return dr == dc or dr == 0 or dc == 0
    return max(dr, dc) == 1        # king

def solve_avoid(army):
    m = cp_model.CpModel()
    x = {(c, k): m.NewBoolVar("")
         for c in CELLS for k in TYPES}
    occ = {}
    for c in CELLS:
        o = m.NewBoolVar("")
        m.Add(o == sum(x[c, k] for k in TYPES))
        m.Add(o <= 1)         # one piece per square
        occ[c] = o
    for k in TYPES:           # the army's roster
        need = army.get(k, 0)
        m.Add(sum(x[c, k] for c in CELLS) == need)
    # an attacker forces its targets empty
    for p in CELLS:
        for k in TYPES:
            for q in CELLS:
                if attacks(k, p, q):
                    m.Add(x[p, k] + occ[q] <= 1)
    s = cp_model.CpSolver()
    s.Solve(m)
    out = {}
    for c in CELLS:
        for k in TYPES:
            if s.Value(x[c, k]):
                out[c] = k
    return out

Asked for four bishops and two knights, the program returns the placement of Figure 60.1, and it is the only one: a bishop on the upper square and on the right of the middle row, and along the bottom a bishop, a knight, a bishop, a gap, a knight. No other arrangement of this army avoids every line of attack.

How full can the board be?

The single rule rewards counting how much the cramped board can hold. With only one kind of piece allowed, the most that fit without attacking are six bishops or six knights, four kings, and just three queens or three rooks. The puzzle’s army of six therefore sits at the ceiling for bishops and knights, and reaching that ceiling with exactly four bishops and two knights pins the answer to one board. Allow the full set of five piece types and the maximum creeps up only to seven, the holes and the pieces’ overlapping lines of attack keeping the board far emptier than its twelve squares suggest. The avoidance puzzle is the packing problem of the queens chapter turned loose on a ragged board and a mixed force, and the same instinct solves it: one binary per square and per piece, and a single inequality wherever one piece can see another.

Sources. The puzzle type is Erich Friedman’s, from his chess-avoidance collection; the integer-programming treatment, including the five-piece attack families and the worked four-bishops-and-two-knights board, follows Martin J. Chlond, Puzzle—Chess Avoidance Puzzles, INFORMS Transactions on Education volume $15$, number $3$ ($2015$), pages $254$–$256$. The pairwise “attacker implies target empty” constraint used here replaces the published model’s auxiliary attack variables and big constant. The reproduced solution, the uniqueness of that placement, the single-type maxima (six bishops, six knights, four kings, three queens, three rooks), and the seven-piece mixed maximum are checked by exhaustion over the board’s twelve squares.