数独を解くやつ作ってみた
今日はアルゴリズムのおはなしです。
経緯
もともと私はパズルゲームなんかは好きこのんでやる方ではないのですが、数独だけは学生時代、狂ったようにやっていた時期がありました。
プログラミングに初めて触れたのもちょうどその時で、中級レベルの問題に少し飽きていた時分「だったら自動で解かせればよくね？」と思い、自動解答ツールを作ってみたのです。
が、アルゴリズムの不備で難問が解けないクソヘッポコ仕様であることが後に発覚し、作り直すのも億劫になったのでそれからずっと放置プレイになってました。
そんな折（もう7～8年は経っていますが…）最近購読している Software Design 8月号 にグラフ探索を使った数独ソルバーなるものが紹介されており、久々にモノづくりのソウルが燃え滾ってしまったので作ってみることにしたのでした。
作ったもの
C++版
Python版
なお、記事を執筆された方のプログラムも以下にありました。
しくみ
数独の盤面をツリー構造のグラフにモデル化して、それを深さ優先探索（Depth-First Search: DFS）で辿っていって、ルールに矛盾しないゴールを探し当てていくというものです。つまり総当たり戦です。
解いてみた
Pythonで実装した版で試してみます。
こんな感じのテキストファイルを作って……
53**7****
6**195***
*98****6*
8***6***3
4**8*3**1
7***2***6
*6****28*
***419**5
****8**79実行します。
(.env)$ python .\main.py sample.txt
File: sample.txt
1 results, 0.0095 sec
No.1
-------------------------
| 5 3 4 | 6 7 8 | 9 1 2 |
| 6 7 2 | 1 9 5 | 3 4 8 |
| 1 9 8 | 3 4 2 | 5 6 7 |
-------------------------
| 8 5 9 | 7 6 1 | 4 2 3 |
| 4 2 6 | 8 5 3 | 7 9 1 |
| 7 1 3 | 9 2 4 | 8 5 6 |
-------------------------
| 9 6 1 | 5 3 7 | 2 8 4 |
| 2 8 7 | 4 1 9 | 6 3 5 |
| 3 4 5 | 2 8 6 | 1 7 9 |
-------------------------
--------------------------------------------------
Complete!!
--------------------------------------------------
Elapsed Time: 0.0095 sec経過時間が2つ出ているのは複数ファイルを読ませて一括実行に対応しているためです。Elapsed Timeがトータルの処理時間になります。
高速化
グラフ探索は理論はシンプルですが、問題の空きマスの数に比例して処理時間がかかってしまいます。参考にさせていただいた数独問題サイトの問題を拝借したところ、中級レベルでは0.7秒だったのに対し、最高レベルの1つ下の専門級レベルでは110秒もかかってしまいました。
そこで、これも記事に従って、高速化を実装していきます。今回は
- 対策１）入れられる数字の選択肢が少ないマスから埋めていく
- 対策２）一意に決まるマスはあらかじめ埋めておく
どちらも人間が手で解いている分には当たり前といえますが、この概念をプログラムにも組み込んでみます。
対策１）入れられる数字の選択肢が少ないマスから埋めていく
下記のような問題を考えます。
それぞれの空きマスに入る選択肢の数は、以下のようになります（分かりやすくフォントを変えています）。
初期状態のアルゴリズムでは (0, 0) すなわち左上から処理を進めていくわけですが、選択肢の数が少ないマスから順に数字を確定させていった方が効率いいですよね。なのでこの場合は選択肢の数「3」のマスから処理します。
対策２）一意に決まるマスはあらかじめ埋めておく
これもまぁ当然っちゃ当然ですが、「数字の配置を見たらこのマスにはこの数字しか入らない」もしくは「このブロックのこの数字はこのマスにしか入らない」と分かっているものは先に処理するのがよいでしょう。
さっきと同じ問題です。
この時点で下の赤太字が埋まります。
結果
ベンチマーク比較です。先のサイトの最高難易度の8月分を30問解かせてみました。
まとめ
ゴリゴリ書くの楽しいよ！！！！！みんなでゴリゴリ書こうよ！！！！！！！！
