箱入り娘を毒牙にかける・Part I

パズル『箱入り娘』を、Python3で解いてみたはなし。

• Github: https://github.com/tarohs/hakoiri
• Part I: 『箱入り娘』の解き方とアルゴリズム・データ構造の工夫、いろんな『箱入り娘』クラスのパズル
• Part II: (ヒューリスティクスの導入(してない)・力技で解けた)、並列化、Pythonのデータ構造の最適化
• Part III: 手数の数え方 (step数とRLC): 『手数』(RLC) 最適化へ

いきなりだけど、タイトルつけてから「ん?」と思って確認すると、python (ニシキヘビ) は毒蛇じゃなかったorz 。ひとを殺す、というのは、窒息させるほど巻き付き力が強いってことなんですねえ。
まあタイトルはそのままにしますが(笑)。

まあよくあるパズルの探索問題と思って始めたのですが、ちょっと面白かった。アルゴリズム・データ構造のお勉強とか、Pythonのデータ構造とか、1ヶ月近くも汗をかいて遊んでしまった。それもそのはず、後から調べると数学屋さんとか計算機屋さんに人気のあるネタだそうで。そういうトレーニングをしよう、と思っているひとにはおすすめなネタです (※ 後追いするならこの後読まずに作ってみて(笑))。

2025年6〜7月の1ヶ月くらいの記録。

※ Part IIとかでPythonでの最適化をさんざやりまくってますが、これはPythonのお勉強つーよりPython縛りゲームですな(笑)。だからCやRustで書けよ、という突っ込みはなしの方向で。
アルゴリズムをいろいろ試すのにはPython便利。ある程度最終版が固まったので、CかRustで書き直しますそのうち。

※ 記事を書き始めてからプログラムを改良し始めちゃって、記事もまた修正したので、超長いです。基本的には (後になって恥ずかしいコードを書き直した) 最終版についての説明ですが、自分メモも兼ねてるので、失敗した反省や時系列的な部分が混在しています。まとまりなくてすみません。

箱入り娘とは

日本の伝統的な木工おもちゃらしいです。いわゆる『15ゲーム』(sliding block puzzle) と呼ばれるクラスのパズル、コマを枠内でスライドさせて所定の並びにするというもの。

この場合は (ずいぶんでかい) 『娘』コマを玄関から出す……『玄関』の上4コマ (女中番頭祖父祖母の色を濃くしているところ) にもっていくのがゴール。まあ『玄関』とはいってもただの壁で、他のコマも枠内から出してはいけない。
浅学にしていままでわしは、人力でも解いたことがないし解くプログラムを作ったこともなかった。

たまたま図のようなパズルが難しいだかでTwitterで話題になっていた (Togetterまとめ) のだが、その週は『ポーランドからお客さんが来てもてなす』というなぞ業務が入っていて、遊びもお仕事も集中してできなかったので、お・も・て・な・し の空き時間にぼ〜っと考えて、夜とかちょちょっと試す、というのを続けていた。

縦型探索と横型探索

情報系の大学1年の授業ででも習いそうなはなしなので、ご存じの方はコラムは読み飛ばしてください。

縦型探索 (深さ優先探索、DFS) と横型探索 (幅優先探索、BFS)

この手の問題で解を探索する場合、縦型探索 (深さ優先探索) と横型探索 (幅優先探索) がある。

縦型探索

横型探索

まあ何も考えずにパズルを解くときは、再帰で縦型探索を使っちゃいますかね。
縦型探索は、どーやってもすぐ解にたどり着くような探索、つまりどの枝を辿ってもすぐに末端や行き止まり (後述のメモ化による枝刈り含む) になってバックトラックを起こしてしまう、などというときに向いている。

わしも新しいプログラミング言語を覚えたら書いてみるお約束の手習いのひとつ・8-Queensなど、一定の深さ以内で解が見つかるし (深さ8まで行ったらそりゃもう解だ)、もう進めないとか簡単にわかる (他のqueenの筋に入る)。
覚えておかなきゃいけない盤面状態も少ない。

箱入り娘を縦型探索で解くとすると (というか一番最初のバージョンはこれで書いた)、こんなんなる。

• (探索ルーチン) 引数は現在の盤面 (, あとここまでの手順)
  1. ゴール判定: ゴールコマがゴール位置か?
     • yes -> ここまでの手順を表示、終了
  2. コマ1〜 すべてのコマごとに
     1. 方向 [上, 右, 下, 左] ごとに
        1. 動けるか?
           • yes ->
             1. 新しい盤面を作る
             2. 自分自身 (新しい盤面, ここまでの手順+移動方向) を呼ぶ

ゴール判定はコマが動けることを確認した直後でもよい。

横型探索ではこうなる。

• (探索ルーチン) 引数は、ここまでの手で可能な探索すべき盤面のリスト
  1. まえのレベルのすべての盤面候補について
     1. すべてのコマごとに
        1. すべての方向 (上下左右4方向) ごとに
           1. 動けるか?
              • no -> 次へ
           2. ゴール判定: ゴールコマがゴール位置か?
              • yes -> ここまでの手順を表示、終了
           3. 新しい盤面候補をつくる。新しい盤面候補リストに追加。つくっておいておくだけ
  2. すべての新しい盤面候補をもって次のレベルの自分自身 (探索ルーチン) を呼ぶ

いずれの場合もメインは

• (メイン)
  1. 盤面や状態初期化
  2. 初期状態の盤面をもって探索ルーチンを呼ぶ

こんな感じ。

縦型探索は断然、再帰のほうが書きやすいけど、横型探索は別にループでもあまり手間は変わらない。

なお横型探索のばあい、最初に見つかった解がベスト解である。これはわしも途中まで勘違いしていて (縦型探索の名残もあって)、最適解かどうかのチェックコードとか余計に書いてしまった。
横型探索では、すべての候補が同じレベル、当初は最初から数えたstep数 (Part IIIの頃は『手数』RLC) が同じである。

例えばあるレベルで、遠回りして同じ状態に来る候補があったとしたら、それより少ないstep数の最短経路のメモが必ず存在するので必ず切られる。
娘が出口に至る経路をひとつみつけたとしたら、同じ盤面状態になる、より長い経路は今後見つかるかもしれないが、それより短い経路はそれまでにない (後述するがメモに存在しないから)。

横型探索へ 〜 Pythonの再帰の段数

当初バージョンは何も考えず縦型探索でさくっと作って実行してみたのだが、まず再帰を使っている以上、再帰段数のオーバーには気をつけないとならない。まあ、Pythonの再帰の最大段数はちょっと少ないかな? (デフォルトで1000くらいで再起段数エラーを起こして止まる)、という感じだし、tail recursionも最適化してくれないのだが

sys.setrecursionlimit(2000)

こんなのを書いてやれば、とりあえず増やせる。

で、実行してみた。
2000ではやっぱりあっさり止まる。
4000、8000、……おいおい。32000まで増やしても終わらない(笑)。

再帰の段数というのはこの場合、step数 (わしの定義では) に対応する。まさか人間が解けるようなパズルが10000 stepも必要とは考えにくいのだが。縦型探索の場合、たとえ最短の正解が100 stepであったとしても、解が見当違いな方向にどんどん行ってしまって、なおかつ動く自由度が大きい (たとえメモを取っていたとしてもその中に候補がない) ならば、バックトラックが起きずに段数はどんどん深くなってしまう。

ちなみに、再帰で書けるプログラムはすべてループでも書き直せるので、再帰の段数『だけ』が問題ならば、ループにしてしまえばよい (ちょっと面倒だけど)。だけどループだろうが、メモとか状態を取っておくメモリが増えるのは同じだ。

16000、32000 stepくらいまででどういう盤面になっているかモニタしてみてみると。どうやら、『大番頭』が通せんぼをして、『娘』が出てこられないようだ。数万step目くらいになると大番頭が娘の横くらいまで上がっている盤面もあったりするが、『娘』はずっと奥に張り付いて出てこない。だめだこりゃ(笑)。

まあここまでは半日くらいで辿り着いたのですが。
これは……横型探索のほうがよろしいのではないか?

箱入り娘のデータ構造

盤面の状態

縦型探索で簡単に解がみつかるパズルなら、あまりデータ構造に凝ることはなかったと思う (いい加減な性格なので)。要は、衝突が起きないか検出できて、そこまでの手順が保持されていれば何でもよい。だが横型探索では膨大な(?)盤面状態や手順を保持しないといけないので、必然的にデータ構造 (メモリ使用量とかアクセス速度とか) は慎重に考えちゃう。

ある一瞬の盤面、つまり家の中の状態を表わすプライマリなデータ構造は、各コマの座標でよい。
というか、本当にプライマリなデータ構造は『手順』であって、盤面状態は初期状態と手順から作れたりするが、はじめから手順を辿らないとある瞬間の盤面を再現できないのでは計算効率が悪すぎるから、盤面も保持する。

ソース中のColistとかいう型は、盤の中の全コマの、IDと座標の対応関係のセットである。
この後とPart IIで述べるが、当初は {コマID: 座標} のdictであったが、効率のためにdict→list→tupleへ。その後コマIDは1から連続する整数にした (XMLからパズルを読み込むようにしたのでID自動生成) し、座標も効率のため構造体→list→intへと変遷を遂げている。

座標系・座標

座標系は、Pythonの配列のアクセス順序に合わせて$(y, x)$ ($x$が横軸) とした (説明では東西南北は、画面座標系、つまり$x$は右・$y$は下が大きいとする)。以下も断りない限りこの順番ですが、界隈で『4x5パズル』っていう場合はやっぱり『横x縦』なんだよね。

当初座標 (Coords型) は2つの数字のペア (dataclassによるオブジェクトだったが速度が遅いのでtupleにした) であったが、さらに後述の盤面コマ番号 (左上→右下に数える、Twitter板箱入り娘なら0〜29の整数)、そして y << 4 | xなる整数へと変遷を遂げている。
この縛りから、解けるパズルは$14\times 14$以内なんですけどね……って、上のパズルでも爆発して解けないのに、そんなでかいの解くかよ? っていう思想です(笑)。UNIXの設計はできないね。

この最終バージョンは、16進数 (hex()) で読むと0xYXの座標値になっていてデバッグに便利だ。つまり$(3, 2)$なら0x32だ。
さらに後で出てくる盤面状態のハッシュ Cohash は、colistをID番号順にただ並べただけになったし (コマが14個だと28桁の16進数)、座標値$y$や$x$との変換も速いしやはりデバッグ時に視覚的に確認しやすい。
また特別な加算のオーバーライドを定義しなくても、整数の足し算で0x10を足せば$y$座標に1を足す、0x01を引けば$x$座標から1を引く、などの演算ができる (このために移動ベクトルを整数化したものがdirvec[]である)。

盤面のビットマップ

生のピクセル? (コマID) を並べた2次元の配列、視覚的に理解できるいわゆる『盤面』は、Colistがあればそこから作れる。Bmatrixなどという名前の型は、これである。

マス目はコマIDで埋める。0は空隙に使うのでコマIDは1から始める。
実際にコマが動けるところより縦横1マスずつ外側に『壁』を作り、そこは最初に0でもコマ番号でもない値で埋める。こうすることで、コマはみ出しの判定は、衝突判定 (コマや壁がない) で統一してできる。したがって盤の大きさbsizeは、動ける部分より縦横2だけ大きく定義する。

コマは当初、すべて長方形とした (テトリスのコマみたいなのは定義できなかった)。コマの大きさkomasizは$1 \times 1$だけではないので、座標は左上を代表座標とする。つまり下図の初期配置だと、『父』なら$(y, x) = (1, 2)$、『娘』なら$(1, 3)$である。

また当初、ビットマップ盤面はnumpyのndarrayを使った。長方形コマだけなら、スライスでコマ領域のandとnumpy.sum()で衝突判定とかbroadcastでコマ配置・消去とかできるからである。

その後の改良で、このやり方は解の表示のために残してあるが、衝突判定だけならコマ番号すら要らない。速度のため・また長方形コマとテトリスコマを同じ速度 (コマが占める行数依存) で扱うため、2進数ビットマップにしてしまった (行を整数とするリスト ←実はマイコン時代からの得意技だったりw)。

2進数のビットマップは、こんなコードを挟めばたった2行でデバッグ時に視覚化ができる。Python便利。

    for r in bmx:
        print(bin(r)[-1:1:-1])

細かいことであるが、このビットマップも生成時間の短縮のため、探索するコマごとに書き直さず、ある盤面については一回だけ生成するようにした。各コマのiterationをするときはそのコマ部分を消して、動いたときの衝突判定に使って、終わったらまた描き直す。

(2025/ 8/ 4更新)

盤面を0・1のビットマップにして眺めてみると、なんか『箱入り娘』その他のパズルでは空隙が2個くらいしかなく、0がスパースなほぼ1行列みたいになる。
これをなにか利用できないかとずっと考えていたが、消極的に利用して以下の『プレ衝突判定』を試みた。

