数独をプログラムで解く

数独（SUDOKU)をプログラム (Ruby) で解きます。

アルゴリズム

マスを前から見ていって、空欄のマスに1, 2, ..., 9の順で置けるかどうか試します。

• 置けるならその数字を置いて次のマスを見る
• どの数字も置けないなら、いままでの数字の置き方がまずかったということなので前のマスに戻る

これで解けます。

$9^{81}$通りくらい試すことになりそうですが、いい感じに枝刈りされてすぐに答えが出ます。

Demo

アルゴリズムの動作のイメージはこんな感じです。

https://ia7ck.github.io/visualization/backtracking/sudoku/index.html

ソースコード

github.com

データは 1 million Sudoku games | Kaggle のものを使いました。