数独とかナンバープレイスとかで呼ばれるパズルを解くアルゴリズムをPHPで書きました。
https://github.com/hanhan1978/sudoku
数独自体のルールについては、数独 - Wikipedia とかを見てください。電車の中で紙の問題に鉛筆で解答している方を、ちらほら見つけられる程度には有名なパズルです。
アルゴリズムの解説
100％正しい情報なのかと言われると怪しいのですが、数独はある程度の難易度になると、理詰めでは解けない状態になります。そのため、仮置きという戦略を使って、入りうる数字を次々に試していって、矛盾が出なければ正解という解き方をします。
このソルバーでは、人間が自然に数独を解いていく方法をなるべく再現するようにして、プログラムを書いてみました。
理詰めロジック x3
仮置きで、すべての数字を洗い出すことは可能ではあるのですが、組み合わせ爆発が起こってしまい計算時間が非常に長くかかってしまいます。そのため、ある程度は理詰めで解けるように３つの理詰めロジックを用意しました。
1. ユニーク
https://github.com/hanhan1978/sudoku/blob/master/src/Solver/Unique.php
縦一列、横一列、3x3マスの中で、一個しか入りえない数字を探します。数独でもっとも基本的なルールです。画像の例では、最上段の右から2番目のマスに入りうる候補は8以外無いことがわかります。
2. ペア
https://github.com/hanhan1978/sudoku/blob/master/src/Solver/Pair.php
縦一列、横一列、3x3マスの中で、同じ数字2つが候補になった2マスがあった場合、他のマスからその2つの数字は候補から外せるというロジックです。
下記例では、下から2段目の行に4, 5 しか入りえないマスが2つあります。特定は出来ないが、他のマスの候補から4, 5をなくすことが出来ます。結果として、赤字で記した数字が一気に特定できました。
3. 孤児
https://github.com/hanhan1978/sudoku/blob/master/src/Solver/Orphan.php
１つのマスに注目した上で、縦一列、横一列、3x3マスの中で、そのマスに入る候補が複数あるが、そのマスにしか入らない数字が1つである場合、そのマスに入る数字が特定出来るというロジックです。このロジックは意外と強力で、仮置きが必要にならないレベルの数独であれば、基本的にはコレだけで解けます。
下記例では、中段の3x3マスで、各マスに対して全候補を書き出しています。右側に4, 5, 7を候補とするマスがありますが、7はこのマス以外には候補にありません。結果として、このマスには7が入ると特定出来ます。
仮置きロジック
https://github.com/hanhan1978/sudoku/blob/master/src/Solver/Guess.php
DFS - Depth First Search（深さ優先探索）で試行していきます。マスを順番に走査して、候補になる数字を仮置きして数独を解いて、矛盾が出たらその一つ前に戻って仮置きをやり直すというロジックです。
前述の通り、組み合わせ爆発が発生しますので、一つのノードの探索をどれくらい速く終わらせられるかというのが鍵になります。そのため、今回のソルバーでは仮置きをしたあとに上記3つの理詰めロジックを実行して、速やかに矛盾を特定して探索をやめるという方式を採用しています。
パフォーマンス計測
上記リンク1番のナンプレ世界最難問を使ってパフォーマンスチューニングをしてみました。一部のロジックで array_search array_shift など計算量が多いロジックを一部使っていたので地道に解消したところ、126ms までいきました。これ以上は、オブジェクトを潤沢に扱う今回のアーキテクチャーでは難しいかもしれません。
まとめ
数独自体が、頭の体操として楽しいのですが、仮置きしないと解けない数独はコンピューターに任せたほうが絶対に効率がいいなと思っていました。4年ほど前にチャレンジしたときは、そもそも仮置きアルゴリズムを実現することも出来ず失敗したのですが、LeetCode で培った経験が活きたようで、今回は作り上げることが出来ました。
アルゴリズムの種類としては、「深さ優先探索」のみで解答出来るので、それほど面白みがないと思うかもしれませんが、数独自体のルールや理詰めの方法論の有無で効率が変わってくるというあたりが少し変わっているかもしれません。
※余談ですが、巷のソルバーの中には組み合わせ爆発上等で全パターンを試行するソルバーが結構多いです。解けるけど時間がかかる、という感じのものが多かったです。
参考とか
Maximum Depth of Binary Tree - LeetCode
今回のアルゴリズム解説に出てきたDFS（深さ優先探索）については、この問題で勉強すると良いです。BFS（幅優先探索）でも解けるので、その両方が一気に体験できるお得な問題です。
wand2016/sudoku-solver: inspired by https://twitter.com/hanhan1978
@d_horiyama_webさんが作成したソルバー。私より後で作り始めて、私より先に完成しててすごい。
ダイクストラ法 - Wikipedia
ついでに出てきた話題の最短経路探索アルゴリズム。勉強中。
Top Interview Questions - LeetCode
LeetCode の、面接でよく使われるという質問集。この上位20くらいやると少しレベルが上がる。