トイザラスに売っていたsudokuゲームのスージアムを見てからsudokuに興味を持つ。究極の左脳パズルとわれるだけあって、非常に論理的に解答が得られる。ということは比較的単純なalgorithmで表現出来るはず。ということでsudoku解答algoを考えてみた。で、そいつをC++で実装してみた。ネットに転がっているsudoku問題の全てを試したわけではないが、今のところ全問正解。
sudokuの前提条件
- 9x9マスで、各マスのとりうる値の範囲は１から９
- 一つの行には値が重複して存在しない
- 一つの列には値が重複して存在しない
- 9x9マスを3x3マスずつに分割したエリア内には値が重複して存在しない
algoの基本的な考え方は、まず、全てのマスにとりうる値の可能性（１から９）を設定。条件を与えて（sudoku問題で最初から与えられている値）、可能性を絞っていく。そのマスの可能性が一つにまで絞られれば、そのマスの値が固定される。最終的に全てのマスが固定されれば終了。
1)初期化：9x9マスのとりうる値の可能性を１から９に設定
2)条件を一つ与えて（＝問題にかかれている初期値を一つ設定）、その一つのマスの値を固定する
3)一つの行には値が重複して存在しない。値が固定されたマスの行の残り全てのマスの可能性から、その値を削除する。
4)一つの列には値が重複して存在しない。値が固定されたマスの列の残り全てのマスの可能性から、その値を削除する。
5)9x9マスを3x3マスずつのエリアに分割（合計９エリア出来る）。そのエリア内には値が重複して存在しない。値が固定されたマスのエリアの残りのマスの可能性から、その値を削除する。
6)2)から5)を繰り返して、全ての条件（問題にかかれている初期値）を全て設定する。
7)2)から5)の作業途中で可能性が一つに絞られたマスが発生したら、そのマスに対して2)から5)の処理を同様に行う
8)ある行の全てのマスで、複数の可能性を持つマスに注目。複数の可能性の値のうち、その行で一つしか出現しない値を持つマスは、その値に固定。さらに3)から5)の処理を行う
9)同様に列に対しても、複数の可能性の値の中で一度しか出現しない値を持つマスを固定し、3)から5)の処理を行う
10)同様に３ｘ３マスのエリアに対しても、複数の複数の可能性の値の中で一度しか出現しない値を持つマスを固定し、3)から5)の処理を行う
11)8)から10)の作業途中で可能性が一つに絞られたマスが発生したら、そのマスに対して2)から5)の処理を同様に行う
12)値が固定されていないマスがまだ残っていたら、8)から11)までの処理を繰り返す。固定されていないマスがゼロになるまで繰り返す。