コマの占める範囲と各空隙の位置関係・距離をみただけで、衝突判定をしなくても『絶対に移動不可能である』判定はできる。
ただし空隙数だけiterationしていたら判定でかえって時間を喰ってしまう可能性がある (そもそもビットマップにしてからのバージョンでは、不定形のコマだろうと衝突判定はすごく速い)。
そこで、下記詳細のような1次元への射影を論理演算した簡易判定とした (空隙数・コマサイズによらず一定時間)。

これで速くなったかというと、微妙(笑)。
コマの射影 (iterationするコマごとに作る・4方向は共通で使う) は一瞬で作れるが、盤面の射影 (すべてのコマ・4方向について1回だけ作る) をわざわざ作っているので、そこで時間を喰っている模様 (下記のベンチマークは、『基本箱入り娘』全体および『難しい箱入り娘』の最初のほうで計測)。

• step数最適……各stepについて射影を作っている・『この先動けるか』では使用せず: 5%くらい遅くなった (涙)
• RLC最適……各手について最初に射影を作ったら、「つるつるっと動く」上で使い続けられる限りつかう (上記のようにコマの垂直移動ならgapprojxは変わらない・同水平移動gapprojy): 2%くらい速い
  • ダンプして内訳をみると、「つるつるっ」の最初の1手で衝突判定がサボれる割合が約3割。もう3割くらい、続くstep・RLC内で衝突判定をサボれている

Pythonのint (射影はintのシフト・論理演算が中心だ) は可変長であるがゆえに、シフトや論理演算があまり速くない、というはなしもある。そのためかもしれない。

やはりというか、下記『いろいろなパズル』の中では、空隙コマだらけのSOAPでは微妙に (4%くらい) 速度ダウン、空隙コマが1個しかない15ゲーム (21手くらいまで) では16%もの速度アップになった。

射影を使ったプレ衝突判定 (コマの移動可能性のチェック)

• すべてのコマで埋め尽くされた移動前の盤面の空隙から$x$軸への射影をgapprojx、コマ (移動前の位置) から$x$軸への射影をkomaprojxとすると (gapprojx、komaprojxは1次元ビットマップの整数・Projection型):
  • 移動方向が北・南だったら、gapprojx & komaprojx != komaprojxなら移動できない
    • つまり空隙は『コマの幅』だけ同じ$x$座標に並んでいることが必要条件
    • (==だった……コマの幅だけ空隙が並んでいたとしても移動できるとは限らない (これは射影なので$y$座標とかコマ・空隙の凹凸は考慮していない)→衝突判定を真面目にする)
    • 次の1 stepについても、gapprojx (komaprojx) は変わらない
  • 移動方向が東 (西) の場合、gapprojxの、komaprojxの1並びの東隣 (西隣) ビット位置は1である必要がある
    • (次の1手ではgapprojx、komaprojxは変わるので、プレ衝突判定はしない)
  • なおkomaprojxは、駒の形によらず1..1(コマ幅分) である (全0の列はないから)
• $y$軸に対する空隙・コマの射影についても同じ (略)

例: (実際は左がLSB)

        盤面3x4    コマ2x2 @(2, 2)
        1111
        1011      .01.
        0111      .11.
projx:  --------------
        1100      0110 ← 1の位置はコマの幅が占める場所
        ↑1はどこかの行に空隙があることを示す
コマ東隣            0001
コマ西隣            1000

なおコマ東西隣ビットのマスクは(kpj ^ (kpj << 1)) & ~kpj、(kpj ^ (kpj >> 1)) & ~kpjとして計算できる。

コマ射影  :01110  01110
<</>> 1  :11100  00111
xor取ると :10010  01001 (西・東隣とコマの東・西エッジが1)
~koma    :10001  10001 (コマ外が1)

手と手順

『手』(Move) は、動かすコマのIDKomaidと方向ベクトルDiridのペアになる。
これもtupleから効率化のために整数 (komaid << 2 | dirvec) とかにしてみたが、ほとんどメモリ節約にならないし速くならなかった (解く問題の規模による) ので、tupleに戻した。

『手順』Movehist は単純に『手』を並べた可変長listとかtupleになる。

手数の数え方

実はこれ、後で大ハマリする原因なのであるが。
詳しいことはPart IIIで、っていうかPart IIIはその話題で1パートである。『手数』の定義は、実はパズルの定義 (そして最適解を求める手法) に関わる大問題である。

当初は、ふつーに計算機パズル解きの感覚で、step (複数形省略w) というのはコマを1マス動かすと1、と数えていた。
ところが、Conway先生の『Century』が100 stepにならないとか、Wikipediaで『基本的な箱入り娘』が81手とあるのに115 stepになるとか、の不一致を発見した。
最適なはずなのに、なんで?

すぐにこれは、『手数』の定義 (数え方) によるものだとわかった。
つまり、sliding block puzzle界の常識では「一コマを連続してつるつるっと動かすときは1」と数えている。
本稿 (やプログラム) では、前者をstep数・後者をRLC (rectlinear count、整数だけどRlc型)として区別している。

当初はしつこくstep数を最適にするアルゴリズムをつくっていたが、最適RLCを求めるアルゴリズムに至る (Part III) 前までの間も『同じstep数なら最適RLCを選ぶ』ようにしていた (なんの拘り? w) ため、当初からRLCも盤面 (手順の手) ごとに保持している。
step数もRLCも、プライマリには手順Movehistがあれば作成できるのだが、前者はlen(movehist)で瞬間に作れるのに対し、後者は『連続した2 moveが同じコマか?』を勘案しないといけないため、盤の局面ごとに手順と一緒に保持している (ただしRLC最適化では、同じ探索レベルでは同じRLCになるので保持は不要だが、同じソルバで解かせるため同じ形式である)。

MCR構造体

以上を組み合わせた『ある手順における手順と盤面状態』、つまり横型探索で探索候補として持っておくのがMcr (Move-Colist-RLC) 型 (構造体) である。

並列探索のメインの探索部分では、上のレベルから可能な候補のリストを受け取って、動けるコマ × 方向の枝を1段付け加えてそのレベルのリストに付け加えていく。
細かいことだがPythonのデータ構造的には (Part IIで詳しく述べる)、探索ループの最初、あるレベルの探索のため前のレベルから受け取るときはMcrのlistなのだが、探索候補をつくったらメモ (今までのレベルの盤面) との重複、あるいは自分で既に (このレベルで) 探した候補との重複を検査しやすいように、McrはC (Colist) のハッシュ値 (次に述べる) をキーとするdictにしておく。次レベルに行くときは、dictのkeyのsetをメモに追加・valueのlistを次の探索候補として渡す。
探索候補は、当初勘違いして手数ごとに2次元のリストを使っていたが、並列探索では上のレベルの候補は取っておく必要はない。というより、取っておいたらメモリのムダである。ループの場合は次探索候補listのbindを『この段で探索する候補』にすりかえちゃえばPythonがごみ収集してくれるが、再帰を使うときは次段 (子どものオレ) を呼ぶ前にきちんとdel()する。

メモ化というか枝刈り

これまた探索アルゴリズム (再帰関数を呼び出す言語) ではよく習うはなし。

箱入り娘では、枝ノードが他のノードと重複 (ノードが複数の親を持つ) したりしている。つまりある盤面状態に至る手順が複数ある。これをろくに考えないメモ化で実装したのが、当初3万手w までで終わらなくなった縦型探索の原因である。

ある再帰関数を呼ぶときとか探索候補を調べるとき、前の関数の計算結果や途中の盤面状態をキャッシュしておき、以前と同じ入力が来たら……関数の入力のばあいは『同じ答え (出力) を返す』でよいのだけど、探索の場合は『探索を打ち切る』ことにする。そうすることで、以前探索したのと同じ状態からまた探索せずにすむ、ということである (探索の枝刈り)。

箱入り娘の場合で考えると、例えば『父』の左に空間があるから左に動かした後、右に空間ができたからといってまた右に動かしたら、千日手になってしまう。

なおこの2手リピートの『千日手』については後に、ちょっとでも盤面比較の時間を減らすため、『直前と同一コマが反対方向から来たか』を判定している。

縦型の探索の場合、メモの (これまで通った同じ) 盤面状態が同じで、今回探す盤面に至る経路のほうが短ければ、最短手数・手順を更新することもできる (あとそれ以降の道筋は既に辿られているなら辿り直す必要はない)。

Pythonのinによるsetの検索

一度とった盤の状態をリストやセットにしておけば、Pythonのinで簡単にメモ内に存在するか調べられる。
盤の状態は、基本的には上述のように(IDと座標)のタプルの、全コマ分のセットである。要素がセットになっているリストをinで検索できるのかな、と思ってちょっと試してみると、いけるようである (setなので要素の順番関係ないことに注目)。

>>> a = [{(3, 4), (2, 3)}, {(2, 3), (5, 6)}]
>>> print({(2, 3), (3, 4)} in a)
True
>>> print({(2, 3), (5, 4)} in a)
False

で、縦型探索の (ときに) 入口にささっと実装してみたのだが……。
3万手w まで探索しても解がみつからないときに、真っ先に疑ったのがこのsetの検索である。かなりきつきつで動ける箇所がそれほどなさそうなのに、循環手にならずに3万手ものバリエーションがあるものか? (※ 実際にはそのまた数百倍以上あるw) なんかPythonのsetが、検索漏れを起こしているのではないか、と。

結論から言えばこれは濡れ衣だったのだが、おかげで『盤の状態のhash値』と『コマクラス』というのを思いついてしまった。

盤面構造のフラット化

上の座標の表現でも少し触れたが、一番最初のhash値計算では盤の状態をフラットにして (つまりhash) 整数化した。考え方としては:

• 盤のうちコマが動ける部分は、$(6 \times 5) = 30$のマス目である。それぞれのマス目が15の状態 (空白または14のコマのいずれか) を取るのだから、15進数30桁の整数で表わせる。
• あるいは、こう考えても良い。上述のように盤の状態は14のコマの座標値 ($6 \times 5$のコマ可動範囲に0〜29の番号を振った値、つまりマス目の番号) で決まるので、14桁の30進数で表わすこともできる。
  • なお、30コマがたまたま$2^5$に近かったので、32進数にしてみた (べき乗の代わりにシフト演算が使える) が、0.何%しか速くならなかったので、盤の大きさの一般化および可読性を考慮して一旦はボツにした (→後にもっと冗長な256進数として復活する)

どちらかというと前者のほうが冗長と考えられる (0が多い) ので、後者で実装することにした。
整数の桁数で比べると、前者は$\log_2 (15^{30}) \simeq 118$ビット、後者は$\log_2 (30^{14}) \simeq 69$ビットくらいあるが、Pythonのint型は桁数不問なのでまあ良いだろう (numpy.ndarrayの要素だとint64とかの制限がある)。

座標値 (当初)

当初の座標値は、コマの動ける範囲 (盤面より$2\times 2$少ない) を左上から右下に、走査線 (※ 昭和) の順番に番号を振ったものを、マスの座標値とした。

この後の例では、後述する『基本の箱入り娘』を例にしよう $(y\times x) = (5 \times 4)$と小さいしコマ数が少なめ・10コマなので)。

y\x	0	1	2	3	4	5
0
1		0	1	2	3
2		4	5	6	7
3		8	9	10	11
4		12	13	14	15
5		16	17	18	19
6

結局、$(y, x)$のtupleのsetを、ハッシュ値 (int) のsetに変えてみても、探索履歴 (途中の手をざーっと表示させてみた) は変わらなかったので、当初の『メモ (セット) 検索漏れ疑惑』は濡れ衣だとわかったのだが、探索が4倍 (!) くらい速くなった。んで、このまま行くことにした。

Pythonでもinで検索できるものは、キーをハッシュできるものに限られているから、同様のフラット化がなされているのだと思う。つか、わしがフラット化した値は疎だし (長い整数だし) さらにset検索の際にハッシュされていると思う。
では、わざわざ少ない脳みそを絞ってハッシュしたほうがなんで速かったかというと、複雑なデータ構造をジェネリックな手段でフラット化するより、データ構造がわかっていて無駄なくタイトにフラット化されたもののほうが、効率が良い、という教訓なのだろう。

という知見は得たものの、もし計算機が4倍速くなったら、こういうことに悩んでプログラムがなかなかできなかったり、バグを誘発したりするよりか、Pythonにフラット化を任せたほうがよいのかも。
バランス取らなきゃな〜!?

座標を整数値にした後

座標系の説明で書いたが、当初の$(y, x)$のtupleが効率悪そうだったので、座標を整数化した。そうすると上で言っている『座標値』は『座標』(Coords型) そのものになるわけで、それをつなぎ合わせれば盤面状態になる。

整数化した座標 == 座標値

y\x	0	1	2	3	4	5
0
1		0x11	0x12	0x13	0x14
2		0x21	0x22	0x23	0x24
3		0x31	0x32	0x33	0x34
4		0x41	0x42	0x43	0x44
5		0x51	0x52	0x53	0x54
6

