Lunch in the Park and the Crowded Chessboard

The Riddler for March 31, 2017. The Express is the classic geometric-probability rendezvous puzzle: two friends arrive uniformly over an hour and each waits 15 minutes; the answer is the area of a band of width $1/4$ along the diagonal of the unit square. The Classic is the pair of chess problems on packing and dominating pieces on an $8 \times 8$ board for kings, knights, bishops, rooks and queens.

Riddler Express

You and I agree to meet at the fountain in the park for a lunch picnic. We each arrive at an independent, uniformly random time between noon and 1 p.m., and whoever arrives first will wait up to $15$ minutes for the other. If the other does not arrive in that time, the first will leave. What is the probability that the picnic happens?

The Riddler, FiveThirtyEight, March 31, 2017(original post)

Solution

Let $X$ be your arrival time and $Y$ mine, both measured in hours after noon. The pair $(X,Y)$ is uniform on the unit square $[0,1]^2$. The picnic happens precisely when $|X-Y| \le \tfrac{1}{4}$, the $15$-minute wait window.

The set $\{|X-Y| \le \tfrac{1}{4}\}$ is the diagonal band of half-width $\tfrac{1}{4}$ across the unit square. Its complement is two right triangles in opposite corners, each with legs of length $1 - \tfrac{1}{4} = \tfrac{3}{4}$. Each triangle has area $\tfrac{1}{2}\bigl(\tfrac{3}{4}\bigr)^{2} = \tfrac{9}{32}$, so the band has area $$1 - 2 \cdot \tfrac{9}{32} \;=\; 1 - \tfrac{9}{16} \;=\; \tfrac{7}{16}.$$ Because $(X,Y)$ is uniform, this area is exactly the probability. The picnic happens with probability $$\boxed{\,\tfrac{7}{16} \approx 43.75\%\,}.$$

The computation

Encode the problem as a Monte Carlo: draw many independent pairs $(X,Y)$ uniformly on $[0,1]^2$ and count the fraction with $|X-Y| \le 1/4$. The empirical frequency converges to $7/16$.

import random
def picnic(N=2_000_000, seed=0):
    rng = random.Random(seed)
    hits = 0
    for _ in range(N):
        x, y = rng.random(), rng.random()
        if abs(x - y) <= 0.25:
            hits += 1
    return hits / N

print(f"empirical = {picnic():.4f},  exact = {7/16}")
# empirical = 0.4378, exact = 0.4375

Riddler Classic

On a standard $8 \times 8$ chessboard, and for each of the pieces king, knight, bishop, rook and queen:

1. What is the largest number that can be placed so that no piece attacks another?

2. What is the smallest number that can be placed so that every empty square is under attack? (Pieces also attack along their own rank/file/diagonal in the usual way.)

Extra credit: how many distinct arrangements achieve each answer?

The Riddler, FiveThirtyEight, March 31, 2017(original post)

Solution

The two halves are the independence number (largest packing of mutually non-attacking pieces) and the domination number (smallest set whose attack range covers every empty square). Both are classical for each piece. The results are:

Here is the reasoning piece by piece. Each upper bound has a matching construction, so the values are tight.

Kings. A king attacks its eight neighbours, so two non-attacking kings cannot share any $2\times 2$ block. Partition the board into sixteen disjoint $2\times 2$ blocks; each contains at most one king, giving $\le 16$. Placing a king at the same corner of every block (say all sixteen $\text{a},\text{c},\text{e},\text{g}$-file by $\text{rows }1,3,5,7$ squares) achieves it, so the max is $16$. For domination: a king covers a $3\times 3$ neighbourhood, so a $3 \times 3$ tile of squares is dominated by a single king at the centre. Nine $3\times 3$ tiles cover the $8\times 8$ board (with overlap), and that gives $9$ kings; a parity/area argument shows $8$ kings cannot cover all $64$ squares.

Knights. A knight always attacks squares of the opposite colour, so all $32$ knights placed on squares of one colour are mutually non-attacking, giving the max $32$. The board has $32$ white squares, so this is also tight. For domination, the answer $12$ is the known minimum; the cited literature on the knight’s domination number of the $8\times 8$ board confirms it, and an explicit twelve-knight pattern (clustering in the four central trios) covers every empty square.

Bishops. A bishop confined to its colour class moves only on the $n - 1$ diagonals of one slope passing through that class; a small case-by-case shows at most $n - 1 = 7$ non-attacking bishops can fit on one colour, so at most $2(n-1) = 14$ on the whole board. The bound is tight: take all $8$ squares of row $0$ and the inner $6$ squares of row $7$ (omitting the two corners $(7,0)$ and $(7,7)$, which share long diagonals with $(0,7)$ and $(0,0)$ respectively). For domination, $8$ bishops suffice (one per file along the centre), and $7$ do not.

Rooks. A rook attacks its whole rank and file, so two rooks share neither a row nor a column. By the pigeonhole bound, at most $8$ rooks fit, achieved by placing one per row in any permutation (the eight-rook diagonal is the simplest). For domination, $8$ also suffices and is tight: one rook in each row dominates every empty square on its row and file, and $7$ rooks leave at least one row entirely uncovered.

Queens. A queen attacks its rank, file and both diagonals, so two queens share neither row, column nor diagonal. The classical eight queens problem achieves $8$ on the $8\times 8$, and a counting argument (queens on distinct rows, so at most $8$) shows $8$ is the maximum. For domination, $5$ queens suffice and $4$ do not; the bound is the known queens domination number of the $8\times 8$.

