数独ソルバーを実装しています。数独の問題を標準入力として与えるとそれを解いて出力します。
数独は、3 × 3 ブロックに区切られた 9 × 9 の正方形の各マスに 1 から 9 までの数値を入れるペンシルパズルです。縦・横の各列および、太線で囲まれた 3 × 3 のブロック内には、同じ数値が複数入らないようにします。
図:数独の問題例 ( https://en.wikipedia.org/wiki/Sudoku ) と、その解答
- Sudoku.cpp を C++11 上でコンパイルして実行します。
- Wandbox 上の gcc 10.1.0 で動作します。
- 「9 × 9 の文字列」の形式で、標準入力から数独の盤面を与えます。
- 文字 '*' は空白マスを表します。
53**7****
6**195***
*98****6*
8***6***3
4**8*3**1
7***2***6
*6****28*
***419**5
****8**79
- 一意解の場合は、たとえば先述の入力例に対しては、以下の結果を出力します。
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
- 解なしの場合は "no solutions." と出力します。
- 解が複数個ある場合は "more than one solutions." と出力します。
- ベンチマークとして、ニコリ「数独名品 100 選」 (文藝春秋、2006年) に掲載されている問題 100 問を使用しました。
- 100 問すべてを解き切るのに要した時間は 2.65 秒 (1 問あたり平均 0.00265 秒) でした。
なお、計算実行環境は、以下の通りです。
- MacBook Air (13-inch, Early 2015)
- プ ロ セ ッ サ:1.6 GHz Intel Core i5
- メモリ:8GB
ソルバーのベースは、深さ優先探索 (バックトラッキング) です。探索順序の工夫や枝刈りなどを行うことで高速化を図っています。詳細については下記の参考資料に書かせていただきました。
以下の連載記事に詳細の解説を行っています。
- 技術評論社:Software Design 2020年8月号
- https://gihyo.jp/magazine/SD/archive/2020/202008
- 【新連載】パズルで鍛えるアルゴリズム力 【1】「数独ソルバー」で,汎用的に使える探索アルゴリズムを学ぶ ……けんちょん(大槻 兼資)
These codes are licensed under CC0.