箱入り娘（Klotski、L'Âne rouge、華容道）をブラウザに実装した。盤面ごとに「あと何手か」を3 通りの数え方で同時に表示する。有名な「81 手」はそのうちの 1 つにすぎず、同じ初期配置が「1 つの駒が角を曲がってどこまで動いても 1 手」なら 81、「一直線ならどこまで動いても 1 手」なら 90、「1 マス 1 手」なら 116 になる。Hordern の Sliding Block Puzzles（1986）の 3 列の値（Torsten Mütze の表経由）とすべて一致し、ペナント・パズルも 59 / 62 / 83 で一致した。日本語の資料にある「118 手」は、娘が盤から出る 2 マスまで数えた値。GitHub でよく読まれている Python ソルバー（aschmied/klotski-solver）の README は「最短 85 手」と出し、81 との差を手の数え方と初期配置の違いで説明している。実際にはこの初期配置（Pioneer 1）は 1 マス 1 手で 84 手で、プログラムは始点を含む盤面の列の長さを表示していた（「最長 125 手」も 124 手）。同じ README の 25,955・964・65,880 は完全に一致する。局面は 20 マスの形を 5 進数で読んだ 1 つの JS の number（5^20 < 2^53）にし、同じ 10 個の駒の棒 5 本を立てる・寝かせるの全 6 通り（363,480 配置）と、棒 4 本＋小駒 6 個の全 5 通り（566,272 配置）を全部並べた。「最も難しい初期配置」は全ゴールからの幅優先 1 回で決まり、m-kasahr さんが 5 時間・14 時間かけて求めた 138 手・75 手（角曲がり 1 手）を再現した（全部のチェックを含めて 11.9 秒）。「最も遠い 2 配置」（グラフの直径）は Takes & Kosters の離心率の上下界で求め、Mütze の 190 と 359 を再現した。古典配置の駒では、全頂点から BFS する 65,880 回（48.9 秒）が **184 回（0.2 秒）**になる。公表値 19 件すべて一致。テスト 14 件。ソルバー内蔵パズル第 76 弾。
デモ: https://sen.ltd/portfolio/klotski/
リポジトリ: https://github.com/sen-ltd/klotski
ルール
4 列 × 5 行の箱に、2×2 の「娘」、縦長 1×2 が 4 つ、横長 2×1 が 1 つ、1×1 が 4 つ入っていて、空きは 2 マス。駒を箱の中で滑らせて、娘を下辺中央の出口の上（下 2 行の中央 2 列）まで運ぶ。
B##C # = 娘 (2×2)
B##C B C D F = 縦長 (1×2)
DEEF E = 横長 (2×1)
DGHF G H I J = 1×1
I..J . = 空き
ページでは駒をクリックすると、その駒が行ける場所がすべて点線で出る（角を曲がる移動も含む）。どこかをクリックすると動く。右のパネルには、今の盤面から娘をゴールに運ぶまでの最短手数が 3 つの数え方で出ていて、1 手ごとに「今の手で何手縮んだか」が色付きで出る。Hint と Solve は、選んだ数え方での最短手を指す。
1 つのパズルに、3 つの答え
最短手数は「1 手」の定義で変わる。Mütze の用語に合わせて 3 つに名前を付ける。
| 数え方 | 1 手とは | 箱入り娘 | ペナント・パズル |
|---|---|---|---|
| finger | 1 つの駒を、角を曲がってでも行けるところまで動かす | 81 | 59 |
| straight | 1 つの駒を、一方向にどこまでも動かす | 90 | 62 |
| unit | 1 つの駒を 1 マス動かす | 116 | 83 |
Martin Gardner が 1964 年 2 月の Scientific American で示した 81 手は finger で数えた値。Hordern は 3 列とも載せていて、Mütze のページがそれを表にしている。ここで計算した値は 6 つとも一致した。ペナント・パズル（L. W. Hardy、1909 年、Hordern の C19）は娘を左下に運ぶ別の配置で、配置は Bosbury History Resource の図から起こした。
日本語版 Wikipedia などにある「118 手」は unit で数えて、娘が出口から出ていく 2 マス分を足したもの（116 + 2）。finger で数えると、最後の手はかならず娘の手なので、盤から出る動きはその手の続きになって 81 のまま変わらない。
3 つの数え方は包含関係にある（unit の 1 手は straight の 1 手で、straight の 1 手は finger の 1 手）。テストでは 5,000 局面についてこれを確かめ、3 つが実際に全部違う局面があることも確かめている。
局面を 1 つの number にする
同じ形の駒は区別しない。すると局面は「各マスを覆っている駒の形」の 20 文字で書ける。
これだけで局面は一意に決まる。縦長が同じ列に縦に連続していたら、上から 2 マスずつ区切るしかない。横長も同様で、2×2 は 1 個しかない。そこで 0（空き）〜 4（2×2）を 5 進数の各桁にすると、キーは 5^20 ≈ 9.5 × 10^13 未満で、2^53 に収まる。局面が JS の number 1 つになり、Map のキーにも Float64Array の要素にもそのまま使える。
export const EMPTY = 0;
export const SMALL = 1; // 1 x 1
export const TALL = 2; // 1 wide, 2 high
export const WIDE = 3; // 2 wide, 1 high
export const BIG = 4; // 2 x 2, the daughter / the red donkey
export function keyOf(grid: Uint8Array): number {
let k = 0;
for (let i = N - 1; i >= 0; i--) k = k * 5 + grid[i];
return k;
}
さらに「形 s の駒が左上 a にあるとキーにいくつ足されるか」を表 PK[s * N + a] にしておくと、駒を動かしたあとのキーは引き算と足し算 1 回ずつで出る。
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]);
3 つの数え方を 1 つの関数で
reach は、ある駒が 1 手で行ける位置を返す。finger では、その駒自身のマスを空きとみなして、左上の位置の上で幅優先探索をする。straight は 4 方向にそれぞれ伸ばし、unit は 1 マスで止める。
if (metric === 'finger') {
// breadth-first over anchors: every spot the block can slide to, around corners
const prev = new Map<number, number>([[from, -1]]);
const queue = [from];
for (let q = 0; q < queue.length; q++) {
const a = queue[q], r = (a / W) | 0, c = a % W;
for (let d = 0; d < 4; d++) {
const nr = r + DR[d], nc = c + DC[d], b = nr * W + nc;
if (!fits(nr, nc) || prev.has(b)) continue;
prev.set(b, a);
queue.push(b);
}
}
...
}
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;
}
}
経路（1 マスずつの位置の列）も返すので、ページのアニメーションは finger の 1 手を角を曲がりながら再生できる。
全配置を列挙する
「読み順で最初の空いているマスに、空きを置くか、どれかの駒の左上を置く」を再帰すると、全配置をちょうど 1 回ずつ列挙できる。
const go = (from: number) => {
let i = from;
while (i < N && grid[i] !== 255) i++;
if (i === N) {
keys.push(keyOf(grid));
return;
}
if (gaps > 0) {
gaps--; grid[i] = EMPTY; go(i + 1); grid[i] = 255; gaps++;
}
for (let shape = 1; shape <= 4; shape++) {
if (left[shape] === 0 || !free(shape, i)) continue;
left[shape]--; place(shape, i, shape); go(i + 1); place(shape, i, 255); left[shape]++;
}
};
箱入り娘の駒では 65,880 配置になる。キーをソートした Float64Array にしておけば、頂点番号は二分探索で引ける。あとは各配置から隣の配置を出して CSR 形式（オフセット配列＋隣接配列）のグラフにする。unit で 103,390 辺、finger で 114,958 辺。このグラフは 898 個の連結成分に分かれていて、初期配置を含む最大の成分が 25,955 配置。どちらも Mütze の値と一致する。
どの駒の動きも逆向きに戻せるので、グラフは無向になる。以降の問いはすべて、このグラフ上の幅優先探索で答えられる。
「85 手」の正体
"klotski solver" で検索すると上位に出る aschmied/klotski-solver（Python）の README は、実行結果をこう載せている。
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)
そして 81 との差を、Wikipedia は「同じ方向に 2 マス動かすのを 1 手と数えている」がこのプログラムは 2 手と数えるから、また初期配置も違うから、と説明している。
下の 3 つはここの値と完全に一致する。初期配置を含む成分が 25,955、そのうちゴール配置が 964、全配置が 65,880。つまりこのソルバーは、箱入り娘と同じ連結成分の中の別の配置（Pioneer 1）から探索している。
.##.
B##C
BDEC
FGHI
FJJI
Pioneer 1 の最短手数をここで計ると、finger 60・straight 66・unit 84。85 ではない。原因はソルバーの _analyze_solutions にある。
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)),
solutions の各要素は _solution_to_list が previous_board をたどって作った盤面のリストで、始点の盤面も入っている。長さは手数 + 1 になる。84 手が 85、ゴール配置のうち最も遠いもの（124 手）が「125 moves in longest solution」と表示される。ここの計算でも unit の最遠ゴールはちょうど 124 だった。
81 との差の説明も、半分は当たっていない。「同じ方向に 2 マス動かすのを 1 手」は straight の数え方で、箱入り娘でも 90 手になる。81 になるのは、角を曲がる動きも 1 手に数える finger だけ。
こういう食い違いは、数字を全部再現して初めて切り分けられる。964 と 25,955 が合っていたから、グラフ自体は正しく、ずれているのは表示だけだと言えた。
最も難しい初期配置
「娘をゴールに運ぶのに最も手数がかかる配置はどれか」。m-kasahr さんの Qiita 記事「もっとも気難しい箱入り娘は誰なのか」は、finger で数えて、棒 5 本の駒組で 138 手、棒 4 本＋小駒 6 個で 75 手を報告している。計算時間は Core i7-12700 で並列処理して 5 時間と 14 時間だった。
グラフが無向なら、これは幅優先 1 回で済む。全ゴール配置を同時に始点にして外側へ広げれば、各配置の距離はそのまま「そこから娘をゴールに運ぶ最短手数」になる。
export function hardest(g: Graph, goalAnchor: number): Hardest {
const n = g.keys.length;
const grid = new Uint8Array(N);
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]];
...
棒 5 本（娘 1・棒 5・小駒 4）で、棒を何本寝かせるかの 6 通りをすべて回した。
| 立て | 寝かせ | 配置 | 連結成分 | 最大成分 | 解ける配置 | 最難の初期配置 F / S / U | 直径 F / S / U | 直径の BFS 回数 (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 |
（F / S / U = finger / straight / unit。4 本立て 1 本寝かせが箱入り娘そのものの駒組）
finger の最大は棒 3 本立て・2 本寝かせの 138 手で、そうした配置は 6 つある。そのひとつがこれ。
ABCD
AE##
GE##
GHHI
JJ..
m-kasahr さんの記事は、娘が右 2 列にある配置を鏡像として除いて「娘が 2 行目の左」と書いている。これはこの配置の左右反転にあたる。棒 4 本＋小駒 6 個の 5 通りでは、最大は 3 本立て・1 本寝かせの 75 手で、娘が上段中央にある配置（これも記事と一致）。
| 立て | 寝かせ | 配置 | 連結成分 | 最大成分 | 解ける配置 | 最難の初期配置 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 |
記事は対象を「解ける配置が約 144,000（棒 5 本）、約 270,000（棒 4 本）」と書いている。同じ条件（ゴールに到達可能、娘が右 2 列にない、すでにゴールにあるものを除く）で数えると 144,309 と 271,395 で、どちらも記事の概数と整合する。
箱入り娘そのものの駒組では、最難の初期配置は finger 93 / straight 101 / unit 126。古典的な初期配置の 81 手より 12 手長い配置が、同じ駒で作れることになる。
.##B
C##B
DEEF
DG.F
HGIJ
最も遠い 2 配置: グラフの直径
Mütze のページは別の問いにも答えている。「最も遠い 2 配置の距離」、つまり構成グラフの直径で、箱入り娘の駒では unit で 190、同じ駒の向きを変えると「少なくとも 359 手必要なパズルが作れる」。
直径を素直に求めるなら、全頂点から BFS して離心率（その頂点から最も遠い頂点までの距離）の最大を取る。65,880 配置なら BFS も 65,880 回で、Node では 48.9 秒かかった。これも記録のために一度だけ実行して、結果が 190 になることを確かめてある。
Takes & Kosters（2011）の BoundingDiameters は、1 回の BFS で全頂点の離心率に上下界を付ける。頂点 v から BFS して離心率 e(v) と距離 d(v, w) が分かれば、三角不等式から
- 下界: e(w) ≥ max(d(v, w), e(v) − d(v, w))
- 上界: e(w) ≤ e(v) + d(v, w)
が出る。上界が今の直径の下界以下になった頂点はもう直径を更新できないので、候補から外す。BFS の始点は「上界が最大の頂点」と「下界が最小の頂点」を交互に選ぶ。
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);
}
連結成分は大きい順に処理して、成分の頂点数 − 1 がすでに見つけた直径以下なら残りを読み飛ばす。箱入り娘の駒では BFS 184 回・0.2 秒で 190 が出た。
ひとつ落とし穴があった。直径の下界 dl は「BFS の始点の離心率」だけでなく「他の頂点の離心率の下界」からも上がる。そのためループが dl == du で止まった時点で、値は正しいのに、その距離だけ離れた 2 配置の組を BFS でまだ一度も見ていないことがある。ページで「359 手離れた 2 配置」を遊べるようにするには組そのものが必要なので、最後に下界を与えた頂点からもう 1 回 BFS して組を拾う。
// A lower bound can reach the diameter before any sweep has seen a pair
// that far apart; one more sweep from the vertex that set it finds one.
if (dl > witnessed && dl > best) {
const seen = bfs(g, [argLo], dist, queue);
...
テストでは、棒 5 本全部寝かせた 14,220 配置について全頂点から BFS した値と一致すること、BFS 回数が頂点数の 1/50 未満であること、返した 2 配置の BFS 距離がちょうど直径になることを確かめている。
結果は上の表の「直径」列のとおり。unit の最大は 3 本寝かせの 359。Mütze の値と一致する。
##.B AABC
##CB DDEF
.DEE → GGE.
FDGG HI##
HIJJ H.##
この 2 配置は、finger で 268、straight で 290 離れていて、それぞれがその駒組の finger・straight の直径と同じ値になっている。つまりこの組は 3 つの数え方すべてで「最も遠い組」になっている。ページの「Farthest pair」は、右の配置（点線で表示）にぴったり一致させるパズルになっている。
**最難の初期配置と最遠の 2 配置は、別の駒組が勝つ。**ゴールまでの距離が最大になるのは 2 本寝かせ（unit 179）で、任意の 2 配置の距離が最大になるのは 3 本寝かせ（359）。最難の初期配置は「娘が出口にある配置の集合」のどれかまでの距離なので、ゴールが 1 つに決まっている直径とは別の量になる。
ページの実装
ページのソルバーは、全配置を並べる代わりに、今の配置の連結成分だけを unit の BFS で集める。その成分の中でゴールを始点に 3 つの数え方でそれぞれ幅優先を 1 回ずつ回して、距離の表を作る。どの手も成分の外には出ないので、この表はその後ずっと使える。距離の表示、Hint、Solve、最後の手が何手縮めたかの表示は、すべて表を引くだけになる。
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;
}
最短手が複数あるときは、他の 2 つの数え方でも近づく手を優先する。こうすると、finger で解いたペナント・パズルの 59 手が、unit で数えても最短の 83 マスになった。
成分の地図を作る時間は、手元の Chromium で箱入り娘（25,955 配置）が 0.2〜0.3 秒、プリセットの中で最も大きい成分（棒 4 本・3 本立て、136,040 配置）が約 1.2 秒だった。
プリセットは 7 つ。箱入り娘、ペナント・パズル、Pioneer 1、箱入り娘の駒での最難配置（93 手）、棒 5 本での最難配置（138 手）、棒 4 本での最難配置（75 手）、最遠の 2 配置（359 手）。最後の 4 つの配置は npm run stats が書き出した JSON から読んでいる。
まとめ
- 「何手」は数え方とセットで書く。 同じ箱入り娘が 81 / 90 / 116 / 118 になる。Hordern は 1986 年の時点で 3 列とも載せていた
- 公表値を全部再現すると、ずれの場所が分かる。 25,955・964・65,880 が合っていたから、「85 手」はグラフではなく表示（盤面の数 = 手数 + 1）の問題だと切り分けられた
- 局面はなるべく小さい値にする。 同じ形の駒を区別しなければ 20 マスの形の並びが一意で、5 進数なら number 1 つに収まる
- 無向グラフの「最難」は、ゴール全部から 1 回の幅優先。 5 時間・14 時間の探索が、全駒組・全チェック込みで 11.9 秒になった
- 直径は上下界で絞る。 全頂点 BFS の 65,880 回が 184 回になる。ただし最後に、直径に等しい距離の組を BFS で実際に確かめる
数値はすべて npm run stats が出力する src/stats.json から、ページの notes とこの記事に写している。公表値 19 件はスクリプトの中で照合していて、不一致は 0 件。テスト 14 件。ソルバー内蔵パズル第 76 弾。
参考文献:
- E. Hordern, Sliding Block Puzzles (Recreations in Mathematics 4), Oxford University Press (1986)
- M. Gardner, "Mathematical Games", Scientific American (1964年2月)
- T. Mütze, "Sliding block puzzles", https://tmuetze.de/puzzle.html （2026年9月27日参照）
- 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" / 「箱入り娘 (パズル)」（2026年9月27日参照）
デモ: https://sen.ltd/portfolio/klotski/
リポジトリ: https://github.com/sen-ltd/klotski