Can You Hop Across The Chess Board?

Riddler Express

An $8\times 8$ board holds one chess piece per square. Starting on the white bishop (the green square), move from white piece to white piece according to each piece’s move (pawn: one step diagonally up; knight: an L; bishop: one diagonal step; rook: one orthogonal step; queen: one step any direction), never landing on a black piece other than a king. Reach a black king.

Solution

Make the board a directed graph: each square is a node, with an arrow to every square its piece can legally step to, but only if that destination is a white piece or a black king (so the walk never touches a forbidden black piece). The puzzle becomes a path-finding problem, and a shortest-path search from the green bishop reaches a black king in eight moves. Writing squares as (column, row) with row $0$ at the bottom, one such route is $$\boxed{\begin{aligned} &(4,1) \to (3,2) \to (2,3) \to (0,2) \to (1,3) \\ &\quad \to (2,5) \to (4,6) \to (5,7) \to (4,7), \end{aligned}}$$ that is bishop $\to$ pawn $\to$ knight $\to$ queen $\to$ knight $\to$ knight $\to$ pawn $\to$ rook $\to$ king, ending on the black king at $(4,7)$, as traced below.

The computation

Build the directed graph from the board, adding an edge only when the destination is white or a black king, then take the shortest path from the start to any king.

import networkx as nx
def moves(piece, i, j, n=8):
    M = {"p": [(i+1,j+1),(i-1,j+1)],
         "b": [(i+1,j+1),(i-1,j+1),(i-1,j-1),(i+1,j-1)],
         "r": [(i,j+1),(i-1,j),(i+1,j),(i,j-1)],
         "h": [(i-1,j+2),(i+1,j+2),(i-1,j-2),(i+1,j-2),
               (i-2,j-1),(i-2,j+1),(i+2,j-1),(i+2,j+1)],
         "q": [(i,j+1),(i-1,j),(i+1,j),(i,j-1),(i+1,j+1),
               (i-1,j+1),(i-1,j-1),(i+1,j-1)]}
    return [(a, b) for a, b in M[piece] if 0 <= a < n and 0 <= b < n]
def solve(board, start, kings):
    cell = {}
    for i, row in enumerate(reversed(board)):
        for j, pc in enumerate(row): cell[(j, i)] = pc
    G = nx.DiGraph()
    for (i, j), pc in cell.items():
        if pc[0] == "w":
            for m in moves(pc[1], i, j):
                if cell[m][0] == "w" or cell[m] == "bk": G.add_edge((i, j), m)
    reachable = [k for k in kings if k in G and nx.has_path(G, start, k)]
    return min((nx.shortest_path(G, start, k) for k in reachable), key=len)
board = [["bk","bb","wb","bb","bk","wr","wb","wr"],
         ["wh","wr","wh","wh","wp","wh","bk","wb"],
         ["wr","bp","wh","bh","wp","wr","wp","wr"],
         ["bp","bb","wp","wr","bh","wh","br","bh"],
         ["wh","wh","wh","wb","br","wb","wr","wb"],
         ["wq","wr","wh","wp","br","wh","wr","wq"],
         ["bb","br","wr","wp","wb","wp","wb","wq"],
         ["bk","wb","wq","wh","wp","wr","wh","wh"]]
print(solve(board, (4, 1), [(0,0),(0,7),(4,7),(6,6)]))

Riddler Classic

Climbing holds are dropped at uniformly random heights on a $10$-metre wall until there is no vertical gap larger than $1$ metre (counting the floor and the top). How many holds, on average? Extra credit: on a $10 \times 10$ wall where any two holds (or a hold and an edge) must be within $1$ metre to connect, how many until the bottom links to the top?

Solution

Both versions are settled by running the actual placement process: drop holds at random and stop the moment the wall becomes climbable. In one dimension a hold sits at a uniform height in $[0, 10]$, and we keep adding until every gap between neighbouring holds (and to the two ends) is at most $1$. Simulating many walls, the average count settles near $$\boxed{\approx 43 \text{ holds.}}$$ For the two-dimensional wall, two holds connect when they are within $1$ metre, the floor connects to any hold within $1$ metre of the bottom edge and likewise the top, and we stop once a connected chain of holds joins bottom to top. Tracking the growing clusters with a union-find structure, the average is far higher, $$\boxed{\approx 143 \text{ holds,}}$$ because a two-dimensional barrier is much harder to bridge than a single vertical line.

The computation

Simulate the placement directly. In one dimension, insert random heights until the largest gap drops to $1$; in two dimensions, union each new hold with every hold (and edge) within range and stop when bottom and top join.

import bisect, math
import numpy as np
from networkx.utils.union_find import UnionFind
rng = np.random.default_rng(0)
def climb_1d(H=10.0, d=1.0, runs=20_000):
    total = 0
    for _ in range(runs):
        pts = [0.0, H]
        while max(b - a for a, b in zip(pts, pts[1:])) > d:
            bisect.insort(pts, rng.uniform(0, H))
        total += len(pts) - 2
    return total / runs
def climb_2d(H=10.0, d=1.0, runs=400):
    total = 0
    for _ in range(runs):
        holds = {1: (0, 0), 2: (0, H)}; cnt = 2     # 1 = floor, 2 = top
        uf = UnionFind(); uf.union(1); uf.union(2)
        while uf[1] != uf[2]:
            cnt += 1; nh = (rng.uniform(0, H), rng.uniform(0, H))
            for i, h in holds.items():
                near = abs(h[1] - nh[1]) <= d if i in (1, 2) else math.dist(h, nh) <= d
                if near: uf.union(i, cnt)
            uf.union(cnt); holds[cnt] = nh
        total += cnt - 2
    return total / runs
print(climb_1d(), climb_2d())                  # ~43, ~143