スポンサーリンク
TOP > コラム > ナンプレ（数独）の組み合わせパターン数
ナンプレ（数独）の組み合わせパターン数
数字の組み合わせ
ナンプレ（数独）の組み合わせはいくつあるのでしょうか、高校で習う組み合わせで解けそうですが、けっこうむずかしい。
1行目は簡単で9*8*7*6*5*4*3*2*1で362880通りです。
2行目ABCは1行目ABC以外なので6*5*4の120通り
3行目のABCは残りの3*2*1の6通りです。
ここまでは簡単なのですが2行目DEFは1行目DEFと2行目ABCを除いた組み合わせになります。
1行目DEFと2行目ABCがかぶらないなら3*2*1なのですが、かぶったりするのでこういう場合はかぶる場合の反対の組み合わせで計算します。が、もう忘れたので。ちょっと私にはむずかしい。
2段目のBOXとなるともっと難しくて上の列、横の行、BOX内の数字をすべて考慮に入れる必要があります。
で、難しくて解けないので検索して調べたのですが6,670,903,752,021,072,936,960通りあるそうです。
これは対称な物を同一していないので、90°や180°、270°回転させたもの、鏡のように対称なものを省くと5,472,730,538通り。
54億7273万0538になるとエド・ラッセルさんとフレーザージャービスさんによって示されているそうです。
Jarvis, Frazer; Ed Russell (2005年9月7日). “There are 5472730538 essentially different Sudoku grids ... and the Sudoku symmetry group”. Frazer Jarvis's home page. 2006年9月16日閲覧。
ヒントマスの組み合わせ
ここまでは数字の組み合わせで、ナンプレ（数独）にはヒントマスの組み合わせがあります。空白のマスが1つだと9*9で81通りですが
空白のマスが2つだと81*80の6480通りになりますが、場所がかぶるのでこれも考慮に入れます。。ヒントマス30個だと階乗を使って出すということになるのですが、どうもものすごい数になるようです。また、ヒントマスは最小16らしいのですが、解ける問題でないとナンプレ（数独）にはならないので、単純にヒントマスの組み合わせ数だけでなく、上の54億7273万0538通りの数字の並びとヒントマスの組み合わせを作って、解けるかどうか調べる必要もあります。
それとヒントマスも数字と同様90°や180°、270°回転させたもの、鏡のように対称なものを省く必要がありそうに思えますが、数字の組み合わせ1つにつき90°や180°、270°回転させたものはまったく違う問題になるので、こちらは省略しなくても良さそうですね。
ということで、無限のようにたくさんあるナンプレ（数独）の組み合わせですが、ちょっと数を出すことは無理そうですので、そのうちどこかでどなたかが公開されることを待つとします。
