0. 箱入り娘の大家族
スライディングパズルの古典「箱入り娘」をご存知でしょうか。4 × 5 マスの盤に詰め込まれた家族を一つひとつスライドさせて、真ん中の 2×2 の娘を箱の外へ脱出させるパズルです。日本では「箱入り娘」、中国では「華容道」、欧米では「Klotski」の名で知られていて、最短 81 手で解けることが有名です。
2025年、この「箱入り娘」を拡張した、その名も「箱入り娘の大家族」というパズルが一部界隈でバズりました。さわたく工房さんが、木材を加工したパズルを販売されていて、盤面は 6 × 5 マス、駒は 14 個。家族構成も賑やかで、娘・父・母に加えて、大番頭・手代・女中・番頭・祖父・祖母・番犬・兄嫁・丁稚 3 兄弟まで居ます。普通の箱入り娘よりはるかに窮屈そうです。
そんな大家族と日々向き合っていると、こんな疑問が頭をよぎります。
箱入り娘の大家族は、普通の家族よりもどれぐらい箱入りなのだろう？
直感的には「大家族のほうが断然キツそう」と思うわけですが、これを正面から評価します。忙しい方向けに結論を書いてしまうと、以下の通りです。
| パズル | 盤 | 駒数 | 最短手数 | 探索状態数 | 解探索時間 |
|---|---|---|---|---|---|
| 普通の箱入り娘 (古典) | 4×5 | 10 | 81 手 | 11,955 | 0.03 秒 |
| 箱入り娘の大家族 (拡張) | 6×5 | 15 | 38 手 | 26,220,903 | 70 秒 |
ここでの「1 手」は、1 つの駒を空きマスを伝って動かす一続きの動き（途中で何度向きを変えてもよい）を指します。探索しなければいけない状態数は圧倒的に大家族の方が多いのですが、意外にも手数的には大家族の方が半分以下に少ないという結果でした。興味があればこのオチに辿り着くまでの検討にお付き合いください。
本記事および本記事で紹介しているソースコードはAIによる支援を受けてかかれています
1. まずは Python で遊んでみる
ことの始まりは「最近、生成AIでバイブコーディングとか流行ってるけど、どんなもんなんだろう」と思ってclaude codeで遊び始めた時期と「箱入り娘の大家族」がバズっている事象のタイミングがかぶっていることでした。main.py、board.py、piece.py の3つを書いて、デスクトップアプリ版「箱入り娘の大家族」が動きました。駒をクリックするとハイライト、ドラッグで移動、娘が下まで降りたら「クリア！」のメッセージ。よくある、ほんわかしたパズルアプリです。
ところが自分で遊んでみると、これがなかなか難しい。「父」と「母」の間に挟まった「娘」を下に動かすには、まず手前の「大番頭」（4×1 の細長い駒）をどうにかしないといけない。大番頭を動かすには「祖父」と「祖母」と「女中」が邪魔。彼らをずらすには下段の「丁稚」と「番犬」を…と、一手指すたびにパズルが鈍重に絡まり合って、何手指しても娘は一向に降りてこないままです。
色々試行錯誤をして、100手ほどをかけて、無事クリアしました。そうすると、やはり純粋な興味が首をもたげてきます。「これ、最短手は何手なんだろうか？」ということでソルバーを書いてしまえばいい、と自然に発想しそのまま、Python で BFS（幅優先探索）を書いてみました。
BFS の発想自体は単純で、
- 初期盤面をキューに入れる。
- キューの先頭の盤面を取り出して、そこから合法手をすべて生成し、未探索の盤面をキューの末尾に加える。
- 取り出した盤面が「ゴール」（娘が出口に来た状態）なら、そこまでの手順を出力。
- 出ない限りキューが空になるまで繰り返す。
これだけ。BFS は枝の浅い方から見ていくので、もし解があれば最短手の解が必ず見つかる、教科書にも載っている基本のアルゴリズムです。
書きました。動かしました。全然返ってきません。数時間くらい放置してもキューが空にならない。理由は明らかで、
- 1 手ごとに盤面オブジェクトを丸ごとコピーしている
- 既訪問判定を Python の
setに「タプル化した盤面」を入れる方式でやっている - 駒の移動可能位置を生成するたびに辞書をひっくり返している
…の三重苦で、1 秒に数百〜数千状態しか進みません。一方、探索すべき状態数の規模は数千万〜数億のオーダー。
当時のclaude codeは「Cython で固めれば」「__slots__ を使えば」と数分で実行できるはずです！と粘っていましたが、全く見積もりの計算が合っていないので、バイブコーディングといってもこんな程度なんだな、と早々に諦めていました。
2. ブラウザでも試す（けど早々に断念）
せっかくなのでブラウザ版も作り、ブラウザ内で解ければ楽だよね、と考えました。
JavaScript で同じ BFS を書いてみます。
書き始めてすぐ気づきます。JS の Map も Set も、Python と五十歩百歩。盤面を Uint8Array にして展開してみても、requestAnimationFrame を挟んでも、メモリは食い荒らし、UI スレッドはブロックされ、ブラウザが「応答していません」のダイアログを出してきます。WebWorker に逃がせば UI は止められても、計算量自体は減りません。やっぱり厳しいのかも。
3. Go で書き直す
そこで Go に乗り換えました。Go は GC こそあるものの、[30]byte のような固定長配列を値として持ち回せるのが大きい。配列の値コピーはヒープを避け、CPU キャッシュに優しい。コンパイル後はネイティブコードで、Python の数百倍は速い。最初の Go 実装は素朴な BFS でした。盤面は 6×5=30 セルの固定長配列で表現し、駒は ID と幅・高さを持つ構造体。1 マスごとの移動を 1 手と数え、訪問済みは盤面のシリアライズ文字列で map[string]struct{} に突っ込む方式です。
これでもブラウザ JS よりはだいぶ速く、しかしまだ重い。そこで 今までsonnetで頑張っていたのですが、opusに聞いてみることにしました。opusは、データの持ち方が良くないから、Zobrist Hashingを使えば？と提案してきました。
Zobrist Hashing は、本来チェスや囲碁の盤面ハッシュとして使われる手法で、考え方はシンプルです:
- 「セル位置」×「駒の種類」の組ごとに、初期化時に決定的乱数で 64bit 値を割り当てる（テーブルを作る）。
- 盤面のハッシュ値は、その盤面に置かれている全ての（位置, 駒種）について、テーブルから引いた 64bit 値を XOR し合わせたもの。
// pkg/board/hash.go
func (zh *ZobristHasher) Hash(b *Board) uint64 {
var h uint64
for i, cell := range b.Grid {
if cell != 0 {
pt := zh.pieceTypeByID[cell]
h ^= globalZobristTable[i][pt]
}
}
return h
}
ここで重要なのが「駒の種類 (PieceType)」でテーブルを引いていること。駒の ID（個別の識別子）ではなく形状で同一視しています。
6×5 の盤面には 2×1 横長の駒が「番頭・女中・祖父・祖母」と 4 個ありますが、これらはどれも PieceTypeFamily という同じタイプで XOR されます。XOR は可換なので、4 個が入れ替わっただけの盤面は自動的に同じハッシュになります。BFS が「重複しているが微妙に違う盤面」を別物として展開してしまうのを防いでくれる、地味に効く工夫です。
さらに XOR の性質を利用すると、「ハッシュ値の更新」が駒のサイズ分の XOR で済むのも嬉しいところです。
// pkg/board/hash.go ― 駒1個分の差分でハッシュを更新
func (zh *ZobristHasher) IncrementalHash(oldHash uint64, piece *Piece, fromX, fromY, toX, toY int) uint64 {
pt := byte(piece.Type) + 1
h := oldHash
// 旧位置を XOR で打ち消す
for row := 0; row < piece.Height; row++ {
for col := 0; col < piece.Width; col++ {
h ^= globalZobristTable[(fromY+row)*BoardWidth+(fromX+col)][pt]
}
}
// 新位置を XOR で入れる
for row := 0; row < piece.Height; row++ {
for col := 0; col < piece.Width; col++ {
h ^= globalZobristTable[(toY+row)*BoardWidth+(toX+col)][pt]
}
}
return h
}
1 手指すごとに 30 セル全部を読み直してハッシュを取る、なんてことをやらずに済みます。BFS が回す状態の大半は「1 手分の小さな差分」なので、この差分更新はとてもよく効きます。この Zobrist 入り BFS で、初めて「箱入り娘の大家族」の最短解が見えました。75 手。
ここで一旦、ホッとひと安心。「解ける」ことが分かっただけでも、ずっと抱えていたモヤモヤが晴れます。
4. ルールを書き直す ― スライドを 1 手と数える
最初のソルバーは「駒を 1 マス動かすごとに 1 手」と数えていました。だが実際にゲームを遊んでみると、人間は「父を 3 マス下にスライドさせる」のを 1 手と感じるものです。盤面に空きが空いていれば、その空きを通って好きなだけスライドできるのが、このパズルの自然な手触りです。
そこで移動の定義を書き直しました。同じ方向への連続したスライドを 1 手 と数える。pkg/board/moves.go で言うと、こうなります:
// pkg/board/moves.go (抜粋)
for dir := DirUp; dir <= DirRight; dir++ {
delta := DirectionDelta[dir]
dx, dy := delta[0], delta[1]
for dist := 1; dist <= maxSlideDistance(dir); dist++ {
nx, ny := pos.X+dx*dist, pos.Y+dy*dist
if nx < 0 || ny < 0 || nx+piece.Width > BoardWidth || ny+piece.Height > BoardHeight {
break
}
if !checkLeadingEdge(b, piece.ID, piece.Width, piece.Height, pos.X, pos.Y, dir, dist) {
break
}
buf.Moves = append(buf.Moves, Move{ PieceID: piece.ID, FromX: pos.X, FromY: pos.Y, ToX: nx, ToY: ny, Direction: dir })
}
}
1 マス移動だけだった生成ループが、各方向について「1 マス、2 マス、3 マス…」と先頭辺の衝突がなくなる距離まで生成するようになっただけです。が、これだけで結果は劇的に変わります。75 手 → 49 手 に短縮された。
スライド可は「1 マス移動」を厳密に内包する（distance=1 のスライドが 1 マス移動と等価）ので、最短手数は必ず元以下になります。49 手は最短保証つきの数字です。
さらに一段 ― 曲がってもいい連続移動
ここまでで「同じ方向への連続スライド」を 1 手としました。しかし指の動きを思い返すと、もう一歩ある。空きが L 字に空いていれば、手代を「右に 2、そこから下に 1」とひと続きの手つきで滑り込ませる。指は途中で一度も止めていない。これも 1 手と感じるはずです。
そこで定義をもう一段広げます。1 つの駒が空きマスを伝って到達できる位置への移動は、途中で何度向きを変えても 1 手と数える。実装は「その駒を空き領域の中で 1 マスずつ動かす flood fill（幅優先の塗りつぶし）」になる。到達できた左上位置を、それぞれ 1 手として列挙するだけだ。自分が今いるマスは「動けば空く」ので、通過可能として扱う、というものです。
// pkg/board/moves.go ― 駒1個の到達可能位置を flood fill で列挙
func reachableMoves(b *Board, piece *Piece, start Position, emit func(Move)) {
var visited [BoardSize]bool
var queue [BoardSize]Position
head, tail := 0, 0
visited[start.Y*BoardWidth+start.X] = true
queue[tail] = start
tail++
for head < tail {
cur := queue[head]
head++
for dir := DirUp; dir <= DirRight; dir++ {
d := DirectionDelta[dir]
nx, ny := cur.X+d[0], cur.Y+d[1]
if nx < 0 || ny < 0 || nx+piece.Width > BoardWidth || ny+piece.Height > BoardHeight {
continue
}
idx := ny*BoardWidth + nx
if visited[idx] || !footprintClear(b, piece.ID, piece.Width, piece.Height, nx, ny) {
continue
}
visited[idx] = true
queue[tail] = Position{X: nx, Y: ny}
tail++
emit(Move{PieceID: piece.ID, FromX: start.X, FromY: start.Y, ToX: nx, ToY: ny})
}
}
}
同方向スライドは「曲がらない連続移動」の特別な場合なので、この新ルールは前のルールを厳密に内包します。最短手数はまた必ず元以下になります。49 手 → 38 手。
そしてこのルールにおいて古典「箱入り娘」のほうは 90 手 → 81 手。これは冒頭に挙げた「最短 81 手で解けることが有名」のあの 81 手とぴったり一致します。世間で言う箱入り娘の 81 手は、まさにこの「曲がってもいい連続移動を 1 手と数える」流儀での数字だったわけですね。
しかし、手数が減ったから簡単になったというわけではありません。1 つの状態から生成される合法手が増えるので、1 状態あたりの計算量は増加します。拡張版を解く時間は、訪問する状態数自体は減って 26.2M なのに、45 秒 → 70 秒 と少し延びています。以降のソルバーは、すべてこの「曲がってもいい連続移動」を 1 手として動いています。
5. ソルバーを 4 倍速くする
ここで時計を少し巻き戻す。以下の高速化は、まだ「同方向スライドを 1 手」とする 49 手の段階で入れたものです（連続移動ルールにしても効きどころは変わらない）。当時、最初の Go 実装で 49 手を出すには 3 分以上 かかっていました。環境は手元の M1 Mac。
| 計測 | 高速化前 (0b3f568) | 高速化後 (スライドルール時点) | 比 |
|---|---|---|---|
| 探索時間 | 3 分 21 秒 | 45.4 秒 | 4.5× |
| 探索状態数 | 55,884,531 | 28,489,831 | 0.51× |
| 状態/秒 | 277K | 628K | 2.3× |
入れた最適化は 4 つ。順番に書きます。
5.1 対称性正規化
このパズルの初期配置は左右対称です。であれば、探索中に出会う盤面の半分は「左右を入れ替えれば既出」になっているはずで、状態空間の半分が無駄になっているのでこれを削減します。やり方は簡単で状態を作るたびに、その盤面の 左右反転版のハッシュ も同時に計算します。そして両者のうち小さいほうのハッシュを「正規形（canonical）」として扱い、訪問済みかどうかはこの正規形でだけ判定します。
駒 ID は 1〜14 と小さい。なら固定長配列で十分です。map を [15]Position の固定配列に置き換えます。これだけでアロケーションが消え、map の内部ハッシュ計算もなくなりBFS の内側ループは秒間 277K → 628K まで、約 2.3 倍に伸びました。
5.3 カスタム HashSet ― Go の map に勝つ
訪問済み集合 visited は当初 map[uint64]struct{} でした。Go の map は汎用に強いが、uint64 → struct{} の用途にはバケット、ポインタ、空きスロット、メモリアロケータなどの1 エントリあたり 50 バイト以上のオーバーヘッドがありこれが 28M エントリ並ぶと、それだけで GB オーダーのメモリを消費してしまいます。そこでシンプルなオープンアドレス法ハッシュセットを利用しています。
// pkg/solver/hashset.go (抜粋)
type HashSet struct {
slots []uint64
mask uint64
size int
hasZero bool
}
func (s *HashSet) Add(h uint64) bool {
if h == 0 {
if s.hasZero { return false }
s.hasZero = true; s.size++
return true
}
idx := h & s.mask
for {
slot := s.slots[idx]
if slot == 0 {
s.slots[idx] = h; s.size++
if s.size*10 > len(s.slots)*7 { s.resize() }
return true
}
if slot == h { return false }
idx = (idx + 1) & s.mask
}
}
Zobrist ハッシュは一様分布なので、衝突確率を 64bit 全空間で評価できる。スロットが 0 のときに「空」を意味させ、リテラル 0 のキーだけは hasZero フラグで別管理する。これで 1 エントリ約 16 バイト、Go の map の 1/3 未満のメモリで同じ働きを期待できます。
5.4 状態のスリム化 ― packed board
BFS が回している bfsState 構造体は、以下の情報を保持しています。
- 盤面 (
[30]CellType) - 通常ハッシュ (
uint64) - ミラーハッシュ (
uint64) - 親状態のインデックス (
int32) - 直前の手 (
board.Move)
このうち盤面が支配的で、CellType は 1 バイトだから 30 バイト。駒 ID は最大 14 なので 4 ビットあれば足りる。nibble 単位で詰め直すと 15 バイト に縮む。アライメントの都合で 16 バイトの配列に格納します。
// pkg/solver/packed.go (抜粋)
type packedBoard [16]byte
func packBoard(b *board.Board) packedBoard {
var p packedBoard
for i := 0; i < board.BoardSize; i += 2 {
p[i>>1] = byte(b.Grid[i]) | (byte(b.Grid[i+1]) << 4)
}
return p
}
Move も int フィールド 5 つから int8 フィールド 5 つの packedMove に詰め直しています。座標は 0〜5 しか取らないので 1 バイトで十分。
type packedMove struct {
PieceID byte
FromX, FromY, ToX, ToY, Dir int8
}
結果として bfsState は 約 48 バイト になりました。最初の素朴な実装では []board.Move の slice ヘッダや Move 配列でゆうに 100 バイト以上だったので、半分以下です。状態数 28M で見たメモリ使用量は、これだけで 2 GB は浮く計算になります。
以下のコミットで4倍ほど高速化されたことになります。
BFS高速化: ミラー対称性正規化、移動生成のmap撤廃、カスタムhash set、状態スリム化
6. ゴール側からの事前計算
ここまでで「1分以内で解ける」ところまでは来た。だが、ブラウザに移植するなら、せっかくならもっと体感速度を上げたい。ということでそこでもう一段、踏み込んでみることにしました。
任意の状態から問題を解けるソルバーですが、実はゴールの状態はある程度決まっています。つまり、BFS の逆で**「ゴールの近くの盤面と、そこまでの残り手数」を、あらかじめ全部知っておけばいい。** これは双方向探索（Bidirectional Search）の発想を、片方だけ「事前にやっておく」形で実体化したものです。
具体的な流れは:
- 通常の前向き BFS で初期盤面から G_final（最短解の終端）を 1 つ求める。
- G_final から出発して、26 手分 の単源 BFS を回し、到達したすべての盤面の正規ハッシュと「G_final までの距離」を記録する。
- このテーブルをファイルに書き出す（生で約 8 MB、gzip で約 7.2 MB）。
- 探索時には、いま見ている盤面のハッシュをテーブルで lookup する。当たれば「ここからゴールまであと N 手」と即答できる。
実装は cmd/precompute/main.go と pkg/solver/precompute.go にある。テーブル形式は (uint64 hash, uint8 distance) の 9 バイト/件で、ハッシュでソートしてバイナリサーチできるようにしてあります。
なぜ深さを 26 に切ったのか、というとこれはブラウザ上で動かすときの現実的な制約として考えたものです。1 段深くするたびに到達状態数は 1.4 倍ほどに増えていく中でweb/precomputed/ に置く前提だと、配信サイズを無尽蔵にするのは現実的ではなく、10 MB 程度と設定して、26 段約 90 万件・gzip 7.2 MBを決めています。
7. ブラウザに戻る ― JS への移植
Go で書いたソルバーをそのままブラウザでも動かせるようにしたい。クライアントサイド完結にしておけば、サーバーは要らない、API キーも要らない、リクエストレートも気にしなくていい。移植のキモは「Go と JS でハッシュが完全に一致すること」だ。一致しなければ、Go で作ったテーブルを JS から引けない。Zobrist テーブルは固定 seed (0x48414B4F = "HAKO" のバイト列) の math/rand から生成している。Go の math/rand は仕様としてアルゴリズムが固定されているから、再現性がある。とはいえ JS で math/rand の実装を再現するのは面倒なので、テーブルそのものをバイナリで書き出して JS にロードさせました。
// pkg/board/hash.go
func ZobristTableBytes() []byte {
buf := make([]byte, BoardSize*(NumPieceTypes+1)*8)
off := 0
for i := 0; i < BoardSize; i++ {
for j := 0; j <= NumPieceTypes; j++ {
binary.LittleEndian.PutUint64(buf[off:], globalZobristTable[i][j])
off += 8
}
}
return buf
}
6×5 盤・5 種の駒タイプで 30 * 6 * 8 = 1440 バイト。これと先ほどの距離テーブル goal_distances.bin (約 8 MB) を web/precomputed/ に置いておけば、JS は同じ計算ができます。
JS 側 (web/solver.js) は Uint8Array で読み込んで DataView で 64bit 値を引く。64bit は JS のネイティブ数値型では扱えないので、上位 32bit と下位 32bit に分けて XOR する小細工が要るのですがpacked[i >> 1] から nibble を取り出す関数も、Go の packBoard と対称な見た目になっています。
ブラウザ側でやっていることは、Go 版とほぼ同型の BFS 。ただし、
- 訪問済み集合は Go と同じくオープンアドレス法の自作 (
U64HashSet)。 - 探索の途中で
await new Promise(r => setTimeout(r, 0))を挟むことで、メインスレッドを完全には占有せず、ユーザーが「キャンセル」ボタンを押せる猶予を作る。 - 距離テーブルにヒットしたら、その時点で残り手数が確定するので、そこから先は完全に展開を打ち切る。
これで、最初は「ブラウザが固まる」と諦めた問題に、もう一度同じブラウザで挑戦して実行することができました。アルゴリズム（人類の叡智）の勝利です。
プレイページのリンク（再）
画面右側の「最短手探索」ボタンを押せば、数秒で 38 手解が手順リスト付きで表示されます。
8. 古典「箱入り娘」と比べる
ここまでが「6×5 の大家族」での話。最後に、冒頭の問いに戻ります。
箱入り娘の大家族は、普通の家族よりもどれぐらい箱入りなのか？
これに数字で答えたい。同じソルバーで、普通の箱入り娘 (4×5, 10 駒) も解いてみることにします。
実装は pkg/board/config_extended.go と pkg/board/config_classic.go を build tag で切り替える形にしました。デフォルトビルドが従来の大家族版、-tags classic でビルドすると古典版になります。
//go:build classic
package board
const (
BoardWidth = 4
BoardHeight = 5
BoardSize = BoardWidth * BoardHeight
GoalDaughterX = 1
GoalDaughterY = 3
PuzzleName = "箱入り娘 (4×5, 10駒・古典)"
)
これで Board.Grid の大きさや IsGoal の判定座標が自動的に切り替わります。Zobrist テーブルも BoardSize 依存だから、勝手に正しいサイズで初期化されて同じ BFS ロジックをそのまま流せます。
go build -tags classic -o solver-classic ./cmd/solver
./solver-classic
走らせた結果がこちら。
=== Hakoiri Musume Golang ソルバー ===
パズル: 箱入り娘 (4×5, 10駒・古典)
アルゴリズム: bfs
...
=== 解発見！ ===
手数: 81
探索状態数: 11955
経過時間: 30ms
並べて見比べると、。
| パズル | 盤 | 駒数 | 最短手数 | 探索状態数 | 解探索時間 |
|---|---|---|---|---|---|
| 普通の箱入り娘 (古典) | 4×5 | 10 | 81 手 | 11,955 | 0.03 秒 |
| 箱入り娘の大家族 (拡張) | 6×5 | 15 | 38 手 | 26,220,903 | 70 秒 |
ここで気づくのは 2 つ。
ひとつは、解を導出するのに必要な状態空間の広さは大家族のほうが約 2,200 倍ということ。盤面が大きく駒も多い分、組み合わせ爆発でゴリゴリに広がる。ソルバー目線では大家族は圧倒的に難しい。もうひとつは、最短手数は古典のほうがおよそ倍ということ。大家族は確かに賑やかだが、6×5 の盤の外周には空き 2×2 領域が点在し、4×1 の大番頭を含めても駒同士のロックインが意外と緩い。一方、古典の 4×5 は空きマスがちょうど 2 個しかなく、その 2 個をぐるぐる引き回す形でしか駒を移動できない。
つまり、
- 古典の 箱入り娘 = 狭い家でみんなギチギチ。動かすたびにあちこちぶつかる。
- 大家族の 箱入り娘 = 部屋が広いから、人数が多くてもそれなりに自由に動ける。
冒頭の答えはこうなる。
普通の箱入り娘のほうが、大家族よりも、約 2.1 倍 「箱入り」 だった。
ちなみに、§4 で同方向スライドのルールだったときは古典 90 手・大家族 49 手で、比は約 1.8 倍だった。曲がってもいい連続移動に広げると 81 手・38 手になり、比は約 2.1 倍へ少し開く。
そしてこの 81 手は、まさに冒頭で触れた「箱入り娘は最短 81 手で解けることが有名」のあの 81 手です。同方向スライドだけのルールだと古典は 90 手と出てしまい、世間の 81 手と食い違っていた。「曲がってもいい連続移動を 1 手」と定義し直して初めて、有名な 81 手とぴったり一致しました。世間で言う 81 手は、暗黙のうちにこの流儀で数えられていたわけです。大家族の 38 手も、同じ流儀での最短保証つきの数字となります。
9. 触れなかったこと（付録）
書ききれなかったが、リポジトリには 双方向探索 (pkg/solver/bidirectional.go) も入っています。順方向と逆方向の探索を中間で出会わせる、教科書的な手法です。
実はかつては IDA / A / 並列探索** と、それらが使う ヒューリスティック関数（単純な Manhattan 距離と、娘のゴール列を塞ぐ駒数を加味した Enhanced 版）も置いていました。だが連続移動ルールに切り替えたタイミングで、これらは消しました。理由はヒューリスティックが破綻してしまうからです。
Manhattan 距離（娘とゴールのマス距離）が許容ヒューリスティックであるためには、「残り手数は必ず Manhattan 距離以上」でなければならないが連続移動ルールでは、空きが通っていれば娘を 1 手でゴールまで運べてしまいます。つまり Manhattan 距離は残り手数を過大評価してしまう。許容性が崩れた A* / IDA* は、最短解を保証できずヒューリスティックなしでは A* は実質ただの BFS なので、まとめて撤去した。
10. リポジトリ
ソースは GitHub にある。
- GitHub: https://github.com/prime-oda/hakoiri_musume
- プレイ: https://prime-oda.github.io/hakoiri_musume/
- Go ソルバー:
cmd/solver/main.go(go build -o solver ./cmd/solver) - 古典版ソルバー:
go build -tags classic -o solver-classic ./cmd/solver - JS ソルバー:
web/solver.js
11.最後に
ソルバーの解いている手順を眺めると、娘が出ていくために、家族全員が一丸となって玄関までの道のりを通しているのが非常に興味深いです。誰か一人でも非協力的な駒があると娘は家を脱出できないのです。
「箱入り娘の大家族」は、さわたく工房さんが、木材を加工したパズルを販売されている。こんな面白いパズルを教えてくれてありがとうございます。
改めて結論。
箱入り娘の大家族は、実は普通の箱入り娘の半分以下しか箱入りでない。
その代わり、状態空間の広さは 2,200 倍に膨らんでいる。
ソルバーから見ると賑やかで難しく、人間から見ると意外と自由に動かせる。
箱の大きさと駒の数だけでは「箱入り度」は測れない。
ここまで読んでくれてありがとうございました。