これは16進数でみないと意味ない。16進値なら、みただけで盤面状態が人間にもひと目でわかるしハッシュ値のパーツにもなっている。周囲は壁に取られるのでコマ可動範囲の$y$、$x$は1はじまりになっている。

例えば初期状態の『娘・父・母』はそれぞれ$(1, 2), (1, 1), (1, 4)$にいるので

• コマの座標 (Coords型) はそれぞれ0x12、0x11、0x14となる。そのまんまやんけ
• 盤面のハッシュ値 (この3コマしかいなくてコマIDは上の順番として) は、0x121114となる。そのまんまや〜

初期のバージョンでは、1つのコマの位置に関する情報量は、20マスに対して$\log_2(20) \simeq 4.3$bit程度、10コマで$10 \log_2(20) \simeq 43$ bitを割り当てることになるが、この例では1マスが必ず8bitになるので10コマで80bitと冗長にはなる (数百万の候補盤面については馬鹿にならない差である)。
それでも、掛け算足し算よりシフト・ORのほうがやや速い (オブジェクト生成とGC含めても1%程度高速w) とみえて、デバッグしやすい上に速くなった。

ソートされたコマクラスによるハッシュ値

ちょっとややこしいはなしであるが、これは割と初期の段階で導入したアルゴリズム最適化のはなし。

探索の枝刈りをより効率的にするために、コマの大きさの互換性に着目する。
すなわち$1 \times 1$の大きさをもつコマは別に女中だろうが兄嫁だろうが互換性があるのではないか。そこに至るまでの経路は違うかもしれないが、その後その形の『誰か』が取りうるアクションは同じだ (※ 後で気づくが、正確にはゴール対象のコマでない場合に限り)。そしてメモにないならば、その状態 (互換コマを含めて) に至る最短経路である。

そこで『コマの大きさ (形) クラス (種類)ID』を導入した (Komacls型)。$2 \times 1$と$1 \times 2$はもちろん、別のクラスである。
当初はソートのキーとして使われるだけなので Komacls は整数値とかであれば何でも構わない、としたが、XMLファイルからパズル定義を読むようになって、これまた1〜254の連続した整数値 (自動生成) となった。0と255は、とあるアルゴリズム (Part II『自前アルゴリズムの敗北』で述べる) でガード値として使う (……予定であったが最終的にはそのアルゴリズムはクビになっている)。

コマクラスを考慮した盤面状態のハッシュ値は次のように計算できる。

• 『コマ座標値』(前出の表参照) 順→『コマの大きさクラス』順にコマをソートする (『コマの大きさクラス』で整列・同じクラス内では『座標値』で並んでいる状態にする)
  • Pythonのsort()、sorted()は順序保証なので、座標値→コマクラスとキーを変えて次々呼び出すだけである
• このときのインデックスを『コマの種類インデックス』とする
• ハッシュ値は、『コマの種類インデックス』(コマ数分) を桁として『コマの座標値』を値とする (この例では10桁の256進数で表わされる)

いままでのハッシュ値は『コマID順に』桁重みを付けた座標値だったが、この場合は『コマの種類インデックス順に』桁重みを付けた座標値、ということになる。

わかりにくいが、例は下の囲みに示す。

例: コマクラスリストのハッシュ値の計算

初期状態の盤面の状態は、 $({\rm コマID}, (y, x)) \Rightarrow {\rm コマ座標値}$ のリストが

[(1, (1, 1)), (2, (1, 2)), (3, (1, 4)), (4, (3, 1)),
 (5, (3, 2)), (6, (3, 4)), (7, (4, 2)), (8, (4, 3)),
 (9, (5, 1)), (10, (5, 4))]
=>
[0x11, 0x12, 0x14, 0x31, 0x32, 0x34, 0x42, 0x43, 0x51, 0x54]

(上の『基本の箱入り娘』の写真で、コマの左上隅の座標値が、左上→右下に増える順に並べている: 父、娘、母、祖父、兄弟、祖母、……)

また、コマのクラス

ID	$y \times x$
1	$2 \times 2$
2	$2 \times 1$
3	$1 \times 2$
4	$1 \times 1$

としたとき、コマID順のクラスが

[2, 1, 2, 2, 3, 2, 4, 4, 4, 4]

となっていたとしよう。

これをクラス順

[1, 2, 2, 2, 2, 3, 4, 4, 4, 4]

次にクラス内では座標順に並ぶようにすると

[0x12, 0x11, 0x14, 0x31, 0x34, 0x32, 0x42, 0x43, 0x51, 0x54]

となる。

ちなみにPythonのソートは順序保証があるので、単純に座標順にソート (上記は既に座標順に並んでいるが)→クラス順にソート、とするだけでよい。

この状態では必ず

• リストの1番目にコマの大きさクラス = 1のコマ ($2\times 2$のコマ、『娘』) の座標値
• リストの2〜5番目にコマの大きさクラス = 2 (縦長2マス、『父』『母』『祖父』『祖母』) のコマが座標(値)順で入る。クラスに複数のコマがある場合、それが父母祖父祖母のどれであるかは問わない
• 同様に6番目は横長2マスのコマなので唯一必ず『兄弟』
• 7〜10が1マスのコマ『和裁』『華道』『茶道』『書道』(いずれかを問わず)が座標(値)順に入ることになる

これを結合したハッシュ値は 0x12111431343242435154 である。

この後『いろいろなパズル』で詳しく紹介するように、パズルによってゴールの定義は、大きく分けると

1. Goaltype: BYID: 『特定のコマまたは全コマが所定の位置に』 (例えば『15ゲーム』は『1』〜『15』と数字が書かれたコマを順番に並べる。例えば『箱入り娘』もこれでもよい)
2. Goaltype: BYCLS: 『ある形のコマ (一部、どれでもいい) が所定の場所に来る』 (例えば『箱入り娘』もこれでもよい)
3. Goaltype: BYCLSHASH: 『ある形のコマ全部が所定の位置に揃う』(例えば後述・Conwayの『Century and a half』)

ことであったりする。

1. は一番ふつうに考えられるように、ゴールコマ (全コマではない: したがって辞書を使う) が指定位置にあるかを調べるのだが、いくつかのパズルでは1.ではなく2.でゴール判定をしていることから、ここで言うコマクラスがゴール判定でも活躍する。
2. のゴールタイプが指定されていたら、ゴールコマだけではなくその同クラスのコマいずれかが指定位置にあるか調べる (のでちょっとだけ計算量が増える)。
3. は、ここでのトピックの『盤面全体のソートされたクラスによるハッシュ値』を比較するので、ハッシュ値比較一発である。

鏡像もメモ

2番目の工夫は、鏡像対称を同じとみなす、ということ。8-Queens程度の問題を解くときは、鏡像対称 (8-Queenなら回転対称も) の検出などサボって、全解を出力してから目の子で重複解を探したりするんですが(笑)、こと激しい嫁入り娘 (※ 解の爆発が)、中途状態も半分にでも候補を減らせれば御の字。

つまり、左側の『父』を左に動かすところから始めるのと、鏡対象でまったく同じ解は『母』を右に動かすところから始められるので、『父』を左に動かした鏡像のハッシュ値をもうひとつ登録しておけば、『母』のほうの枝の分岐は刈れる、ということっす。

考え方としては上記のハッシュ値の計算において、『座標値』の与え方を反転 (つまり左上→右下に番号を振っているのを、右上→左下に) とするだけ……なんだけど、幅2以上のコマもあるので、コマの座標も左上ではなく右上に換算してやらないといけない (コマの幅より1少ない数を引く)。

上記の例では、鏡像の座標値は次のようになる。

y\x	0	1	2	3	4	5
0
1		0x14	0x13	0x12	0x11
2		0x24	0x23	0x22	0x21
3		0x34	0x33	0x32	0x31
4		0x44	0x43	0x42	0x41
5		0x54	0x53	0x52	0x51
6

例: 鏡像のハッシュ値の計算

上記、ハッシュ値が 0x12111431343242435154 のときの鏡像のハッシュ値を計算してみる。

上の表でわかるように

• まずクラス1 (唯一) の『娘』は0x12の鏡像位置0x13にくるのだが、幅2のコマなので1を引いて0x12が鏡像の右上の位置になる
• クラス2のコマはそれぞれ、0x11・0x14・0x31・0x34だから、鏡像の位置は0x14・0x11・0x34・0x31になるが、クラス内で座標値をソートして0x11・0x14・0x31・0x34となる
• クラス3のコマ『兄弟』も、0x32の鏡像位置0x33から娘同様1を引いて0x32
• クラス4のコマもクラス2同様、0x43・0x42・0x54・0x51に来るが、ソートして0x42・0x43・0x51・0x54
• これらをクラス順につなぎ合わせて、鏡像のハッシュ値は 0x12111431343242435154
• 鏡像と正像のハッシュ値が同じであるが、左右対称なのでこれは正しい

デバッグには

• 大きさの同じコマを入れ替えても同じ値になることを確認する
• 鏡対象に配置したコマで同じになることを確認する (上の例と同じ)
  • そもそも (本文の例のように) スタート直後に父が左に行く候補がメモに登録されるので、その後母が右に行こうとするとき『既にメモにある』として狩られることを確認するなども

すればよい。

さらに、2つの値をメモに入れるのではなく、正像と鏡像2つの値を同時に計算して、小さい方を『その盤の状態値』とすれば、メモリと探索時間の節約になる。並列に2つ計算して、小さい方をハッシュ値とする。

ちなみにPart II『自前アルゴリズムの敗北』では、ハッシュ値の計算および鏡像計算のときソートしなくてよいようにしてみたことがある……のだが、これで逆に遅くなってしまった (5%程度)。Pythonのforで回してifで判断するより、何も考えずsort()した方が速かった……という(涙)。

箱入り娘は出られないのか！？

さて、上の例では4x5クラスの箱入り娘で説明しているが、時間を巻き戻すとこのあたりのデータ構造・アルゴリズムを考えていたときは、最初のTwitterでみた『難しい箱入り娘』を解こうとしている。

ここまでのデータ構造の工夫をする前、一番最初の横型探索 (何も考えず座標タプルのセットでメモ化) では、深さごとの候補数と時間はこんな感じであった。

(横軸: step数・Macbook Pro)

と実行してみると、やっぱり……手数の爆発は「それほどでもない」といっても、1段増えるごとにやはり、漸近的には手数が1.45倍くらい、実行時間がちょうど2倍くらいになっていく。
18手まででも10分ちょっと。ううむ、このペースでは50手くらいまででも8万年くらい掛かる計算になる(泣)。

実行時間を減らすためにわしがよくやる常套手段は『並列化』である (この後Part IIにて)。
だけど10倍 (CPUのコア数) とか速くなっても、計算量オーダは変わらない。8万年が8千年になっても、やはり解にお目にかかれることはこの人生では、ない。

と人生の儚さについて考えていて思いついたのが、ここまでのコマクラスの考慮、盤面状態のハッシュおよび鏡像の工夫である。これらを実装してみる。さあ、どれだけ刈れるかな〜?

(横軸: step数・Macbook Pro)

だいぶ爆発は抑えられたようだ (計算量のオーダが減っている)。24手までで4分、1手ごとにメモリは1.5倍程度、実行時間は1.4倍程度。

(この辺で次節のようにカンニングを試みたので、他のパズル同様に) 100手くらいで解が見つかるらしい? として? 100 stepで800万年……うん、だいぶ速くなったね♡

って。

これでは、終わることはないのではないか。万事休す。

ちょっとここでカンニング

伝統的なパズルであれば、誰かが最短手順とかを解明しているはずだ。実行時間やメモリの見当をつけるにも、数十手で終わるのか数百手なのか、あるいは本当に数万以上の手数を踏まないといけないのか。数万手はあり得ないといったが、人間であれば小さいコマを連続した4つの空きにつるんと動かすのも計算機にとっては深さ4の探索が必要だし、人間ならルービックキューブを解くときのように20手くらいからなるコンビネーションを似たパターンで何度も適用する、ということもあり得る。多分、数百手くらいは朝飯前だ (?)。

ここに至ってちょっとカンニングしてみよう。
WikiPedia 箱入り娘……ぼへぇ〜っ!?

そもそも紹介されているパズルが、違う(笑)。もっと簡単である。あの、どうやっても上に退けられる気がしない『大番頭』がいない(笑)。紹介によると、81手くらいで娘は出口に到達できるようだ。

いろいろな箱入り娘が考案されている、という紹介はあるが、さいしょのTwitterにあった箱入り娘は、かなり難しいパターンのようだ。最も簡単な箱入り娘は、下のようなもの、らしい (WikiPediaより。『将棋』にみたてている)。

パズルの与え方 (そして初めて解けた『将棋』の定義)

