数独の構造

先の記事（数独の特殊解）で数独の特殊な解に出会ったと書いたが、その解を眺めているうちに数独の解の構造についていくつかのことがわかってきた。

基本解	色分け

上左がその特殊な解で、数独の解のうちもっとも基本になるものと考えられる。 上右はそれを同じ数字ごとに色分けした物。
この各色に１から９の数字を任意に割り当てて配置すれば、それは常に数独の解の条件を満足する。

ブロック	列ブロック２と３を交換

さらに、３列からなる列ブロックを他の列ブロックと入れ替えても、上右図のように数独の解の条件は保たれる。 これは３行からなる行ブロックについても同じだ。 また、行ブロック内の１行全体を行単位で同じブロック内の他の行と入れ替えても解の条件は保たれる。 これは列についても同じだ。 これを踏まえれば、可能な数独の全ての解を作れるし、それが何通りあるのかも計算できる。

３ｘ３のブロックに１～９の数字を一つずつ割り当てる配列は順列と同じなので、９！＝３６２，８８０通りとなる。 さらに行ブロックと列ブロックの入れ替えはそれぞれ２通りとなる。 それぞれ６通りとならないのは、たとえば左上隅のブロックを基準に考えると、他の八つのブロックの配列はすべて基準ブロックの９！通りの配列の中に含まれているので入れ替える意味が無いからだ。 上下や左右の反転や対角線による反転も同じ理由で入れ替える意味が無い。

さらに、各ブロック内の行あるいは列を入れ替えてできる入れる配列はそれぞれ３！＝６通りになる。
よって可能な解の数は、９！ｘ（２ｘ６ｘ６）ｘ（２ｘ６ｘ６）＝約１９億（１，８８１，１６９，９２０） となる。 意外に少ないような気もするが、重複を除けばこんな物なのだろう。

上記の手順を使えば、コンピューターなどですべての解の配列を書き出すことは可能だ。 しかしそれを数独の問題に仕上げるには、どこを抜けば良いかを決めねばならないが、これはまた別のロジックが必要だ。

さらに言えば、この程度の数（＊）であればすべての解をコンピューターに記憶させておき、問題と重ね合わせて照合することで正解を求めることは可能だ。 だがしばしば見かける、正解が複数ある問題には複数の回答が出力されるだろう。 逆にそれを利用すれば、問題に複数の正解があるかどうかをチェックすることができる。 複数正解を避けたい問題作成者にとっては有用なツールになるだろう。

（＊）バイト数で１５２ＧＢになるが、今のパソコンでは照合にさほどの時間はかからないだろう。 ９行ｘ９列＝８１桁の数字からなる文字列の照合と考えれば良いので、プログラムとしては単純だ。