作ったもの
動機
WEBで適当に「数独 ソルバー」と検索すると先人たちのソルバーがヒットするのですが、ブラウザ上で動作するものをいくつか使ってみると（いわゆる）「仮置き」に対応していなくて途中で計算を打ち切ったり、複数解持つ数独は解かない仕様となっていました（人が楽しむ上で数独の答えが複数解あるものはあまりよろしくないと思いますが、数独の定義に「唯一解である」はない……と思う）。 インストール形式の数独ソルバーもいくつかあったのですが、ちょっとした数独の確認のためにインストールするのもうーん……だったので、以下の要望を満たすソルバーを作りました。
- 仮置きに対応してちゃんと最後まで解く
- 複数解ある場合でも最後まで解いてひとつの解を出力する
- ブラウザ上で動く
数独ソルバーの作り方（雑）
DFS（深さ優先探索）が書けるならソルバーを書けます。
以下、雑なアルゴリズムです。
- 【ステップ1】：マスに入る数字の候補が1つしかない場合、その数字で確定させる
- 【ステップ2】：マスに入る数字の候補が複数ある場合でも、どの縦、横、3x3マス内にもない、自分しか持っていない候補の数字を持っているなら、その数字で確定させる（たとえば自分のマスの候補が「1,2,3」で、縦、横、3x3のどのマスも3を候補に持っていないなら、自分は3で確定）
- 【ステップ3】：確定するマスがなくなるまで【ステップ1】に戻る。
- 【ステップ4】：確定するマスがなくなり、かつまだ全マス埋まっていないなら、最も候補数字の少ないマスをひとつ見つける。そのマスの候補数字の1つを「仮置き」して、【ステップ1】へDFSで再帰する。仮置きした数字で全てのマスが埋まらないなら、他の候補数字を仮置きして同様に再帰させる。
- 【終了条件】：【ステップ3】または【ステップ4】の過程で全てのマスに数字が埋まったら数独が解けた。埋まらなかったら数独は解けなかった。
DFSで深い探索になるとStack Overflowになる可能性があるので、「仮置き」する前に確定できるマスがあるなら埋める、というのが良いソルバーのコツでしょう。調べた感じX-wingなど様々な方法がありましたが、今の所基本的な【ステップ1】と【ステップ2】で解けています。
一番難しかったのはJavaScriptでした
TypeScriptで数独ソルバーを書いたのですが、数独ソルバーのアルゴリズム云々よりも、ブラウザで動作させる以上非同期処理を逐次処理に置き換える作業が必要になってきます。VSCodeでデバッグのやり方もようわからんし、配列をコピーしたいだけなのにJSON.parse(JSON.stringify())しろとか言われるし、Setのdeepcopyはそれに対応してないから自分で作らないといけなかったり、いわんやArray<Array<Set<number>>>の場合をや……など、JavaScriptはDOM操作をする言語であってデータ構造をいじる言語ではないと思いました。次にソルバーを書くならRustで書いてwasmで処理させると思います。
おわりに
Arto Inkala氏が作成した世界で最も難しい数独や、Hiroshi Watanabeがスパコンで作成した数独や、全空白の数独なども解ける数独ソルバーを作りました。
「この問題解けるはずなのに解けてないよ～」等の不具合があれば、数独ソルバーサイトの「不具合報告」からお願いします。
