概要

数独ソルバーを実装しています。数独の問題を標準入力として与えるとそれを解いて出力します。

数独は、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】「数独ソルバー」で，汎用的に使える探索アルゴリズムを学ぶ ……けんちょん（大槻 兼資）

　

License

These codes are licensed under CC0.