Part IIで述べるが、しばらく (手を付けて10日目くらいまで) は、パズルの定義は構造体 (dataclassによるオブジェクトの糖衣錠) で与えていた。構造体メンバは、コマのID・名前・大きさ・コマクラス・初期座標、である。
それ以外には幸い、決め打ちにしている部分はないので、別のパズルを解くときはパズル定義の部分を簡単に書き換えられる。
ありがとう構造体。

最も簡単な箱入り娘『将棋』の定義 (構造体) 部分

######## komalist shougi ########
komalist = (
    Koma( 1, 'hisha',   Coords(2, 1), 2, Coords(1, 1)),
    Koma( 2, 'oh',      Coords(2, 2), 1, Coords(1, 2)),
    Koma( 3, 'kaku',    Coords(2, 1), 2, Coords(1, 4)),
    Koma( 4, 'kou1',    Coords(1, 1), 4, Coords(3, 1)), 
    Koma( 5, 'keima1',  Coords(1, 1), 4, Coords(3, 2)),
    Koma( 6, 'keima2',  Coords(1, 1), 4, Coords(3, 3)),
    Koma( 7, 'kou2',    Coords(1, 1), 4, Coords(3, 4)),
    Koma( 8, 'kin',     Coords(1, 2), 3, Coords(4, 1)),
    Koma( 9, 'gin',     Coords(1, 2), 3, Coords(4, 3)),
    Koma(10, 'fu1',     Coords(1, 1), 4, Coords(5, 1)),
    Koma(11, 'fu2',     Coords(1, 1), 4, Coords(5, 4)), 
)
BSIZE = (7, 6)  # (y, x)
KOMA_GOAL = 2
POS_GOAL = Coords(4, 2)

さあこれで走らせてみよう……。手数の爆発も、Twitter版箱入り娘より随分少ない。
横型探索で次のレベルに渡す候補の数 (下記実行ログで『search: 』の値) もほとんど増えないし (平均1レベルで1.1倍程度)、実行時間もそれに比例したくらいしか増えない。

(横軸: step数・Macbook Pro)

結局、デバッグしながら最大 (打ち切り) 段数を変化させている途中で、63 step目で解がみつかった。
なんと。解を出力するルーチンのバグをここで初めて、出すことになってしまった(汗)。

候補数は最大で1000ちょっと (最後わずかに減る)、実行時間37秒。なお面白いことに (当たり前か???) このパズル、2021 M1 Macbook Proと、2024 M2 Macbook Airでは実行時間がほぼ同じ……さいきんGPU絡みのものばかり走らせたり作ったりしているが、CPUクロックだけに依存している。
そのうち、GPUでも解いてみるか!? (笑)

『将棋』の解 (63手)

% python3 hakoiri.py 70 
---lev: 0, search: 1, time: 9.5367431640625e-07
---lev: 1, search: 1, time: 0.0005371570587158203
---lev: 2, search: 2, time: 0.0008990764617919922
---lev: 3, search: 1, time: 0.001499176025390625
---lev: 4, search: 3, time: 0.0019068717956542969
---lev: 5, search: 9, time: 0.003280162811279297
---lev: 6, search: 16, time: 0.006987094879150391
---lev: 7, search: 27, time: 0.014128923416137695
---lev: 8, search: 30, time: 0.02474212646484375
---lev: 9, search: 28, time: 0.035919189453125
---lev: 10, search: 28, time: 0.045866966247558594

(中略)
---lev: 61, search: 681, time: 33.57582211494446
---lev: 62, search: 652, time: 35.37714409828186
---lev: 63, search: 655, time: 36.77780604362488
@found
63 655 38.055423974990845
initial:
[[99 99 99 99 99 99]
 [99  1  2  2  3 99]
 [99  1  2  2  3 99]
 [99  4  5  6  7 99]
 [99  8  8  9  9 99]
 [99 10  0  0 11 99]
 [99 99 99 99 99 99]]
move 1: fu1 to (0, 1):
[[99 99 99 99 99 99]
 [99  1  2  2  3 99]
 [99  1  2  2  3 99]
 [99  4  5  6  7 99]
 [99  8  8  9  9 99]
 [99  0 10  0 11 99]
 [99 99 99 99 99 99]]
(中略)
move 63: fu2 to (0, -1):
[[99 99 99 99 99 99]
 [99  1  4  3  6 99]
 [99  1  7  3  5 99]
 [99  8  8  9  9 99]
 [99 10  0  2  2 99]
 [99 11  0  2  2 99]
 [99 99 99 99 99 99]]
move 64: oh to (0, -1):
[[99 99 99 99 99 99]
 [99  1  4  3  6 99]
 [99  1  7  3  5 99]
 [99  8  8  9  9 99]
 [99 10  2  2  0 99]
 [99 11  2  2  0 99]
 [99 99 99 99 99 99]]

他家の箱入り娘 〜 いろいろなパズルと、それぞれのゴール

まあいちおう、ゆるい家の箱入り娘であればなんとかモノにできそうなので (※ 言い方)、他のパターンをやってみよう。
お〜。いろいろ検索してみると、盤面に余計な突起があって左右非対称 (鏡像対称のメモ化は使えないだろう) だとか、ピースを半分の位置まで動かす? なんてのもあるぞ?
実行できるページにリンクしているものは、ブラウザ上で動いたりするらしいが、残念ながらJavaアプレット実行なぞ今日びセキュリティ制限でできないので、なにが動くのかよくわからん。すんすん。

ということでいろいろ試してみた結果、また悩むことになる。
ゴールの定義と判定について、である

いろいろなタイプのゴール

最初に、パズルによってはどういう状態がゴールか、というのが異なる。ひとつのプログラムでいろいろなタイプのゴールに対応したい、というのが欲張りなのかもしれないが。
したがって、この部分は最後の最後まであーでもないこーでもないといじっていた部分である。ソルバの本質的アルゴリズムがもうおおむねのバグはなくなっていても、パズルの定義の仕方と判定が誤っていると、解が得られなかったり最適解でなかったり (このためソルバ自体を疑って候補のダンプを繰り返したり)。

上記コマクラスの囲みの再掲になるが、ゴールのタイプは、大きく分けると次の3通りである。

1. Goaltype: BYID: 『特定の一部コマまたは全コマが所定の位置に』 (例えば『15ゲーム』は『1』〜『15』と数字が書かれたコマを順番に並べる。『箱入り娘』(1コマの位置指定)、『Cicago (swap)』(2コマの位置指定)、『Super Super Dry 3』(全コマの位置指定) なども)
2. Goaltype: BYCLS: 『あるクラスのコマ (一部) が所定の場所に来る』 (例えば『Chicago』のeast/westどちらのコマがゴール位置にきてもよいルールとか。『箱入り娘』もこれでもよい)
3. Goaltype: BYCLSHASH: 『あるクラスのコマ全部が所定の位置に揃う』(例えば後述・Conwayの『Century and a half』『Super Super Dry』『同2』など)

パズルの多くでは色で塗り分けられている、つまりここでいう『コマクラスID』だったりする。
つまりコマクラスIDの導入は、メモ化の効率化だけではなく、パズルのゴールを定義するのにも便利なのだった。

なお1.でも2.でもよいようなパズルは、1.で解いたほうがちょっとだけ判定時間の節約になる。
さらに2.と3.では、3.は盤面ハッシュ値の比較一発なので超速いが、2.では『ゴールすべきコマクラス』のdictとひとつずつ比較するので、ゴールコマ数が多ければ多いほど判定に時間がかかる (1.タイプのゴールでも同様である)。

以下に紹介するいろいろなパズルは、上記3通りの定義で、まあゴール判定できる。後述する『Chicago』『Super Dryシリーズ』の紹介で詳しく述べる (ソルバのゴール判定が正しいか、さんざこれらのパズルのお世話になった)。

基本の箱入り娘 〜 XMLでパズルを与える

まずWikiPediaにある『ごく一般的』らしい箱入り娘である。
にしても、華道・茶道・和裁・書道って、邪魔する『オブジェクト』なのか? 『メソッド』じゃないのか? (まあ言いたいことはわかる)

こちらは、上記のアルゴリズム最適化のはなしでも、Part IIのPython最適化・並列化のはなしでも、Part IIIのRLC最適解の発見のときも、デバッグのために使い続けている (なお下記グラフは初期バージョン、10秒ほどかかっているのがPart IIで主に述べるPythonデータ構造の最適化によって、最後には2秒半くらいまで短縮されている。えへん)。

XMLでパズルを与えるようにしたのが、こんな定義の仕方だ。
XMLの記法、そしてパズル定義の書法さえ誤っていなければ、データの矛盾のチェックは探索途中ではしなくてよい。

ごく一般的な箱入り娘の定義 (XML) ファイル

座標の記述がXMLっぽくないが (<y>なんとか</y><x>かんとか</x>にすべきだろうが)、タイピングが面倒なので(爆) ここだけカンマ区切りになっている。

<?xml version="1.0"?>
<puzzle name="hakoiri basic">
  <board>
	<size>7, 6</size>
  </board>
  <clssiz>
	<class name="big">
	  <size>2, 2</size>
	</class>
	<class name="vert"><size>2, 1</size></class>
	<class name="horiz"><size>1, 2</size></class>
	<class name="small"><size>1, 1</size></class>
  </clssiz>
  <komaset>
	<koma name="musume">
	  <class>big</class><init>1, 2</init>
	  <goal>4, 2</goal>
	</koma>
	<koma name="chichi">
	  <class>vert</class><init>1, 1</init>
	</koma>
	<koma name="haha">
	  <class>vert</class><init>1, 4</init>
	</koma>
	<koma name="sofu"><short>sf</short>
	  <class>vert</class><init>3, 1</init>
	</koma>
	<koma name="sobo"><short>sb</short>
	  <class>vert</class><init>3, 4</init>
	</koma>
	<koma name="kyoudai">
	  <class>horiz</class><init>3, 2</init>
	</koma>
	<koma name="kadou">
	  <class>small</class><init>4, 2</init>
	</koma>
	<koma name="sadou">
	  <class>small</class><init>4, 3</init>
	</koma>
	<koma name="wasai">
	  <class>small</class><init>5, 1</init>
	</koma>
	<koma name="shodou">
	  <class>small</class><init>5, 4</init>
	</koma>
  </komaset>
</puzzle>

WikiPediaの記述によれば、長方形コマが多いこちらのほうが『将棋』より難しい? ようなことが書いてある。
確かに手数は116 stepと多いが、途中の候補数はほとんど増えず……というか、途中で減ってまた増えたり減ったりしている。『娘』移動の軌跡をみてみると家の中をS字に動いているようで、家の真ん中辺では特異現象が起きているのかな。
実行時間も全部で10秒と『将棋』より全然速い。

当初、WikiPediaには『81手』とか書いてあるが間違い? 数え方の違い? かと思っていた。手数 (RLC) の数え方については後で、そしてPart IIIで悩むことになる。

(初期バージョン・step数最適 (横軸: step数)・Macbook Pro)

ごく一般的な箱入り娘の実行ログ (部分)

---lev: 0, search: 1, time: 2.1457672119140625e-06
---lev: 1, search: 2, time: 0.0009920597076416016
---lev: 2, search: 6, time: 0.0019059181213378906
---lev: 3, search: 7, time: 0.0040130615234375
---lev: 4, search: 10, time: 0.006685972213745117
---lev: 5, search: 8, time: 0.010136842727661133
---lev: 6, search: 10, time: 0.013223886489868164
---lev: 7, search: 10, time: 0.016353130340576172
---lev: 8, search: 11, time: 0.019768714904785156
---lev: 9, search: 16, time: 0.023725032806396484
---lev: 10, search: 19, time: 0.029350996017456055
(中略)
---lev: 106, search: 105, time: 9.502649784088135
---lev: 107, search: 107, time: 9.621942043304443
---lev: 108, search: 98, time: 9.746338844299316
---lev: 109, search: 89, time: 9.856013774871826
---lev: 110, search: 94, time: 9.955394983291626
---lev: 111, search: 87, time: 10.060780048370361
---lev: 112, search: 72, time: 10.163563013076782
---lev: 113, search: 52, time: 10.24567198753357
---lev: 114, search: 45, time: 10.301735877990723
---lev: 115, search: 40, time: 10.34952974319458
@found
115 40 10.377661943435669
initial:
[[99 99 99 99 99 99]
 [99  1  2  2  3 99]
 [99  1  2  2  3 99]
 [99  4  5  5  6 99]
 [99  4  7  8  6 99]
 [99  9  0  0 10 99]
 [99 99 99 99 99 99]]
move 1: wasai to (0, 1):
[[99 99 99 99 99 99]
 [99  1  2  2  3 99]
 [99  1  2  2  3 99]
 [99  4  5  5  6 99]
 [99  4  7  8  6 99]
 [99  0  9  0 10 99]
 [99 99 99 99 99 99]]