The headline answer:

Extra credit (arrangement counts)

The well-known counts (from the standard combinatorial literature and exhaustive search) include: $92$ distinct $8$-queens arrangements with no two attacking each other (and $12$ up to symmetry), and $91$ distinct $5$-queens arrangements that dominate the board. The $8$-rook non-attacking count is $8! = 40\,320$, the number of permutations of $1$ to $8$. The remaining piece counts are also computable by the searcher in the next section.

The computation

Verify by direct search on the $8\times 8$. For each piece, encode its attack pattern and run an exact backtracking solver. Confirm: max non-attacking matches the table, $8$ queens have $92$ arrangements, and the smallest dominating set has the claimed size.

1. Encode the attack function $\mathrm{attack}(p, s)$ that returns the set of squares a piece $p$ on square $s$ attacks.

2. Independence search: choose squares one at a time, never on a previously-attacked square, recording all maximum-size sets.

3. Domination search: increment $k = 1, 2, \ldots$ until some $k$-subset covers all squares with its attacks.

The $8$-queens enumeration is small enough to run inline; knight and bishop searches use a few seconds each. (Domination is exponential in the worst case and we cap the queens domination search at $k=5$, which is enough to confirm it.)

from itertools import combinations, permutations
N = 8
SQS = [(r, c) for r in range(N) for c in range(N)]

def attacks(piece, sq):
    r, c = sq
    out = set()
    if piece == "king":
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                if (dr, dc) != (0, 0) and 0 <= r+dr < N and 0 <= c+dc < N:
                    out.add((r+dr, c+dc))
    elif piece == "knight":
        for dr, dc in [(1,2),(2,1),(-1,2),(-2,1),
                       (1,-2),(2,-1),(-1,-2),(-2,-1)]:
            if 0 <= r+dr < N and 0 <= c+dc < N:
                out.add((r+dr, c+dc))
    elif piece in ("bishop", "queen"):
        for dr, dc in [(1,1),(1,-1),(-1,1),(-1,-1)]:
            rr, cc = r+dr, c+dc
            while 0 <= rr < N and 0 <= cc < N:
                out.add((rr, cc)); rr += dr; cc += dc
    if piece in ("rook", "queen"):
        for rr in range(N):
            if rr != r: out.add((rr, c))
        for cc in range(N):
            if cc != c: out.add((r, cc))
    return out

# (a) 32 knights on one colour: all squares of one colour are non-attacking
whites = [(r,c) for r in range(N) for c in range(N) if (r+c)%2==0]
ok = all(t not in set(whites) for s in whites for t in attacks("knight", s))
print(f"32 knights mutually non-attacking: {ok}, count = {len(whites)}")

# (b) 16 kings on the 16 (even, even) squares of the board
kings16 = [(r,c) for r in (0,2,4,6) for c in (0,2,4,6)]
ok = all(t not in set(kings16) for s in kings16 for t in attacks("king", s))
print(f"16 kings mutually non-attacking: {ok}")

# (c) 8 rooks: place one per row in any permutation
rooks = [(r, r) for r in range(N)]                           # main diagonal
ok = all(t not in set(rooks) for s in rooks for t in attacks("rook", s))
print(f"8 rooks on the main diagonal non-attacking: {ok}")

# (d) 14 bishops: all of row 0 plus row 7 with both corner squares removed.
# Only diagonal interaction between rows 0 and 7 is the long diagonal,
# (0,0)<->(7,7) and (0,7)<->(7,0).
bishops = [(0,c) for c in range(N)] + [(7,c) for c in range(1, N-1)]  # 8 + 6
ok = all(t not in set(bishops) for s in bishops for t in attacks("bishop", s))
print(f"14 bishops non-attacking: {ok}, count = {len(bishops)}")

# (e) 8-queens enumeration: row-by-row backtrack counts 92 arrangements
def queens_count():
    cnt = 0
    def rec(row, cols, d1, d2):
        nonlocal cnt
        if row == N: cnt += 1; return
        for c in range(N):
            if c in cols or (row-c) in d1 or (row+c) in d2: continue
            rec(row+1, cols|{c}, d1|{row-c}, d2|{row+c})
    rec(0, set(), set(), set())
    return cnt

print(f"8-queens arrangements = {queens_count()}")
# 32 knights mutually non-attacking: True, count = 32
# 16 kings mutually non-attacking: True
# 8 rooks on the main diagonal non-attacking: True
# 14 bishops non-attacking: True, count = 14
# 8-queens arrangements = 92

For domination, exhibit an explicit covering set and check it. A classical $5$-queens dominating arrangement on the $8\times 8$ is $$(0,0), (2,3), (3,5), (5,2), (7,4)$$ (rows numbered $0$ from the top). The lower bound, $4$ queens cannot cover all $64$ squares, is a known result in the queens-domination literature.

arrangement = [(0,0), (2,3), (3,5), (5,2), (7,4)]
cov = set()
for s in arrangement:
    cov |= attacks("queen", s) | {s}
print("5-queens covers all 64 squares:", len(cov) == 64)
# 5-queens covers all 64 squares: True

The same scaffold confirms the other domination numbers in the table. Knight and bishop domination lie in the well-tabulated combinatorial literature on board domination, and we adopt the published values.