Pawns, Knights, and Fairy Pieces

The Riddler for October 7, 2016, a pair of chessboard problems. The Express counts a pawn’s routes to promotion; the Classic hunts the longest non-self-intersecting paths of the knight and its exotic cousins.

Riddler Express

On a chessboard, under the standard rules, how many different paths can the king’s pawn (starting on e2) take to reach the far side at e8, where it promotes to a queen?

The Riddler, FiveThirtyEight, October 7, 2016(original post)

Solution

A pawn advancing up the board has three moves from a square: straight ahead, or one step diagonally to either side (a capture). So from e2 to e8 it climbs six ranks, and on each rank it may shift its file by $-1$, $0$, or $+1$, never stepping off the edge. The number of routes to a given square is just the number of routes to the three squares it could have come from, one rank below. That is Pascal’s triangle bent to fit an eight-file board.

Seed the start square e2 with a single route and build upward, summing three neighbours each time and dropping any that fall off the a- or h-file. The counts on each rank (files a to h) come out as $$\begin{array}{c|cccccccc} \text{rank} & a & b & c & d & e & f & g & h\\\hline 2 & 0&0&0&0&1&0&0&0\\ 3 & 0&0&0&1&1&1&0&0\\ 4 & 0&0&1&2&3&2&1&0\\ 5 & 0&1&3&6&7&6&3&1\\ 6 & 1&4&10&16&19&16&10&4\\ 7 & 5&15&30&45&51&45&30&14\\ 8 & 20&50&90&126&\mathbf{141}&126&89&44 \end{array}$$ Reading off the destination square e8 gives $$\boxed{141}$$ distinct paths. (The board’s edges matter: the count at h7 is $14$, not $15$, because one of its feeder squares sits off the board, which is also why e8’s two sides, $126$ and $126$, do not quite carry the symmetry further out.) If you also count the pawn’s opening two-square jump from e2 to e4 as a move distinct from two single steps, you add the $19$ routes that run from e4 onward, for $160$ in all.

The computation

Encode the climb as the three-way recurrence and read off e8. The same pass prints the triangle above.

# files a..h = 1..8; e = 5. Pawn climbs rank 2 -> rank 8, file shifts by -1/0/+1.
N = [[0]*9 for _ in range(9)]
N[2][5] = 1
for r in range(3, 9):
    for f in range(1, 9):
        N[r][f] = sum(N[r-1][g] for g in (f-1, f, f+1) if 1 <= g <= 8)
print("paths e2 -> e8:", N[8][5])
for r in range(2, 9):
    print("rank", r, [N[r][f] for f in range(1, 9)])
# paths e2 -> e8: 141

Riddler Classic

First, how long is the longest path a knight can travel on a standard $8\times 8$ board without the path crossing itself? Second, what are the longest non-crossing paths for three fairy chess pieces: the camel (which leaps like a knight but $3$ squares by $1$), the zebra ($3$ by $2$), and the giraffe ($4$ by $1$)?

The Riddler, FiveThirtyEight, October 7, 2016(original post)

Solution

A “path” here is a sequence of leaps, each landing on a fresh square, whose connecting segments (drawn as straight lines between consecutive squares) never touch one another except where two consecutive segments meet at their shared square. That self-avoidance is what makes the problem hard: a knight has up to eight moves from a square, and the count of legal continuations explodes, but each new segment is forbidden from clipping any earlier one. There is no neat formula; the honest method is a backtracking search that extends a path move by move, abandons it the moment a leap would cross the existing trail, and keeps the longest path it ever reaches.

The established maxima, confirmed by exhaustive computer search and recorded for the knight in the integer-sequence literature (this is the kind of problem Knuth treats in Selected Papers on Fun and Games), are $$\boxed{\text{knight } 35, \quad \text{camel } 17, \quad \text{zebra } 17, \quad \text{giraffe } 15}$$ moves. The pattern fits intuition: the knight’s short, dense leaps let it weave a long thread before boxing itself in, while the longer-striding fairy pieces leave the board faster and tangle sooner. The zebra ($3$ by $2$, the longest single leap) and the camel ($3$ by $1$) tie at $17$; the giraffe ($4$ by $1$), whose reach is longest of all in one direction, is most easily cornered and manages only $15$.

What a printed listing can settle by itself is the constructive half. For the three fairy pieces the randomized search below reaches the full maximum and we check it; a verified $17$-move camel path, given as the squares it visits with files and ranks numbered $0$ to $7$, is $$\begin{aligned} &(5,2)\,(2,1)\,(3,4)\,(0,3)\,(1,0)\,(4,1)\,(7,0)\,(6,3)\,(3,2)\\ &(4,5)\,(1,4)\,(0,7)\,(3,6)\,(6,7)\,(7,4)\,(4,3)\,(5,6)\,(2,5). \end{aligned}$$ The knight is the one piece a short run cannot finish off. The same search readily threads non-crossing knight paths of around thirty moves, and the listing exhibits and checks one of length $30$; squeezing out the last few moves to the proven maximum of $35$ is the work of the exhaustive computer searches behind the boxed figure. We take that $35$ from the established record rather than re-run a search of that scale here. Every path the listing prints is confirmed to be a legal, non-self-intersecting walk of its stated length.

The computation

Two pieces fit together. First a verifier: given a candidate path and a piece’s leap, it checks that every step is a legal move, every square is distinct, and no two non-consecutive segments meet (consecutive segments may meet only at their shared square). Second a searcher: a randomized backtracking walk that, for each piece, finds a path of the maximum length. The searcher readily reaches these lengths; proving no longer path exists is the exhaustive-search result cited above, far beyond a single listing for the knight.

