はじめに
綾瀬川技術室のみなさんと数独ソルバー対決をしました． ルールは前編を見てください．
盤面作成
プログラムで解く上で時間がかかる数独の盤面を作る必要があります．これはどんな盤面でしょう？
なるべく空きマスが多い方が良いのでしょうか，ですがまっさらな盤面だと適当に埋めていくだけで正解ができてしまいます．プログラムで解く上で，例えば 2 択を外すとその先頑張って埋めても正解に辿り着けないような盤面にしたいです．
人力でそのような盤面を設計することを諦め，プログラムでそのような盤面を作成しました． コンピュータで盤面を作成するためには，評価関数を作る必要があります． 評価関数として，自前のアルゴリズムのステップ数を用いました．
いくつかアルゴリズムを設計し，それに対してキラーケースを作成するようにしました．ですが，単一のアルゴリズムにのみ刺さる手法だと，例えばプログラム中の > が >= になるだけで通用しなくなってしまいます．
そこまで相手の戦略を読み切ることはできないので，キラーケースをやや汎用的にする工夫として，探索順をランダムにしたアルゴリズムに対してキラーケースを作成するようにしました．
探索順をランダムにすることにより，ただの山登り法を実装しても焼きなまし法のように特定の解に嵌まりにくくなります．
具体的には，完成された盤面を入力とし，その盤面へのマスクを山登りしました． 探索順をランダムにしているので，評価用のスコアを計算するのに 10 回繰り返し，毎回の計算にかかったステップ数の平均値をとります． 毎回のステップについて，マスクを変化させなかった場合のスコアと変化させた場合のスコアを計算し，もしスコアが上昇する場合マスクを変化させるとします．
数独ソルバー
特定の手法に対するキラーケースを作成することは上に述べた手法でできました． しかしながら，特定の手法に対して強い（探索順をランダムにする程度では対応できない）ケースも，他の手法を用いると簡単に短時間で解けてしまうことがわかりました． 複数手法どれについてもステップ数が多くなるように，同様の盤面生成を試みましたが，そのような盤面は見つからず，汎用的なキラーケースを見つけることができませんでした．
逆に，そのようなキラーケースが作れないのであれば，単純な戦術であっても 2 つ組み合わせて交互に計算を進めるようにしてやればどんな盤面でも高速に解くことができます．
戦術として，2 つを組み合わせ，計算途中に入れ替えながら進んでいく手法を取りました． ざっくり言うと，マスに数字を割り当てる手法と，数字をマスに割り当てる手法です． それぞれの中で高速に動作するように多少の工夫はあります． ビット演算を用いたり，候補数が少ない方から優先して割り当てていくなどをしています． ですが，組み合わせるというところが高速化には（そしてキラーケースで落とされないためには）重要です．
結果
実行結果は長いので記事の一番下に置いておきます．
実行時間の平均とか実行時間の log とった平均とか計算しようと思いましたが，計算せずとも順位が明らかだったので順位は以下になりました．
| 順位 | |
|---|---|
| 1 位 | 一之瀬（筆者） |
| 2 位 | 鮎 |
| 3 位 | taisa |
私が作ったケースを入力とした時に，実行時間がかかりすぎて測定できなかった場合がありました． これは，プログラムを回して作ったケースではなくて，手で作成した以下のようなケースです．
?????????
???1?????
???????1?
?1???????
??????1??
?????????
????1????
??1??????
?????????
この盤面では，1 を必ず埋めなければいけない場所が 3 箇所存在します．
これを埋めるのに失敗した場合，その箇所に他の数字を埋めてしまい，いつまで経っても計算が終わりません．
如何にプログラムでケースを作るかの話をしたのに，結局人力で作成したケースの方が刺さってしまった． 枠が余ったのでとりあえず置いてみただけだったが，そんなこともあるんだなあ．
おわりに
前編にも書いたけど同じことを書きます．
今回作成したソルバー，盤面，計測用スクリプトを GitHub に置いています．
今回作成したソルバー（の一部手法）を TypeScript に移植して，Web サイト上でも遊べるようにしました． こちら から試せます．
数独ソルバーとして 2 つの手法を組み合わせるのが高速だと本編で書きましたが，それはあくまで 1 つの解を見つけるまでの話です． Web サイトに実装した版では解が複数ある場合，順々に見つけていけるようにしているので，1 つの手法のみで探索をしています． 数字をマスに割り当てる手法のみで実装していますが，候補数の小さい方から探索するなどといった工夫は入れているので，それなりに早いとは思います．
実行結果
| ケース | taisa | 一之瀬（筆者） | 鮎 |
|---|---|---|---|
| taisa-01 | 0.01135 | 0.01188 | |
| taisa-02 | 0.01119 | 0.01195 | |
| taisa-03 | 0.01061 | 0.01177 | |
| taisa-04 | 0.01124 | 0.01122 | |
| taisa-05 | 0.01041 | 0.01225 | |
| taisa-06 | 0.01043 | 0.01175 | |
| taisa-07 | 0.01077 | 0.01132 | |
| taisa-08 | 0.01052 | 0.01140 | |
| taisa-09 | 0.01021 | 0.01125 | |
| taisa-10 | 0.01021 | 0.01140 | |
| 一之瀬-01 | 0.01331 | 0.01198 | |
| 一之瀬-02 | 0.01168 | 0.01183 | |
| 一之瀬-03 | 0.46516 | 0.01218 | |
| 一之瀬-04 | 0.02269 | 0.01161 | |
| 一之瀬-05 | 0.01256 | 0.01218 | |
| 一之瀬-06 | 0.01124 | 0.01464 | |
| 一之瀬-07 | 0.04327 | 0.01153 | |
| 一之瀬-08 | 0.01199 | 0.01221 | |
| 一之瀬-09 | 測定不能 | 0.01144 | |
| 一之瀬-10 | 測定不能 | 0.01186 | |
| 鮎-01 | 0.01138 | 0.01010 | |
| 鮎-02 | 0.01190 | 0.01020 | |
| 鮎-03 | 0.66210 | 0.00971 | |
| 鮎-04 | 0.01138 | 0.01054 | |
| 鮎-05 | 0.01166 | 0.00998 | |
| 鮎-06 | 0.01370 | 0.01036 | |
| 鮎-07 | 0.01135 | 0.00980 | |
| 鮎-08 | 0.01134 | 0.00969 | |
| 鮎-09 | 0.01143 | 0.00999 | |
| 鮎-10 | 0.01214 | 0.01008 |