(中略)
move 75: shodou to (0, 1):
[[99 99 99 99 99 99]
 [99  4  7  0 10 99]
 [99  4  1  2  2 99]
 [99  6  1  2  2 99]
 [99  6  3  5  5 99]
 [99  0  3  8  9 99]
 [99 99 99 99 99 99]]
(中略)
move 109: kadou to (0, -1):
[[99 99 99 99 99 99]
 [99  6  4  3  1 99]
 [99  6  4  3  1 99]
 [99  0  7  0 10 99]
 [99  2  2  5  5 99]
 [99  2  2  8  9 99]
 [99 99 99 99 99 99]]
(中略)
move 116: musume to (0, 1):
[[99 99 99 99 99 99]
 [99  6  4  3  1 99]
 [99  6  4  3  1 99]
 [99  7 10  5  5 99]
 [99  0  2  2  8 99]
 [99  0  2  2  9 99]
 [99 99 99 99 99 99]]

箱入り娘は、唯一コマ『娘』が所定の位置に来たらゴールなので、上記1. のタイプ (Goalclass == BYID) でよい。ただし$2\times 2$サイズのクラスのコマは『娘』しかいないので、2. (Goalclass == BYCLS) で判定することもできる。

『基本の箱入り娘』がよくできている (ような気がする) 件について

Part Iでこの後ながめるような各種のパズルについて、(Part IIIで悩む) step数最適・RLC (手数) 最適の両方で解いてみると、『箱入り娘』というのはやはりよくできているのかなあ、と思えてきた。

• 盤面がお手軽サイズ、コマが全部長方形、空隙が2個だけ
• それでいてそこそこ手数がある
• 探索候補数が適度に爆発
  • 『難しい (Twitter版) 箱入り娘』は爆発しすぎ
  • 近年の計算機使った『手数を誇る』パズルは、手数が多くても途中の探索候補数はまったく少なかったり →人間が解いているとき、選択肢は少ないのでずんずん進めるがやたら長くかかる……ので不安になっちゃうんじゃないかなあ
• Part IIIで詳しく述べるが、最適RLC (手数) 解ではstep数との乖離が大きい
  • つまり「つるつるっと一手でたくさん動かす」テクニカルな手が随所に登場する。これが面白いんでしょうなあ。手で解くと (おい(笑))
  • 下のConway先生のCenturyとかD209とか、割と近年計算機で人工的に作ったものは、RLCとstep数が近いとか、RLC最適解とstep数最適解が同一とかいうものもある

まあわしは、計算機で解くばかりで実物のパズルをひとつもやってみてないので、計算機さんの出力みただけの、個人の感想ですが (逆に『好きな動かし方』とか主観がないので、定性的な感想かも)。

L'Âne rouge (赤いロバ: フランス代表)、Klotski (木片: ポーランド? (USA?) 代表

赤いロバ、Klotskiは、コマの構成・初期配置とも、『基本的な箱入り娘』とまったく同じである。略。

Klotskiはアメリカでパテントを取っているようだが、ポーランド語の『klocki』 (木片) から来ているそうな。こういうのポーランドでお盛んなのかな、お・も・て・な・し していたポーランドのお客さん (なお電子デバイス・数学屋さん) は帰っちゃったけど、きいてみればよかった。

この後の海外のsliding block puzzlesもそうなんだけど、コマに記名がないのが多い。デバッグのときのidentifyが数字だけだとなーんか味気ないんだけど、コマに娘だの父母だの役割をもたせるのが、さすが日本は擬人化・万物に神が宿る国、なのか(笑)?

と思ったが、上記『コマクラス』で述べたように、『同じ大きさ (クラス) のコマならゴール位置を区別しない』ためのようである。『箱入り娘』などはコマIDを指定してもコマクラスを指定してもどちらでもよいが、極端な例では『Super Super Dry 2』のように、全コマ『クラス』ではあるが位置指定、というものもある。つまり、コマに名前を書かない (クラスごとに色は塗り分けたりする) ことでゴールの『形』を指定するのに一役買っているというわけである。

まあデバッグは、個々のコマに『娘』とか『大番頭』とか名前が付いているほうが、やりやすかったり感情移入 (何に？) できたりすることもあるんですけどね……。

華容道 (中国代表)

まあ同じくらいの難易度だろうから、あと中国製の『華容道』もやってみよう。

(定義略)

これも10秒未満、106手。なんか『箱入り娘・簡単版』と (構成要素は同じだが) 初期配置が対称になっていないので、難しいかと思ったら、こちらのほうが簡単なようである。

(初期バージョン・step数最適 (横軸: step数)・Macbook Pro)

『華容道』の実行ログ (初期バージョン・部分)

---lev: 0, search: 1, time: 1.1920928955078125e-06
---lev: 1, search: 3, time: 0.0005939006805419922
---lev: 2, search: 6, time: 0.0016870498657226562
---lev: 3, search: 7, time: 0.003643035888671875
---lev: 4, search: 10, time: 0.00606083869934082
---lev: 5, search: 15, time: 0.009645938873291016
(中略)
---lev: 106, search: 108, time: 9.612321138381958
@found
106 108 9.6200430393219
initial:
[[99 99 99 99 99 99]
 [99  1  2  2  3 99]
 [99  1  2  2  3 99]
 [99  4  5  5  6 99]
 [99  7  8  9  6 99]
 [99  7  0  0 10 99]
 [99 99 99 99 99 99]]
move 1: ping2 to (1, 0):
[[99 99 99 99 99 99]
 [99  1  2  2  3 99]
 [99  1  2  2  3 99]
 [99  4  5  5  6 99]
 [99  7  0  9  6 99]
 [99  7  8  0 10 99]
 [99 99 99 99 99 99]]
(中略)
move 107: caocao to (0, -1):
[[99 99 99 99 99 99]
 [99  3  1  6  7 99]
 [99  3  1  6  7 99]
 [99  5  5  9  8 99]
 [99  4  2  2  0 99]
 [99 10  2  2  0 99]
 [99 99 99 99 99 99]]

オリジナル『Century』『Century and a half』 〜 Conway先生の消息

ここから少し、数学者とかけっこー計算機をぶん回すひとたちが開発・収集したのの後追い。参考文献・ページはこの記事末尾参照。

まずは、その後の計算機sliding block puzzle追求に影響を及ぼしたと思われる『Century』から。かのConwayさんが作っている。

Century Puzzlesによると、オリジナルの「Centuryは1975年にJ. H. Conwayによって……」とある。