import random
def leaps(a, b):                          # the (up to) 8 moves of an (a,b) leaper
    s = set()
    for dx, dy in ((a, b), (b, a)):
        for sx in (1, -1):
            for sy in (1, -1): s.add((sx*dx, sy*dy))
    return s
def cross(o,a,b): return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])
def on(o,a,b):
    return cross(a,b,o)==0 and min(a[0],b[0])<=o[0]<=max(a[0],b[0]) \
                           and min(a[1],b[1])<=o[1]<=max(a[1],b[1])
def meet(p1,p2,p3,p4):                    # do closed segments p1p2, p3p4 share a point?
    d1,d2 = cross(p3,p4,p1), cross(p3,p4,p2)
    d3,d4 = cross(p1,p2,p3), cross(p1,p2,p4)
    if (d1>0)!=(d2>0) and (d3>0)!=(d4>0) and d1 and d2 and d3 and d4: return True
    return any(d==0 and on(p,a,b) for d,p,a,b in
               [(d1,p1,p3,p4),(d2,p2,p3,p4),(d3,p3,p1,p2),(d4,p4,p1,p2)])

def verify(path, piece):
    M = leaps(*piece); segs = list(zip(path, path[1:]))
    assert len(set(path)) == len(path)                       # distinct squares
    assert all(0<=x<8 and 0<=y<8 for x,y in path)            # on the board
    assert all((q[0]-p[0], q[1]-p[1]) in M for p,q in segs)  # legal leaps
    for i in range(len(segs)):
        for j in range(i+1, len(segs)):
            if j == i+1:                                     # consecutive: share one vertex only
                (A,B),(C,D) = segs[i], segs[j]
                if meet(A,B,C,D) and (on(A,C,D) or (cross(A,B,D)==0 and cross(A,B,C)==0)):
                    return False
            elif meet(*segs[i], *segs[j]):
                return False
    return len(path) - 1                                     # number of moves

def longest(piece, target, seed=7, budget=4000):
    M = leaps(*piece); rng = random.Random(seed); best, bp = 0, None
    def good(segs, p, q):
        for k,(a,b) in enumerate(segs):
            if meet(a,b,p,q):
                if k < len(segs)-1: return False
                if on(a,p,q) or (cross(a,b,q)==0 and cross(a,b,p)==0): return False
        return True
    for _ in range(budget):
        if best >= target: break
        s = (rng.randrange(8), rng.randrange(8))
        path, segs, vis, cap = [s], [], {s}, [800000]
        def dfs():
            nonlocal best, bp
            if cap[0] <= 0: return
            cap[0] -= 1
            if len(path)-1 > best: best, bp = len(path)-1, list(path)
            if best >= target: return
            cur = path[-1]
            nxt = [(cur[0]+dx, cur[1]+dy) for dx,dy in M]
            cand = [q for q in nxt if 0<=q[0]<8 and 0<=q[1]<8 and q not in vis and good(segs,cur,q)]
            rng.shuffle(cand)
            cand.sort(key=lambda q: -(abs(q[0]-3.5)+abs(q[1]-3.5)))   # hug the edge
            for q in cand:
                vis.add(q); segs.append((cur,q)); path.append(q)
                dfs()
                path.pop(); segs.pop(); vis.discard(q)
                if best >= target or cap[0] <= 0: return
        dfs()
    return best, bp

# Exhibited paths: for the fairy pieces these are the searcher's full-length finds;
# for the knight it is a 30-move path (the established maximum, 35, needs exhaustive
# search beyond this listing). Each is verified to be a legal non-crossing walk.
records = {
 "camel  (3,1)": ((3,1), 17, [(5,2),(2,1),(3,4),(0,3),(1,0),(4,1),(7,0),(6,3),(3,2),
                              (4,5),(1,4),(0,7),(3,6),(6,7),(7,4),(4,3),(5,6),(2,5)]),
 "zebra  (3,2)": ((3,2), 17, [(2,3),(5,1),(3,4),(6,2),(4,5),(7,3),(5,0),(2,2),(0,5),
                              (3,7),(1,4),(4,2),(2,5),(5,3),(3,6),(6,4),(4,7),(7,5)]),
 "giraffe(4,1)": ((4,1), 15, [(7,3),(6,7),(5,3),(4,7),(0,6),(1,2),(2,6),(3,2),(4,6),
                              (5,2),(6,6),(7,2),(3,1),(2,5),(1,1),(5,0)]),
 "knight (1,2)": ((1,2), 35, [(4,4),(6,3),(7,1),(5,2),(6,0),(4,1),(5,3),(3,2),(4,0),
                              (2,1),(0,0),(1,2),(3,1),(2,3),(0,2),(1,4),(3,3),(2,5),
                              (0,4),(1,6),(3,7),(5,6),(7,7),(6,5),(7,3),(5,4),(6,6),
                              (4,5),(2,6),(3,4),(5,5)]),
}
for name,(piece,est_max,path) in records.items():
    moves = verify(path, piece)
    print(f"{name}: path verified, {moves} moves  (established max {est_max})")

# searcher demo: rediscover the fairy maxima from scratch
for piece,tag in [((4,1),"giraffe"),((3,2),"zebra"),((3,1),"camel")]:
    print(tag, "search reaches", longest(piece, {(4,1):15,(3,2):17,(3,1):17}[piece])[0])
# camel  (3,1): path verified, 17 moves  (established max 17)
# zebra  (3,2): path verified, 17 moves  (established max 17)
# giraffe(4,1): path verified, 15 moves  (established max 15)
# knight (1,2): path verified, 30 moves  (established max 35)
# giraffe search reaches 15
# zebra search reaches 17
# camel search reaches 17