ペントミノパズルを解く（深さ優先探索法、Dancing Links法）

2023-05-12
#puzzle

頭の体操と余興として、ペントミノ（５つの四角形）を並べて長方形を作るパズルを解くプログラムを書いてみた。

動作環境：MacBook Air 2020（CPUのスペックわからず…）

ss

リポジトリ：tyfkda/PentominoSolver

ペントミノパズル

ペントミノは四角形を５つ繋げた形で、表裏・回転を同一とすると12種類の形状がある。 これらを1個ずつ使って長方形を作るというパズル。 ペントミノが合計で5x12=60の面積なので、6x10、5x12、4x15、3x20、そして8x8の中央4マスを抜いた形でそれぞれ解が何通りあるか調べる。

各ピースは表裏反転や90度回転させることができるので、最大8パターンの置き方がある。

人間が解くには１つでも難しすぎるが、コンピュータならすべての組み合わせを列挙してやれば力技で一応解ける。 ただそれだとものすごく時間がかかるので、なんらかの対応が必要になる。

SATソルバーを試してみる（失敗）

例によって専用のソルバーを書くんじゃなくてSATソルバーに解かせようとした。 パッと思いついたのはピースを軸に考えて、

  • 各ピースの反転・回転ごとに盤面の各位置のどこかにある、という条件が１つだけ成り立つ
  • ピースのペア全てでお互いが重ならないようにするため、一方のピースがこの位置の場合、他方がこの位置じゃない、という条件を列挙

という論理式を組み立てれば解けそう。 npmのLogic Solverでやってみたが、スタック溢れで解けなかった。

Pentomino Packing – Fishletを参考に、逆に配置先のマスを中心に考えて、

  • 盤面の全マス60箇所について、12種類のピースのどれか１つだけが占める
  • 各ピースについて、ある反転・回転でこの位置ならば、この５つのマスを占める

という具合にやってみたが変わらず。 TOTAL_MEMORYを書き換えて無理やり動かしても、最初の解は（54秒かかって）得られるがその後が返ってこなかった。

以前数独などは同じLogic Solverで解けたし、それらと比べてそんな問題が複雑なわけじゃないと直感的には思うんだが…。

手動でソルバーを書く（深さ優先探索）

しかたがないので手動でペントミノを解くソルバーを作ってみる。 解く手順は、まだ使用してないピースを置いてみるというのを再帰的に繰り返して、すべて置けたらそれが解の候補、というのをすべてのパターンについて調べる。 行き詰まったら以前に置いたものを取りやめて別のケースを試す（深さ優先探索）、というのを全ケースについて調べる。

SATソルバーを利用する場合とは違って、配置先の例えば左上から順に収まるピースを入れていく、という方針にする。 こうすることで前半に好き勝手に配置して後半行き詰まる、となる前に早めに枝刈りができて高速化が見込める。

バックトラッキング・深さ優先探索というのをあまり組んだことがなくてほぼ初挑戦な感じ。 副作用嫌いとしては探索していく際に盤面の状態を複製してダメだったら捨てるという方式にしたいところだが、とにかくチェックする盤面が多いので避けた方がいいだろう。 ピースを置いたら盤面を書き換えてダメだったら元に戻す、という方式にする （ビットボードで持ってれば60ビットで済むのでコピーでもよさそうではある）。

対称の解をはじく

盤面を上下左右対称の配置は１通りの解として数える （8x8の正方形の場合は回転も含める）。 重複をチェックするために盤面を文字列化してHashSetに登録して同一判定を行った。

対称になる解の探索を早めに打ち切れれば高速化できそうだけど、うまい方法思いつかず…。

高速化

最初次のピースの位置を長辺方向に調べていたがそれだと遅くて、短辺方向の方が早くに行き詰まり枝刈りできてお得。 動かしてみると全ての解2,339通りを求めるのに2.6秒程度（探索盤面数2,584万）、まあこんなもんか。

ペントミノを解く の 第5章 C言語版の高速化あれこれ を参考にして、 ピースXは反転・回転がどれも同じ形で１種類なことを利用して、盤面の左上部分に先に配置してしまうようにすると、0.4秒程度（探索盤面数325万）に短縮された。

他になにか高速化できる手段がないかとググっていると、なにやら「Algorithm X」「Dancing Links」という方式があるらしい。 ドナルド・クヌース先生が2000年に発表したアルゴリズムらしく、「Exact Cover Problem」という、条件を満たす重複なしの候補の組を調べるのに使えるらしい。 名前がカッコよすぎて興味そそる…。

アルゴリズムの肝は、双方向リンクリスト（次だけじゃなく前のリンクも辿れる）の要素を取り除いた時に、取り除いた要素のリンクをクリアせずにそのまま取っておけば簡単に元に戻すことができる、ということを使うとのこと。 言われてみれば「なるほど確かに！」と感心する。

あとはExact Coverを満たすために、行列の列が条件、行が候補として、ある条件列に対してどの候補を選ぶか、というのを調べるために、ある候補を選択した場合はそいつが満たす条件を効率よく除外できるようにしている。 すでに満たされた条件と被る候補はリンクから除外されるので探索せずに済む。

ペントミノパズルの場合、条件（列）は「盤面の各マスを埋めるピースが１つ」と「ピース12種類が１回ずつ使われる」（計60+12=72）、 候補（行）は各ピース・反転・回転が盤面のある位置にあった場合（大まかに12（ピース）x2（反転）x4（回転）x6x10（盤面）=5,760）、となる。

Rustのdancing-linksクレートを利用しただけで内部動作を完全に理解したわけではないけど、（ピースX処理をしない状態と比較して）手動で組んだ場合より速くなるというわけではないっぽい？ 手動で組んだ場合には左上から順に調べていって行き詰まったら枝刈りができるけど、Dancing Linksは汎用的なアルゴリズムなのでそのような特殊化が入らないはずなので （すべての解を求めるのに4.4秒程だった）。

論文には手動で組んだ場合に遜色ないようなことが書かれているので、なにか勘違いまたは実装間違いしてるかも知れず （ちょっと論文の要点が掴めず…）。

参考

関連記事

新着記事