No zebra tour on a 13 × 13 board

I looked into this problem as a result of Mathober 2026! This is for Day 2: Zebra Graph.

A zebra is a $(2,3)$ -leaper: it moves two squares in one direction and three in the perpendicular direction. An open tour visits every square once, with no requirement to return to its starting square (unlike a closed tour). In graph language, it is a Hamiltonian path in the graph whose vertices are squares and whose edges represent zebra moves. A graph that has a Hamiltonian path is called a traceable graph.

At the time of writing, all online sources I found claim that the $n \times n$ zebra graph is traceable for $n=1, 10, 14, 15, 16, 17, 18, 19$ , and $20$ , with the case $n=13$ still open.

Theorem. The zebra graph on the $13\times13$ board has no Hamiltonian path.

Proof. Label the columns A–M and the rows 1–13. Shade the squares whose column number plus row number is odd, taking A as column 1. There are 84 shaded squares and 85 unshaded squares, so the shaded squares are a minority. Note that every move changes color, as the zebra's 2-step will preserve the starting color, and the 3-step will flip it. To visit every one of the 169 squares, the zebra needs to make 168 moves, which is an even number of moves. Hence, it will start and end on the same color. So, if we take away the starting square, the remaining 168 squares are evenly split between the two colors, with 84 of each. This implies that its starting color is the majority color.

Thus both ends of a Hamiltonian path would be unshaded, and every shaded square would use two path edges.

First examine B1 and A2. Their complete neighbor sets are

N(\mathrm{B1})=\{\mathrm{D4},\mathrm{E3}\},\qquad N(\mathrm{A2})=\{\mathrm{D4},\mathrm{C5}\}.

Both squares are shaded, so all four edges are compulsory. Two of them meet at D4, which can accept no further path edge. Call a vertex filled when its two path edges have already been forced.

A 5 × 5 corner diagram with green edges connecting E3–B1–D4–A2–C5 and a ring marking D4. — Four compulsory edges form the path E3–B1–D4–A2–C5. The corner forces two edges at D4.

The same deduction at the other corners fills J4, D10 and J10. Now examine G2, B7, G12 and L7. Each is shaded and has exactly four neighbors:

Square	Neighbors already filled	Remaining neighbors
G2	D4, J4	E5, I5
B7	D4, D10	E5, E9
G12	D10, J10	E9, I9
L7	J4, J10	I5, I9

The two remaining edges at each square are therefore compulsory. But they form the cycle

\mathrm{G2}-\mathrm{E5}-\mathrm{B7}-\mathrm{E9}-\mathrm{G12} -\mathrm{I9}-\mathrm{L7}-\mathrm{I5}-\mathrm{G2}.

A 13 × 13 board showing green paths at all four corners, dashed excluded edges, and a red cycle through eight squares. — Four green corner paths exclude the dashed edges, forcing the red eight-square cycle.

Every vertex of this cycle already has its two path edges, so none can connect the cycle to the remaining squares. Hence the supposed open tour is impossible. $\square$

The method above is closely related to the 11 × 11 argument attributed to Dan Cass in Ed Pegg Jr.’s Leapers. For the general setting, see Donald Knuth’s Leaper Graphs. Awani Kumar also calls the 13 × 13 case open in The Chess Journalist 163 (October 2025), pp. 66–67, and gives a path through 168 squares, leaving the center square unvisited.

The funny part is, I started off with the goal to find the tour. I had a little interactive web app going to manually choose my next step, with lookaheads, symmetry-aware invalidation of bad moves, per-square reachability tests, and perhaps most importantly, identifying bridges (i.e., edges whose removal disconnects the graph). The above proof only came into being after I chose just the right paths for my solver to state that the initial board itself was unsolvable (!!), leading me to dig into the why of it. This is the simplest construction I found in which compulsory edges form a cycle that cannot connect to the rest of the path.