え? Conwayさんといったら、有名な2次元のライフゲーム (Conway's Game of Life) を考案したひとじゃないの!? いろいろやってて偉大なひとだな〜。

と、同一人物である確認をしにWikiPediaに行ってみたら、2020年にコロナが流行りはじめの頃、感染して亡くなったんですね……知らなかった。合掌……。

Centuryはゴールに2通りあって、ここでは『大きなコマを底中央に持ってくる』のをオリジナルの『Century』と呼んでいる。最初に半ブロックずれたコマを格子座標に移動させるのと、最後にまた半分ずらすのを含め(rectilinear stepsで) ちょうど100手だからだ。

もうひとつは『初期配置の回転対称にする』のが目標で、同150手なので『Century and a half』と名付けられている。
手数のキリ番が美しい。

なお縦長ブロックが『半ブロック分』ずれているので最初ビビったが(笑)、半ブロック単位の手順は最初と最後にしか出てこない。左右どちらかに寄った状態をスタート・ゴールとして解くのが定番 (半ブロック動かす手数を加えてキリ番にする)、のようである。

当初から、ゴールのタイプGoaltype.BYCLSHASHつまり全コマ (ただし互換性のある形 == クラス指定でOK) を指定位置に、というのを考えていたのは、このCentury and a halfが念頭にあったからだ。繰り返すが全コマの位置指定といっても、同一クラスのコマならどのコマでもよいが、上図の形になれば『……and a half』はゴールである。つまり『ソートされたコマクラスのハッシュ値』が一致すればよい (対して後述する『Super Super Dry 3』は、クラス一致ではなく、コマIDが指定の位置に来ること全コマ、というハードモードである)。

Super Century 〜 手数 (RLC) 最適探索にハマるきっかけ、鏡像対称メモ化の効果

『Century系』というのはこのページにまとめられている (Super Centuryは見出しの3つ目) ものだが、わしの中では、元祖Conway様のCenturyよりこちらのほうを先に手を付けてしまった。

『家系』というと吉村さんの弟子またはそのまた弟子のラーメン屋のことを指す (異論は認めない) が、『Century系』とはCenturyと同じ盤とコマを使ったものらしい。その中で『ベスト』(なにがベストなのかわからん、手数が最多?) のSuper Centuryというのをやってみる。『139手』とある。

走らせると、25秒・179 step。

Super Centuryのログ (抜粋)

---lev: 0, search: 1, time: 9.5367431640625e-07
---lev: 1, search: 2, time: 0.0005559921264648438
(中略)
---lev: 148, search: 45, time: 13.151076793670654
---lev: 149, search: 49, time: 13.210752964019775
---lev: 150, search: 54, time: 13.276472806930542
---lev: 151, search: 65, time: 13.352076053619385
---lev: 152, search: 78, time: 13.442544937133789
---lev: 153, search: 98, time: 13.558222770690918
---lev: 154, search: 104, time: 13.699177980422974
---lev: 155, search: 116, time: 13.854676961898804
---lev: 156, search: 144, time: 14.030701875686646
---lev: 157, search: 163, time: 14.24530577659607
---lev: 158, search: 168, time: 14.475951910018921
---lev: 159, search: 171, time: 14.71488904953003
---lev: 160, search: 189, time: 14.964947938919067
---lev: 161, search: 218, time: 15.22787094116211
---lev: 162, search: 250, time: 15.527404069900513
---lev: 163, search: 296, time: 15.883511066436768
---lev: 164, search: 325, time: 16.312487840652466
---lev: 165, search: 361, time: 16.821599006652832
---lev: 166, search: 384, time: 17.394818782806396
---lev: 167, search: 392, time: 18.075426816940308
---lev: 168, search: 370, time: 18.720524072647095
---lev: 169, search: 353, time: 19.31395387649536
---lev: 170, search: 363, time: 19.88574481010437
---lev: 171, search: 377, time: 20.477179765701294
---lev: 172, search: 377, time: 21.120524883270264
---lev: 173, search: 364, time: 21.770789861679077
---lev: 174, search: 373, time: 22.404168844223022
---lev: 175, search: 349, time: 23.06238579750061
---lev: 176, search: 313, time: 23.683374881744385
---lev: 177, search: 285, time: 24.25455594062805
---lev: 178, search: 236, time: 24.783572912216187
@found
178 236 24.817044973373413
initial:
[[99 99 99 99 99 99]
 [99  1  2  3  4 99]
 [99  1  5  6  6 99]
 [99  7  5  6  6 99]
 [99  7  8  8  9 99]
 [99  0  0 10 10 99]
 [99 99 99 99 99 99]]
move 1: p7 to (1, 0):
[[99 99 99 99 99 99]
 [99  1  2  3  4 99]
 [99  1  5  6  6 99]
 [99  0  5  6  6 99]
 [99  7  8  8  9 99]
 [99  7  0 10 10 99]
 [99 99 99 99 99 99]]
(中略)
move 179: p6 to (0, 1):
[[99 99 99 99 99 99]
 [99  7 10 10  5 99]
 [99  7  1  9  5 99]
 [99  2  1  8  8 99]
 [99  0  6  6  3 99]
 [99  0  6  6  4 99]
 [99 99 99 99 99 99]]

なんかグラフの形はCenturyに似ている気もする。
終盤で一挙に遅くなり、手数が爆発するか? と思いきやそのままゴール、という妙なパズルである。候補数の多少で「すいすい進む」とか「いろいろ行きつ戻りつする」とかありそうだが、わしは手でやってみていないのでよくわからん(笑)。

(step数最適・初期バージョン・Macbook Pro)

ちなみにこのとき勘違いしていて、『初期配置が非対称だからやっぱり鏡像対称の解は省いちゃいけないのか』と思い、鏡像対称をメモに入れるか入れないか切り替えられるスイッチ (ismirrorident) を作って走らせてみた。

Super Century (鏡像対称をメモ化しない) のログ (実行時間だけ)

---lev: 0, search: 1, time: 9.5367431640625e-07
---lev: 1, search: 2, time: 0.0005898475646972656
(中略)
---lev: 148, search: 127, time: 35.51076292991638
---lev: 149, search: 132, time: 35.742958784103394
---lev: 150, search: 133, time: 35.99285578727722
---lev: 151, search: 136, time: 36.249403953552246
---lev: 152, search: 136, time: 36.507960081100464
---lev: 153, search: 154, time: 36.77655792236328
---lev: 154, search: 153, time: 37.069353103637695
---lev: 155, search: 164, time: 37.37292194366455
---lev: 156, search: 194, time: 37.70674800872803
---lev: 157, search: 223, time: 38.10048294067383
---lev: 158, search: 239, time: 38.55018997192383
---lev: 159, search: 248, time: 39.14353895187378
---lev: 160, search: 282, time: 39.73849701881409
---lev: 161, search: 320, time: 40.33783984184265
---lev: 162, search: 362, time: 40.996930837631226
---lev: 163, search: 423, time: 41.75810194015503
---lev: 164, search: 474, time: 42.65225410461426
---lev: 165, search: 535, time: 43.69354605674744
---lev: 166, search: 571, time: 44.92221403121948
---lev: 167, search: 591, time: 46.227314949035645
---lev: 168, search: 595, time: 47.52691102027893
---lev: 169, search: 607, time: 48.82679104804993
---lev: 170, search: 659, time: 50.18516683578491
---lev: 170, search: 659, time: 50.18516683578491
---lev: 171, search: 695, time: 51.67356610298157
---lev: 172, search: 735, time: 53.31849408149719
---lev: 173, search: 746, time: 55.070740938186646
---lev: 174, search: 768, time: 56.91006398200989
---lev: 175, search: 744, time: 58.85155987739563
---lev: 176, search: 704, time: 60.71798396110535
---lev: 177, search: 677, time: 62.500311851501465
---lev: 178, search: 616, time: 64.18648719787598
(略)
move 179: p6 to (0, 1):
[[99 99 99 99 99 99]
 [99  7 10 10  5 99]
 [99  7  1  9  5 99]
 [99  2  1  8  8 99]
 [99  0  6  6  3 99]
 [99  0  6  6  4 99]
 [99 99 99 99 99 99]]

なんと倍以上時間は掛かっているが、手数も手順 (盤面の遷移) もぴったり同じである。びば、メモ化の工夫!!

上のグラフはごちゃごちゃしているが、紫・緑が鏡像対称をメモ化したときの候補数・時間、水色・黄色がしないときの候補数・時間。
鏡像対称な候補を枝刈りしても一定の比率でreduceできているわけでなくて、中盤から効果が出ている (水色から紫が乖離している) のが面白い。
これが一般的なはなしなのか、コマの配置が中盤以降左右対称っぽくなっているからなのかは未検証。

手数の数え方?

このパズル『Super Century』は、全手のログが入手できた。

ここでわしのstep数の定義が『手数』RLCの定義とは異なっていることに気づく。
手数 (139手) がわしのstep数 (179 step) と異なっているので、ちょっとしばらく目の子で比較してみていたが、ログをダウンロードして同一コマがつるつるっと複数動いている行(『#8. Move 2 west 2 units:』などと動いた数の記述がある行) を数えてみると……全部で29行ある。
上記Straight-Line stepsが150手、これに29手の2マス移動があるので、わしの179手と見事、一致した。よかった〜

……と思ったのは糠喜びで、これは偶然『最適step解』と『最適RLC解』が一致していたからである。

手数を世間に揃えてrectilinear stepsで数えてみようとして、他のパズルも解いてみて、猛烈にハマることになる……がそれはまた別のはなし。Part III全部費やすくらいの物語になる。

D209 〜 四角くない家の箱入り娘 (盤面)

さて上記の『4x5パズルまとめページ』にある、「四角くない盤・四角いコマでベスト」(だからなにがベスト?) なるD209を実行してみよう。あとこれ『左下隅に「娘」が行けばゴール』とのこと。なんか他のコマの配置も指定されてそうだけど、とりあえず気にしない。

この時点ではパズル定義はプログラムに埋め込んでいたが、まーこのくらいいろいろ試してると、図見ながら構造体を鼻歌でさくさく作成とかできる。もうわし、『箱入り娘毒牙職人』? (※ 後日、XMLにしますた)

『家の中に張り出した突起』も、汎用性を考えてとりあえず追加のリストに壁の座標を入れておけば良いように改造。
多くのパズルでは『長方形の移動可能エリアを削った形』になるだろう、と考えたので、張り出し部分の座標をパズル定義で書けるようにした。

(XMLで記述できるようになった後の場合)

  <board>
    <size>7, 6</size>
    <extwall>5, 4</extwall>
    <mirrorident>False</mirrorident>
  </board>

あと、家の形が左右非対称なので、先程作った『鏡像対称をメモに入れるスイッチ』 (上のXMLの<mirrorident>) をoffにしないといけない……ような気がしていたけど、どっちでも良いのかもしれない (後述)。

(定義略)

実行も、これ209手 (RLC) だからD209なんだろうけど、数え方の違いで209手で止まらないのは織り込み済み。
当社基準では292 step、32秒ほどで解に到達。

(初期バージョン・step数最適 (横軸: step数)・Macbook Pro)

グラフをみると、面白い形をしている。25と150 step付近で、ほとんど可能な解が1通りになっちってる。

D209の実行ログ (途中盤面)

move 145: p7 to dir Coords(y=0, x=-1):
[[99 99 99 99 99 99]
 [99  3  2  2  9 99]
 [99  1  2  2  8 99]
 [99  0 10 10  4 99]
 [99  6  7  0  4 99]
 [99  6  5  5 99 99]
 [99 99 99 99 99 99]]
move 146: p10 to dir Coords(y=0, x=-1):
[[99 99 99 99 99 99]
 [99  3  2  2  9 99]
 [99  1  2  2  8 99]
 [99 10 10  0  4 99]
 [99  6  7  0  4 99]
 [99  6  5  5 99 99]
 [99 99 99 99 99 99]]
move 147: p4 to dir Coords(y=0, x=-1):
[[99 99 99 99 99 99]
 [99  3  2  2  9 99]
 [99  1  2  2  8 99]
 [99 10 10  4  0 99]
 [99  6  7  4  0 99]
 [99  6  5  5 99 99]
 [99 99 99 99 99 99]]
move 148: p8 to dir Coords(y=1, x=0):
[[99 99 99 99 99 99]
 [99  3  2  2  9 99]
 [99  1  2  2  0 99]
 [99 10 10  4  8 99]
 [99  6  7  4  0 99]
 [99  6  5  5 99 99]
 [99 99 99 99 99 99]]
move 149: p8 to dir Coords(y=1, x=0):
[[99 99 99 99 99 99]
 [99  3  2  2  9 99]
 [99  1  2  2  0 99]
 [99 10 10  4  0 99]
 [99  6  7  4  8 99]
 [99  6  5  5 99 99]
 [99 99 99 99 99 99]]
move 150: p9 to dir Coords(y=1, x=0):
[[99 99 99 99 99 99]
 [99  3  2  2  0 99]
 [99  1  2  2  9 99]
 [99 10 10  4  0 99]
 [99  6  7  4  8 99]
 [99  6  5  5 99 99]
 [99 99 99 99 99 99]]
move 151: p9 to dir Coords(y=1, x=0):
[[99 99 99 99 99 99]
 [99  3  2  2  0 99]
 [99  1  2  2  0 99]
 [99 10 10  4  9 99]
 [99  6  7  4  8 99]
 [99  6  5  5 99 99]
 [99 99 99 99 99 99]]
move 152: p2 to dir Coords(y=0, x=1):
[[99 99 99 99 99 99]
 [99  3  0  2  2 99]
 [99  1  0  2  2 99]
 [99 10 10  4  9 99]
 [99  6  7  4  8 99]
 [99  6  5  5 99 99]
 [99 99 99 99 99 99]]
move 153: p1 to dir Coords(y=0, x=1):
[[99 99 99 99 99 99]
 [99  3  0  2  2 99]
 [99  0  1  2  2 99]
 [99 10 10  4  9 99]
 [99  6  7  4  8 99]
 [99  6  5  5 99 99]
 [99 99 99 99 99 99]]
move 154: p1 to dir Coords(y=-1, x=0):
[[99 99 99 99 99 99]
 [99  3  1  2  2 99]
 [99  0  0  2  2 99]
 [99 10 10  4  9 99]
 [99  6  7  4  8 99]
 [99  6  5  5 99 99]
 [99 99 99 99 99 99]]
move 155: p10 to dir Coords(y=-1, x=0):
[[99 99 99 99 99 99]
 [99  3  1  2  2 99]
 [99 10 10  2  2 99]
 [99  0  0  4  9 99]
 [99  6  7  4  8 99]
 [99  6  5  5 99 99]
 [99 99 99 99 99 99]]

なるほど定性的にはこれ『可能な手が限られる』ってことで、計算機はメモ化しながら突き進んでいて鼻歌なんだろうけど、人間が解いているときには「ああ……なんかさくさく行くけど、これでいいんだろうか???」って不安になるんじゃないかなあ(笑)。

盤が非対称なら鏡像メモはしてはいけないのか?

D209でなんとなく、盤面が非対称だから鏡像対称メモスイッチをoffにして実行していたが、実はonでも同じではないか? という気がしてきた。

• 「出っ張りに阻まれて行けない」場合: 鏡像対称な配置では家の反対側 (出っ張りがない) ところに行ったメモが残っているが、どうせ行けない。メモがムダなだけ
• 「出っ張りがない方 (出っ張りの対称位置) に行った」場合: メモは残ってないんだから行ってみる

要するに、メモに残るべき盤面が出っ張りのせいで残らなくても実害はない。メモはメモなだけで衝突判定に影響はしないので、探索時間がムダになるだけ、ではないか (逆は困る: まだこの先行けるはずの状態がメモに残ってしまう……がそれは出っ張り原因では起きないだろう)。
他のコマの配置もあるので、こんなにシンプルには考えられないのかもしれないが。

とりあえず試してみると、最適解までの到達経路はまったく同じである。
ただし、やはり途中の探索数が『鏡像対称あり』のほうが多くなっている (グラフは水色が上のグラフと同じ『鏡像対称なし』、紫が『あり』)。メモに残るべき盤面が残っていない影響だろう。面白いことに、探索時間は『鏡像対称あり』のほうが有意に速い (32秒に対して1秒くらい)。

(初期バージョン・step数最適 (横軸: step数)・Macbook Pro)

たまたまこのパズルの場合は最適解にたどり着けただけで、家の形によっては可能な経路を切っちゃう場合があるような気もしてきた。
が、暑いのでこれ以上深追いしない(爆)。
鏡像対称のメモ化をさぼっても、上記のように計算量は2倍にはならない。危なそうな場合はismirroridentスイッチを切れば良い、だけである。

Chicago/Century of Progress 〜 複数ゴールコマ、ゴールコマのクラス

ここからのパズルは、Part IIIでの冒険が終わって『RLC最適探索』でいろいろ解きまくっているときの紹介 (したがって探索基準もソルバの速度もここまでとはちょっと異なる)。

ここでクラシック・アナログな世界に戻る。Chicago (とわしが名付けた) パズルは、計算機方面ではなくパズル蒐集家らしいひとのsliding block puzzleを集めたページでみかけたものである (ページ真ん中らへんの左右ぶち抜きの写真のパズル)。1933年のものらしい。

実は同様のレトロレアアイテムは、sliding block puzzleを検索しているときeBayでオークション商品として見かけた。それも1927年製らしいので、この頃こういうパズルが流行したんだろうか。
調べるとシカゴで万国博覧会が開かれたのが1933年。折しもsliding block puzzleが流行っていたとすると、シカゴのお土産グッズにこういうものが作られたのかも。と推測。
しかしその件で100年後に計算機ぶん回しているとはな……。

さてこのパズル、オリジナルは『2x2 (EAST, WEST) のどちらかのコマを左下にもってくるとゴール』というのがオリジナルらしい。
どちらのコマをゴールに持ってくるかで手数も違うし、アレンジして2つの2x2コマを入れ替える遊びもある (同様の木製パズルでそういうのをみたことがある。URL失念につきこれと同じかどうかは不明だが)。そういった異なるゴールを定めて、いくつかXMLを書いてみた (ほとんどの部分は同じ)。

1. (いずれのコマでも早くゴールに到達したらゴールなら) ゴールコマのクラスで指定する
2. (いずれのコマか指定したい場合は)
   1. ゴールコマのIDを指定する
   2. 2つのコマは同形であるがクラスを別々のものとして、ゴールさせたいコマ (のクラス) のゴール座標を指定する
3. (応用編: 2つのコマの位置をスワップしたらゴール)

デバッグを兼ねていろいろなパターンで書いたパズル定義の要点は次のようになる (関係ない行は略)。

1. の場合 (chicago-byclass.xml):

goaltypeにbyclassを指定するだけである。この場合、どちらかのコマ (下例ではeast) にゴール座標を書くことになるが、もう一方のコマ (west) がその座標に来た場合でもゴールが成立する。つまりeast/westの形のコマ『big』のいずれか早いほうが指定位置にくる手を探索することになる。

  <board>
        ...
        <goaltype>byclass</goaltype>
  </board>
  ...
    <koma name="east">
      <class>big</class><init>1, 1</init>
      <goal>4, 1</goal>
    </koma>
    <koma name="west">
      <class>big</class><init>4, 5</init>
    </koma>
  ...

2-1. の場合 (chicago-byid-{east,west}.xml):

eastをゴール指定したい場合 (westを指定したいならそちらにgoalを書く)。1.と書き方は同じで、goaltypeがbyidになっている。

  <board>
        ...
        <goaltype>byid</goaltype>
  </board>
  ...
    <koma name="east">
      <class>big</class><init>1, 1</init>
      <goal>4, 1</goal>
    </koma>
    <koma name="west">
      <class>big</class><init>4, 5</init>
    </koma>
  ...

このケースは実は、このままただ読み込んで実行すると不都合があった。パズル定義部分の改良後 (後述) はeastとwestのクラスはXML読み込み後に自動で分けられる。

2-2. の場合:

east、westいずれもそのコマがクラス唯一のコマとなるように、別々のクラスを作って指定する。

  <board>
        ...
        <goaltype>byclass</goaltype>
  </board>
  <clssiz>
    <class name="east"><size>2, 2</size></class>
    <class name="west"><size>2, 2</size></class>  <board>
  ...
    <koma name="east">
      <class>east</class><init>1, 1</init>
      <goal>4, 1</goal>
    </koma>
    <koma name="west">
      <class>west</class><init>4, 5</init>
    </koma>
  ...

2-1. と同じゴール定義なのに、クラスが同じコマのゴールをすべて検索しなければいけないのでやや計算時間的に不利である。

3.の場合

クラス指定は2-1.と同じ(略)。複数コマのゴール座標を指定するだけ。

    <koma name="east">
      <class>big</class><init>1, 1</init>
      <goal>4, 5</goal>
    </koma>
    <koma name="west">
      <class>big</class><init>4, 5</init>
      <goal>1, 1</goal>
    </koma>

これもeastとwestでは自動でクラスが分けられる。

ID指定でクラスに複数コマがある場合!?

さて、上のページにはeastをゴールさせる場合37手 (RLC)、westが42手とある。ところが実行してみると

1. westが42手でゴールする手をみつける。どちらと指定していないのだから、手数の少ないeastのほうを見つけるはずなのに???
2. 1. eastを指定するが、ゴールまで45手かかってしまう……。
   2. うまくいく
3. うまくいく

なんかおかしい。
また、2-2.の場合と1. や2-1. の途中候補の盤面を出して、追いかけましたね……。
結果、プログラムは誤っていなかった。ただし

• ゴールタイプにGoaltype.BYIDを指定する場合、ゴールコマがクラス唯一のコマでなくてはいけない

ということに気づいた。

その理由は、目標コマと同じクラスのコマが目標コマの位置にある『盤面』 (ハッシュ値) がメモの中に存在することで、目標コマがゴールに至る最短経路のほうが刈られてしまう可能性があるからである。
したがって上記は、westがゴールするほうが残ってしまい、1. ではeastより先にwestがゴールし、2-1. ではeastが遠回りしてゴールする枝が残った、ということだった。

これを防ぐため、XML読み込み後に細工をした。

すべてのゴールコマを読み込んだ後、ゴールコマ指定のコマと同じクラスのコマが他にあれば、ゴールコマを唯一とするクラスをコピー・新設し (名前は『クラス名_2』のようになる、コマの大きさ・形状はコピー)、そちらのクラスにゴールコマを移転させる。

なおこの『クラス新設・コピー移転』は、ゴールタイプがGoaltype.BYCLSのときはやってはいけない。
ゴールコマ『クラス』が指定されているということは、コマに互換性があるということで (クラス内のどれがゴールしてもよいし、いったん通った盤面は刈っちゃってよい)、パズルの意味が違う。

例えば、クラス2にコマID {1・3・5・7} が含まれていて、コマ1にゴール座標が指定されていたとしよう。

• Goaltype.BYIDのときは: 『必ずコマID 1のコマがゴール座標に来なければならない』の意味だから
  • 新設クラス例えば6を作って、クラス2の大きさ・形状をコピーし、唯一コマID 1を所属させる (コマID 3・5・7はそのままクラス2)
  • 探索時はクラス2と6は互換性がないので、クラス6コマが取る最適ムーブを、クラス2コマの同形の盤面がメモ化にあって刈られる、ということはない (あってはいけない)
• Goaltype.BYCLSのときは: 『コマID 1と同じクラスのコマいずれかがゴール座標に来なければならない』の意味 (別にコマID 1だけがゴール対象ではない)
  • 探索時はコマID 1・3・5・7の位置を入れ替えた盤面がメモにあったら、刈ってよい (刈るべし)

その結果、無事 1.でも2-1.でもeastが37手でゴールした。

東西のゴールまでの探索時間と候補数 (最終版・RLC最適(横軸: RLC)・並列・Macbook Pro)

なんかグラフが重なっているが、37手・42手でも横軸step数は54・56とわずか2しか違わない。そこまでの探索候補は (候補数とメモ数を見る限り) まったく同じと考えられ、eastがゴールする場合でもwestがゴールする経路が、その逆もまた候補に残っているのではないかと (当たり前といえば当たり前か?)。

3. のコマ交換は、102手・141 step (これも手数最適化ありの場合) と、いささか難しめのパズルになっているようだ。

(最終版・RLC最適(横軸: RLC)・並列・Macbook Pro)

なおこのタイミングでいろいろ、XML読み込み後部分の追加をした (ゴール判定やGoaltype等のスイッチ、速度面で工夫、定義エラーの検出)。

• (既出) ゴール判定の計算量を減らすためのGoaltype.BYCLSHASH (全盤面の、ソートされたクラスのハッシュ) でのゴール判定は、手動で指定するのではなくGoaltype.BYCLSが指定されており全コマ分のgoalセクションがあるときに自動で切り替えている
  • したがってゴール判定に一番時間がかかるのが、Goaltype.BYCLSでほとんどすべてのコマクラスのゴールが指定されているが一部されていない、という場合である
• Goalby.BYCLSのとき、すべてのゴールコマが唯一クラスに所属していたらGoaltype.BYIDに切り替えた
  • (つまり上記Chicagoの2-2. パターンのゴールを2-1. として解く)
  • Goalby.BYCLSは同じクラスの他のコマもゴール座標にあるか判定するので、Goaltype.BYIDよりほんの少しだけ時間がかかるため
• コマ定義で、行または列に全0があったらエラー (下囲み)
• コマに非対称のものがあるときは、mirrorident (前述・対称盤面メモ化) は自動でFalseに

全0行・列エラー検出、鏡像対称判定

Python便利(笑)。

rprod = 1
ror = 0
for yy in range(ky):
    rb = bmpstr[kx - 1::-1]
    r = int(rb, 2)
    cshape.append(r)
    bmpstr = bmpstr[kx:]
    rprod *= r
    ror |= r
    if rb != rb[::-1]:
        puzzle.ismirrorident = False
if rprod == 0:
    print(f'bitmap of class "{puzzle.clsnam[ci]}" has row of 0')
    sys.exit(12)
if ror != (1 << kx) - 1:
    print(f'bitmap of class "{puzzle.clsnam[ci]}" has column of 0')
    sys.exit(12)

• (bmpstrには[01]以外の文字を除去した文字列が入っている。kxはコマの幅)
• rprodは全行の数値積、rorは全行の数値or
  • rprodが0なら、全0の行がある
  • rorが$2^{\rm kx} - 1$ ($1...1_2$ (kx bit)) でないなら、全0の列がある
• rbは行の2進文字列、逆転させたものと等しくない行があったらpuzzle.ismirrorident (パズル定義構造体の、鏡像を同じとみなすスイッチ) を切る

Simplicity/Simplicity 2 〜 テトリスコマも滑りたい

James Stephensさんの作による (このページの一番上)。4コマしかないが……L字のブロックが出てくる。

弊ソルバも、XMLにbitmapタグを追加して、長方形以外のブロックを定義できるようにしたので、デバッグついでにやってみた。

パズル『simplicity』 XML定義 (全文)

<?xml version="1.0"?>
<puzzle name="Simplicity">
  <!--
	  https://www.puzzlebeast.com/slidingblock/index.html
	  https://www.mathpuzzle.com/MAA/31-Sliding%20Block%20Puzzles/mathgames_12_13_04.html
  -->
  <board>
	<size>6, 6</size>
	<goaltype>byclass</goaltype>
	<mirrorident>False</mirrorident>
  </board>
  <clssiz>
	<class name="red">
	  <size>2, 2</size>
	  <bitmap>10
	          11</bitmap>
	</class>
	<class name="blue">
	  <size>1, 2</size>
	</class>
	<class name="green">
	  <size>2, 1</size>
	</class>
	<class name="yellow">
	  <size>2, 2</size>
	  <bitmap>10
	          11</bitmap>
	</class>
  </clssiz>
  <komaset>
	<koma name="red">
	  <class>red</class><init>3, 3</init>
	  <goal>1, 1</goal>
	</koma>
	<koma name="blue">
	  <class>blue</class><init>2, 1</init>
	</koma>
	<koma name="green">
	  <class>green</class><init>3, 2</init>
	</koma>
	<koma name="yellow">
	  <class>yellow</class><init>1, 3</init>
	</koma>
  </komaset>
</puzzle>

こんな感じで書く。
sizeタグで定義した$(縦\times 横)$文字分の01がbitmapに必要である。
上の例のように書くと、これまたXML的には2行に渡るものがタグに挟まれていていいのか? とも思ったが、記述が簡略になる。
01以外の文字は一切無視しているので、次のどの書き方をしてもよい (それなら文句あるまいw)。

<bitmap>10
        11</bitmap>

<bitmap>10
11</bitmap>

<bitmap>10/11</bitmap>

<bitmap>1011</bitmap>

解法的にはまあ難しいことはなく、それぞれ4・28msecほど(笑)、18手・68手 (最大候補数も10・26) で解けた。
解をみてみると、1はコマを次々循環させるように動かしていて、なかなか美しい。
同2は……床にできた窪みをどう利用するか、は、まあ予想通りでしたね　(コマの向きから予測はつくと思いますが)。

Super Dry/Super Super Dry/Super Super Dry 2/Super Super Dry 3 〜 ゴールタイプ別のデバッグ

なんかビール飲みたくなりますけど。

これら一群のパズル (定義やゴールはこちらのリンク参照)は、同じコマ構成・盤面・初期配置を使いながら (しかも2と3はゴール盤面をコマクラス配置でみるとまったく同じ)

• Super Dry: ひとつのコマのゴール位置が指定されている (クラス唯一なのでBYIDでもBYCLSでも)
• Super Super Dry・同2: 全コマクラスのゴール位置が指定されている (つまりBYCLSHASHだ)
• Super Super Dry 3: 全コマIDのゴール位置が指定されている (BYIDだがクラスが全コマ (前節) 自動新設・コピーされないと正しく動かない)

と、まるでわしがゴールの定義・判定をデバッグするために作ってくれたようなパズルである (つーか作者も計算機で解くデバッグ過程で作ったんだろうなあ)。

正直、あまりきれいな初期・ゴール配置でないし、ただただ『手数 (RLC) いくつ』というのがかなり大きいので、このクラス最大を狙ったんだろうなあ、と思っていたのだが。

まずはデバッグを満喫させていただきました(泣)。
特に、SSD3の、ゴールコマに同一クラスコマがあれば (全コマにありますがな) クラスを新設してコピーしてそっちに行く、という挙動は、(前述のChicagoのゴールタイプ・ゴールパターン別パズルと行き来しながら) 正しく動くまでプログラミングを満喫しましたねえ。

パズル探索プログラム的に面白かったのが、SD・SSDとSSD2はまあ、RLCが396・step数が521 (SSD2の場合) と非常に長い解になりながらも、最大の盤面候補数が100程度なので2〜3秒で解けるクラスであったのだが、SSD3は全然違う。ほんっとにdryでして、候補が爆発しそうになる……、全コマが所定の位置になるまですべての候補を追っているのだから当たり前?
手数基準で作者が求めた最適解が書いてあるので、すべてRLC最適で走らせてみましたが、SSD3は探索候補数は最大で5万程度 (『難しい箱入り娘』は最終400万) とそれほどでもない……ようにみえて、途中から減っていくのだけど、中くらいののろのろ運転 (1 RLCで15秒ほど) になるし、RLCベースで403・step数で537もあるので、結構30分くらい掛かって解を求めていました。
4x5 (欠けているしL字コマとかあるけど) クラスなのに、『難しい……』より時間かかる (RLC最適探索の場合)。すげえ。
メモ数は候補数が増えようが減ろうが一定量増えていく一方で、最終的に700万くらい。

(最終版、RLC最適探索 (横軸: RLC)・並列化・Macbook Pro)

これ面白いと思ったのは、RLC 330くらいで5万候補を記録した後は目減りしていく (でも1 RLC時間は速くならない)。最後は0に近づいて唯一 (とか2、3) の手順が残るのだろうと思ったら、403手目でもまだ1800以上の候補が残っている (解はそのRLCでは唯一)。なんかまだ404手かかる最終盤面とかできそうな気がするのだけど? たぶんできないんだよねえ。
またこれは、探索候補数の挙動をみる限り、ぜんぜん違う候補が (メモにない限り) 生かされて成長させられているようにみえるので、おそらく人間に解くのは無理っぽいのではないでしょうかねえ (最適解でなければ、いじっているうちに解けたりするのかも)。
まさに、計算機遊びで面白いパズルでした。

sparseなパズル

Ed Pegg Jr. さんの『Soap』は、空隙のマスが多い。

これは探索が爆発するかな? と思ってやってみたが、そうでもなかった。
なお、ゴールは『Sopaを浮かせること』とだけあるが、同ページの手数と一致するには、要するにSoapとそれ以外の横長コマの位置を初期位置と交換すること

  init:
.  .  .  .  
.  ho ho .  
ll ll rl rl 
v1 ll rl v2 
v1 so so v2 

  goal (komaclass):
.  .  .  .  
.  so so .  
ll ll rl rl 
v1 ll rl v2 
v1 ho ho v2 

のようである。

(最終版、RLC最適探索 (横軸: RLC)・並列化・Macbook Pro)

空隙が多いということは、「つるつるっ」の余地が大きくどこで止めて次の手に行ったらよいかわからないのでは……と思ったのだが、奇妙なL字のコマなど動ける余地が限られている。
最適解のログをみてみると、L字コマを寄せて大きな空隙の塊をつくる、という手続きが面白く、このテクニカルな一連の手続きに気づいてしまうと面白く解き進められるのだろうなあ、と推察できる。
また最終手で解候補が15も同時に出てきてしまう (RLC = 手数が同着最小であって、step数は異なっているかも。プログラムではその中の最小step数のものを選ぶ) というのも、他のパズルにはなかった、おそらく空隙が多いことからきている特徴である。

解けなかったパズル （1） Sliding Digits

ここからは、解けなかったパズル。

ひとつめはSerhiy Grabarchukさんの作によるSliding Digits。

3x3の『8 game』みたいにみえるが、よくみると1、3、4、7のピースに空隙がある。3分割されているので9x9で量子化した単位で動かし、空隙があるピースに他のピースの突起を潜り込ませれば解けるのか? と思ったが……。

(パズル定義dump) どっか間違ってる?

puzzle: Sliding Digits
        (y, x) = (9, 9) (including border)
        mirrorident = False
        goaltype = Goaltype.BYCLSHASH (hash = 0x1114174144477174)
koma classes:
  (# 1) 1: 1 = (3, 3)
        koma = {1, }
        o o . 
        . o . 
        o o o 
  (# 2) 2: 2 = (3, 3)
        koma = {2, }
        o o o 
        o o o 
        o o o 
  (# 3) 3: 3 = (3, 3)
        koma = {3, }
        o o o 
        . o o 
        o o o 
  (# 4) 4: 4 = (3, 3)
        koma = {4, }
        o . o 
        o o o 
        . . o 
  (# 5) 5: 5 = (3, 3)
        koma = {5, }
        o o o 
        o o o 
        o o o 
  (# 6) 6: 6 = (3, 3)
        koma = {6, }
        o o o 
        o o o 
        o o o 
  (# 7) 7: 7 = (3, 3)
        koma = {7, }
        o o o 
        . o o 
        . o o 
  (# 8) 8: 8 = (3, 3)
        koma = {8, }
        o o o 
        o o o 
        o o o 
koma:
  init:
1  1  .  2  2  2  3  3  3  
.  1  .  2  2  2  .  3  3  
1  1  1  2  2  2  3  3  3  
4  .  4  5  5  5  6  6  6  
4  4  4  5  5  5  6  6  6  
.  .  4  5  5  5  6  6  6  
8  8  8  7  7  7  .  .  .  
8  8  8  .  7  7  .  .  .  
8  8  8  .  7  7  .  .  .  

  goal (komaclass):
1  1  .  2  2  2  3  3  3  
.  1  .  2  2  2  .  3  3  
1  1  1  2  2  2  3  3  3  
4  .  4  5  5  5  6  6  6  
4  4  4  5  5  5  6  6  6  
.  .  4  5  5  5  6  6  6  
7  7  7  8  8  8  .  .  .  
.  7  7  8  8  8  .  .  .  
.  7  7  8  8  8  .  .  .  

RLC最適で34手 (step数最適で94 step) までサーチして候補残らず。解は出ませんでした。
もしかして7の空隙の定義が間違っているか、$1/3$より微妙に動かす手があるのか、はたまた斜めにコマを動かすとか?

解けなかったパズル （2） 15 game

これはルール上やアルゴリズム的に解けない、というわけではなく、当初のソルバにとっての『難しい箱入り娘』同様に現実的な時間・マシンの性能 (この効率悪いPythonソルバで) で、ということである。

Wikipediaの15 puzzle (英語版)にある図からスタートする (この図の初期配置では解けるようだ) だと

puzzle: 15 puzzle
        (y, x) = (4, 4) (including border)
        mirrorident = False
        goaltype = Goaltype.BYCLSHASH (hash = 0x111213142122232431323334414243)
koma classes:
  (# 1) 1: 1 = (1, 1)
        koma = {1, }
        o 
(以下同様・中略)
  (#15) 15: 15 = (1, 1)
        koma = {15, }
        o 
koma:
  init:
12 1  2  15 
11 6  5  8  
7  10 9  4  
.  13 14 3  

  goal (komaclass):
1  2  3  4  
5  6  7  8  
9  10 11 12 
13 14 15 .  

なんてなるが、試しに解いてみると、24手・1時間を過ぎたあたりで16MBメモリのMacbook Proが落ちてしまった (探索候補数20M・メモ43Mほど)。

---RLC: 0, cand: 1, time: 1.5735626220703125e-05, memo: 1
---RLC: 1, cand: 2, time: 0.00013780593872070312, memo: 3
---RLC: 2, cand: 4, time: 0.0003209114074707031, memo: 7
---RLC: 3, cand: 10, time: 0.0006949901580810547, memo: 17
---RLC: 4, cand: 24, time: 0.0015957355499267578, memo: 41
---RLC: 5, cand: 54, time: 0.0052700042724609375, memo: 95
---RLC: 6, cand: 107, time: 0.009956836700439453, memo: 202
---(p2)RLC: 7, cand: 212, time: 0.01872992515563965, memo: 414
---(p3)RLC: 8, cand: 446, time: 0.12513375282287598, memo: 860
---(p5)RLC: 9, cand: 946, time: 0.21081280708312988, memo: 1806
---(p10)RLC: 10, cand: 1948, time: 0.3092358112335205, memo: 3754
---(p10)RLC: 11, cand: 3938, time: 0.45229578018188477, memo: 7692
---(p10)RLC: 12, cand: 7808, time: 0.607637882232666, memo: 15500
---(p10)RLC: 13, cand: 15544, time: 0.813410758972168, memo: 31044
---(p10)RLC: 14, cand: 30821, time: 1.1347148418426514, memo: 61865
---(p10)RLC: 15, cand: 60842, time: 1.6836798191070557, memo: 122707
---(p10)RLC: 16, cand: 119000, time: 2.7721259593963623, memo: 241707
---(p10)RLC: 17, cand: 231844, time: 4.8487067222595215, memo: 473551
---(p10)RLC: 18, cand: 447342, time: 8.779008865356445, memo: 920893
---(p10)RLC: 19, cand: 859744, time: 17.945003032684326, memo: 1780637
---(p10)RLC: 20, cand: 1637383, time: 35.369072914123535, memo: 3418020
---(p10)RLC: 21, cand: 3098270, time: 80.90650177001953, memo: 6516290
---(p10)RLC: 22, cand: 5802411, time: 267.18290877342224, memo: 12318701
---(p10)RLC: 23, cand: 10783780, time: 923.3397507667542, memo: 23102481
---(p10)RLC: 24, cand: 19826318, time: 3426.6103699207306, memo: 42928799

当たり前だが探索候補数は爆発する一方で、初期状態ではステップごとに2倍強に増える→だんだん落ちてくる、という流れになっている。
まあ、23手くらいの手数で到達する初期配置だったら解けるかもね、という感じで、コマサイズも一定しているし、計算機で解いてみてあまり面白いパズルではないと思う。

しかし数学的には解析可能性が高いってことは面白いんだろう、さすがに古典の有名なパズルなので (上記事のほか、MathematicaのWolframさんのページ。参考文献が凄い) 解析されているようだ。

• NP困難だそうだ。4x4だったら、$16! / 2 \simeq 1.0$T候補程度なので、メモリ効率と速度があるソルバだったら、全探索でも解けるかもしれない
  • 上記実行例だとメモ43Mと25000倍程度なので、(メモは倍々で増えているので) あと14ステップくらい解ける速度とメモリ効率があれば、どんな候補でも解けるのかも
• そうでない場合は (Part IIでもちょっと触れるが)、こういうのはヒューリスティクスの導入が必要、ともある (もちろんその場合最適解とは限らない)
  • コマの目的位置までの距離 (taxicab distances) の合計を評価値にするのが普通、だそうだ

(※ 2025. 8. 2補足) 15ゲームに関しては、それ専門ガチ勢がいっぱい。見て回っていたらこんな論文があった……。

• R. Korf, P. Schultze, "Large-Scale Parallel Breadth-First Search," (2005).

って論文巻末P. 6の表、上のログ (※ 全部掲載しました) そのものじゃん!? (爆)
この続き、最大777G候補!? 80 step?
ううむ……汎用ソルバで解こうってのが間違いでした。

2005年にこれって、このひとガチ勢だわwww 斜め読みすると、並列・RAID・長期走らせるためのエラー検出とか、円周率ガチ勢と同じようなキーワードが並んでる。

Correct Order 〜 8ゲームではどうか？

3x3の8ゲームではどうか。まあこれは規模からいって解けるだろう (可能な盤面の総数は$9!/2 = 181440$)。

ちょっと違うのだが、下のようなパズル『Correct Order』(Serhiy Grabarchukさん作) をみかけたので、解かせてみた。単なる3x3の8ゲームだが、下にshuttleと名付けられた2コマ幅のブロックがある……というより、前のSimplicity 2のように下に1つの『穴』があり、それが左右にスライドするという趣向だ。

Facebookの投稿では、8〜1がまったくの逆順からスタートしているので、それを初期配置としてみた。
Macbook Proでも2分ほど、42手 (RLC最適探索) で解ける。
探索候補数の最大が320K、メモ数が最終3.6M程度なので、(盤面が広いしshuttleコマがあるので) 8ゲームの盤面総数よりちょっと (1〜2桁) 多いくらいの盤面総数とすると、8ゲームを全探索しているような感じだろう。
shuttleブロックは最下行で水平移動しているだけなので、やはり『最下行左右どちらかのブロックを抜いた』8ゲームと等価なものと考えて解けるようだ。

この記事は続く

なんか、この後の並列化とヒューリスティクスの導入検討・そして力技で『難しい箱入り娘』が解けた!! ってとこまで書いたら、長すぎるってZennに怒られた。

ので、Part IIに続きますよ。

参考文献・ページ・プログラム

※ sliding block puzzleについては、いろいろな計算機屋さんや数学屋さんがさんざ取り付いていて (かのKnuth先生や、ライフゲームで有名なConway先生もらしい)、アカデミックな考察とかはそちらに任せる。

• Red Donkey: 基本の箱入り娘 (Klotski) に関する考察。一番下の参考文献リンクが、界隈の主だったひとたちのところに張られていて、便利かも
• Math Games: これも参考文献リンクが凄い
• Nick Baxter's Sliding Block Puzzle Pageに、ありとあらゆるsliding block puzzle (いわゆる15ゲームや箱入り娘の変形) が収集されている。
  (基本的な) 箱入り娘は、4x5 Tray Sliding Block Puzzlesという群に属しているらしい
• 計算機屋さんにも凄い人とかいて、ここ同様の考察とか、『4x5クラス』のパズルを全生成→探索してみたとか (2012ごろの記事・Part 2が見つからない???):
  • Sliding Block Puzzles
  • Sliding Block Puzzles, Part 3
  • Sliding Block Puzzles, Part 4 of 3
• 検索している途中で気づいたが、いくつか優秀なsolverを書いている方がいらっしゃる
  • Githubにブラウザ上で実行できるsolverがある。4x5・コマサイズはKlotski互換・空隙数2 (でアルゴリズムをなにか最適化しているのかな?) 限定、手のリストが得られないのが残念
  • 上記Math Gamesで紹介されている、Taniguchi Solver: みつからなかった。見た目がWindowsソフトだし、2007頃の?
• The Complexity of Sliding-Block Puzzles and
  Plank Puzzles: ロジック回路との等価性など、Plank puzzleという別のパズルも紹介
• Sliding block puzzles: ある大きさ・コマ構成のすべてのパズルについての、最大グラフ距離 (手数) の探索と考察