Klotski in three metrics: reproducing 81, 90, 116 and a GitHub solver's \"85 moves\", then mapping 929,752 block configurations in 12 seconds

I built Klotski (Hakoiri Musume, L'Âne rouge, Huarong Dao) in the browser, with every position showing its exact distance to the goal counted three ways at once. The famous "81 moves" is only one of those counts. The same start takes 81 moves if a block sliding anywhere it can reach — around corners — is one move, 90 if only straight slides count as one, and 116 if every one-cell step counts. Those are the three columns Edward Hordern gave in Sliding Block Puzzles (1986), as tabulated by Torsten Mütze. All three reproduce, and so do the Pennant Puzzle's 59 / 62 / 83.

Along the way I found where one popular solver's "85 moves" comes from. Its README puts the gap to 81 down to the metric and a different start. The start (Pioneer 1) takes 84 unit moves; the program prints the length of a list of boards that begins with the starting board. Its "125 moves in longest solution" is 124 for the same reason, and its other three numbers — 25,955, 964, 65,880 — match exactly.

Then I enumerated every configuration of the same ten blocks with the bars turned every possible way, 929,752 configurations across eleven block sets. A single multi-source breadth-first sweep per set reproduces the hardest starts that a published search took 5 and 14 hours to find (138 and 75 finger moves). Bounded-eccentricity sweeps reproduce Mütze's diameters (190 and 359 unit moves) in 184 sweeps instead of 65,880. 19 of 19 published values match; the whole table takes 11.9 s in one Node process.

• Demo: https://sen.ltd/portfolio/klotski/
• Source: https://github.com/sen-ltd/klotski

The rules

A 4×5 tray holds a 2×2 block, four standing 1×2 bars, one lying 2×1 bar and four 1×1 blocks, leaving two gaps. Slide blocks inside the tray until the 2×2 sits over the opening in the middle of the bottom edge.

 B##C      # = the 2x2
 B##C      B C D F = standing bars
 DEEF      E = the lying bar
 DGHF      G H I J = 1x1
 I..J      . = gap

On the page you click a block and every spot it can reach in one move is outlined, including spots around a corner. The side panel shows the optimal number of moves left in all three metrics, and how much your last move changed each. Hint and Solve play optimal moves in the metric you choose.

One puzzle, three answers

metric	one move is…	Klotski	Pennant
finger	one block sliding anywhere it can reach, around corners	81	59
straight	one block sliding any distance in one direction	90	62
unit	one block sliding one cell	116	83

Martin Gardner's 81 (Scientific American, February 1964) is a finger count. Japanese sources that say 118 use unit moves and add the two steps that take the 2×2 off the tray. In the finger metric that exit costs nothing extra: the last move of any optimal solution moves the 2×2, and sliding off the tray just continues it.

The metrics nest: every unit move is a straight move, and every straight move is a finger move. The tests check this on 5,000 positions and check that positions exist where all three move sets differ.

A position is one number

Blocks of the same shape are interchangeable, so a position is the shape covering each of the 20 cells. That grid is already unique. A run of standing-bar cells in a column can only be cut into pairs from the top, a run of lying-bar cells only from the left, and there is one 2×2. Read the grid as a base-5 numeral and the key is below 5^20 ≈ 9.5 × 10^13 < 2^53: a plain JS number, usable as a Map key or a Float64Array element.

export function keyOf(grid: Uint8Array): number {
  let k = 0;
  for (let i = N - 1; i >= 0; i--) k = k * 5 + grid[i];
  return k;
}

A table PK[shape * N + anchor] holds what a block of that shape at that anchor contributes to a key, so a move is one subtraction and one addition:

const base = key - PK[p.shape * N + from];
for (const to of reach(grid, p.shape, from, metric).keys()) out.push(base + PK[p.shape * N + to]);

Three metrics, one function

reach lists where one block can go in one move. For finger moves it runs a breadth-first search over the block's anchor positions, treating the block's own cells as empty. For straight moves it extends in each direction, and unit moves stop after one cell. It also returns the cell-by-cell path, so the page can animate a finger move around its corners.

for (let d = 0; d < 4; d++) {
  const path = [from];
  for (let k = 1; ; k++) {
    const nr = r0 + DR[d] * k, nc = c0 + DC[d] * k;
    if (!fits(nr, nc)) break;
    path.push(nr * W + nc);
    out.set(nr * W + nc, [...path]);
    if (metric === 'unit') break;
  }
}

Every configuration

Filling the first open cell in reading order with either a gap or the top-left corner of some block lists every configuration exactly once. Klotski's blocks give 65,880. Sorted keys in a Float64Array give vertex numbers by binary search, and the neighbours go into CSR arrays: 103,390 unit edges, 114,958 finger edges. The graph has 898 connected components, and the start's component, the largest, has 25,955 configurations. Both counts are Mütze's.

Every slide can be undone, so the graph is undirected, and everything below is breadth-first search on it.

Where "85 moves" comes from

aschmied/klotski-solver, a Python solver near the top of search results, prints:

  964 unique solutions
  85 moves in shortest solution
  125 moves in longest solution
  964 unique end states
  25955 board configurations examined
  65880 board configurations total (39925 unreachable)

The README explains the gap to 81 this way: Wikipedia "counts moving a piece by two squares in the same direction as a single move", this program counts it as two, and the starting configurations differ.

The last three numbers match exactly: 25,955 configurations in the start's component, 964 solved ones among them, 65,880 in all. So it searches the same component from a different start, Pioneer 1:

 .##.
 B##C
 BDEC
 FGHI
 FJJI

Pioneer 1 takes 60 finger, 66 straight and 84 unit moves — not 85. The reason is in its analysis step:

def _analyze_solutions(solutions, examined_configurations):
  return {
    'number_of_solutions': len(solutions),
    'length_of_shortest_solution': min(map(len, solutions)),
    'length_of_longest_solution': max(map(len, solutions)),

Each solution is a list of boards built by walking previous_board back to the start, so it includes the starting board and its length is moves + 1. 84 moves print as 85. The farthest solved configuration, at 124 unit moves (which I also measure), prints as "125 moves in longest solution".

The metric explanation is also only half right. Counting a two-square slide in one direction as one move is the straight metric, and that gives 90 for Klotski, not 81. The 81 needs moves around corners.

I could only pin this down because every other number matched: with 964 and 25,955 right, the graph was right and only the printout was off.

The hardest start

m-kasahr's Qiita article ("Which Hakoiri Musume is the most difficult?") searched for the start that needs the most finger moves. With five bars it found 138, and with four bars and six 1×1 blocks, 75. The runs took 5 and 14 hours with parallel processing on a Core i7-12700.

On an undirected graph this is one breadth-first sweep: start from every solved configuration at once, and each configuration's distance is its optimal solution length.

const goals: number[] = [];
for (let v = 0; v < n; v++) if (bigAt(gridOf(g.keys[v], grid), goalAnchor)) goals.push(v);
const dist = new Int32Array(n);
const order = bfs(g, goals, dist);
const depth = dist[order[order.length - 1]];

Here are Klotski's ten blocks with the five bars turned every way (F / S / U = finger / straight / unit):

standing	lying	configurations	components	largest	solvable	hardest start F / S / U	diameter F / S / U	sweeps (unit)
5	0	15,660	80	7,462	7,462	19 / 21 / 26	65 / 72 / 91	58
4	1	65,880	898	25,955	53,954	93 / 101 / 126	145 / 156 / 190	184
3	2	109,260	2,653	81,340	83,972	138 / 150 / 179	230 / 254 / 307	62
2	3	106,800	2,609	81,462	82,835	135 / 145 / 178	268 / 290 / 359	42
1	4	51,660	1,729	28,832	30,778	97 / 109 / 138	153 / 177 / 223	60
0	5	14,220	505	7,888	8,114	56 / 58 / 77	112 / 120 / 151	44

The finger maximum is 138, with three bars standing and two lying. Six configurations reach it; here is one:

 ABCD
 AE##
 GE##
 GHHI
 JJ..

m-kasahr drops layouts with the 2×2 in the right-hand columns as mirror images and reports the 2×2 "in the second row, on the left", which is this layout mirrored. With four bars and six 1×1 blocks the maximum is 75 (three standing, one lying), with the 2×2 at the top centre, which also matches.

standing	lying	configurations	components	largest	solvable	hardest start F / S / U
4	0	45,696	157	43,704	43,720	44 / 50 / 63
3	1	149,632	1,053	136,040	136,490	75 / 82 / 100
2	2	202,944	2,327	175,580	177,196	65 / 75 / 90
1	3	131,040	1,741	105,064	106,022	62 / 69 / 87
0	4	36,960	587	23,704	24,460	56 / 61 / 80

The article gives its search space as "about 144,000" and "about 270,000" solvable starts. Counting under the same conditions (solvable, 2×2 not in the right-hand columns, not already solved) gives 144,309 and 271,395.

With Klotski's own blocks, the hardest start needs 93 / 101 / 126 moves, 12 finger moves more than the classic start.

The farthest pair: the diameter

Mütze answers a different question: how far apart can two configurations be? That is the diameter of the configuration graph: 190 unit moves for Klotski's blocks, and "at least 359" with some blocks turned.

The direct way is a BFS from every vertex, keeping the largest eccentricity. For 65,880 configurations that is 65,880 sweeps and 48.9 s in Node; I ran it once, for the record, and it gives 190.

BoundingDiameters (Takes & Kosters, 2011) turns one sweep from v into bounds on every other vertex's eccentricity, by the triangle inequality: e(w) ≥ max(d(v,w), e(v) − d(v,w)) and e(w) ≤ e(v) + d(v,w). A vertex whose upper bound cannot beat the best lower bound drops out. Sweeps alternate between the largest upper bound and the smallest lower bound.

for (const w of cand) {
  const d = dist[w];
  lo[w] = Math.max(lo[w], d, ecc - d);
  hi[w] = Math.min(hi[w], ecc + d);
  if (lo[w] > dl) { dl = lo[w]; argLo = w; }
}
for (const w of cand) if (hi[w] > du) du = hi[w];
for (const w of cand) {
  if (lo[w] === hi[w]) continue;
  if (hi[w] <= dl && lo[w] >= (du + 1) >> 1) continue;
  if (hi[w] <= best) continue; // cannot beat what another component already has
  next.push(w);
}

Components go largest first and stop once a component has too few vertices to beat the best so far. Klotski's blocks take 184 sweeps, 0.2 s.

One trap: the lower bound dl can reach the diameter through a bound on some other vertex, before any sweep has actually seen a pair that far apart. The value is right, but the page needs the pair itself, so the code runs one more sweep from the vertex that set the bound. The tests compare against a sweep from every vertex on the 14,220-configuration set, check that fewer than 1/50 as many sweeps are used, and check that the returned pair really is that far apart.

The largest unit diameter is 359, with three bars lying, which is Mütze's number:

 ##.B          AABC
 ##CB          DDEF
 .DEE    ->    GGE.
 FDGG          HI##
 HIJJ          H.##

The same pair is 268 finger and 290 straight moves apart, which are that set's finger and straight diameters too. It is the farthest pair in all three metrics. The page's "Farthest pair" preset asks you to reach the dotted layout exactly.

The hardest start and the farthest pair are won by different block sets. Two bars lying gives the longest way home (179 unit), and three lying gives the farthest pair (359). The hardest start measures distance to the nearest of many solved configurations, while the diameter pairs two single configurations, so the two quantities need not peak together.

The page

The page's solver doesn't enumerate everything. It collects only the current configuration's component by a unit-move BFS, then runs one sweep per metric outward from the solved configurations in it. No move leaves the component, so these tables stay valid for the whole game. Distances, the per-move deltas, Hint and Solve are all lookups.

bestMove(key: number, metric: Metric): Move | null {
  const d = this.distance(key, metric);
  if (d <= 0) return null;
  let best: Move | null = null, bestScore = Infinity;
  for (const mv of moves(gridOf(key), metric, key)) {
    if (this.distance(mv.key, metric) !== d - 1) continue;
    let score = 0;
    for (const m of METRICS) score += this.distance(mv.key, m);
    if (score < bestScore) { best = mv; bestScore = score; }
  }
  return best;
}

Ties between optimal moves go to the one that also helps most in the other two metrics. With that rule, the finger solution of the Pennant Puzzle (59 moves) also takes the unit optimum, 83 cells. Mapping a component takes 0.2–0.3 s for Klotski (25,955 configurations) in Chromium on my machine, and about 1.2 s for the largest preset (136,040).

There are seven presets: Klotski, Pennant, Pioneer 1, the hardest start with Klotski's blocks (93), with five bars (138), with four bars (75), and the 359-move farthest pair. The last four come from the JSON written by npm run stats.

Takeaways

1. A move count needs its metric. One Klotski start is 81, 90, 116 or 118 moves; Hordern printed three of those columns in 1986.
2. Reproducing every published number locates a discrepancy. Because 25,955, 964 and 65,880 matched, "85" had to be the printout (boards = moves + 1), not the graph.
3. Keep the state small. With interchangeable blocks, the grid of shapes is unique, and in base 5 it fits in one JS number.
4. The hardest start on an undirected graph is one sweep from all goals. Hours of search became 11.9 s for every block set and every check.
5. Bound eccentricities for the diameter, 184 sweeps instead of 65,880, and then confirm a pair at that distance with a real sweep.

Every number here comes from src/stats.json, written by npm run stats, which checks the 19 published values itself (0 mismatches). The page's notes render from the same file. 14 tests.

References:

• E. Hordern, Sliding Block Puzzles (Recreations in Mathematics 4), Oxford University Press (1986)
• M. Gardner, "Mathematical Games", Scientific American (February 1964)
• T. Mütze, "Sliding block puzzles", https://tmuetze.de/puzzle.html (retrieved 27 September 2026)
• F. W. Takes, W. A. Kosters, "Determining the diameter of small world networks", CIKM '11 (2011)
• m-kasahr, "もっとも気難しい箱入り娘は誰なのか" (Qiita)
• A. Schmieder, aschmied/klotski-solver (GitHub)
• Wikipedia, "Klotski" (retrieved 27 September 2026)