数独の場合の数

質問

Wikiprdiaで調べると、

http://ja.wikipedia.org/wiki/%E6%95%B0%E7%8B%AC

で、
「数独の組み合わせパターン数は、回転や反射や順列や名前を変更することなどの左右対称が考慮に入れられると、54億7273万0538になるとエド・ラッセルとフレーザージャービスによって示されている[8]。」

とあります。

「・・・」の中の意味を分かりやすく教えてもらえないでしょうか。全部マス目を埋めたパターンが54億通りある、ということでしょうか。それにしたら多すぎるような気がします・・・。

回答No.3

stomachman · ベストアンサー

ANo.1、もひとつミスプリを訂正です。どうもすいませんね。

> (6) 1行目から3列目までを、好きなように並べ替える。
> (7) 4行目から6列目までを、好きなように並べ替える。
> (8) 7行目から9列目までを、好きなように並べ替える。

の部分は、

(6) 1列目から3列目までを、好きなように並べ替える。
(7) 4列目から6列目までを、好きなように並べ替える。
(8) 7列目から9列目までを、好きなように並べ替える。

に差し替えてお読み下さい。

　ついでに、説明を足しておきます。
　「1列目から3列目までを、好きなように並べ替える」というのは、たとえば「1列目と2列目を入れ替えよう」という場合には、各行nについて、
　　1列目のn行目のマスにある数字と、2列目のn行目のマスにある数字とを入れ替える
という操作です。

　また、(4)の「１から3列目のブロックと、4から6列目のブロックと、7から9列目のブロックを好きなように並べ替える。」というのは、たとえば「１から3列目のブロックと4から6列目のブロックを入れ替えよう」という場合、各行nについて、
　　1列目のn行目のマスにある数字と4列目のn行目のマスにある数字とを入れ替える

　　2列目のn行目のマスにある数字と5列目のn行目のマスにある数字とを入れ替える

　　3列目のn行目のマスにある数字と6列目のn行目のマスにある数字とを入れ替える
ということを行う操作です。

お礼

丁寧に回答いただきありがとうございました。
多すぎるような気がしていましたが、よくわかりました。

回答No.2

stomachman

ANo.1 訂正です。違う数字を貼ってしまった。

数独の答（つまり、「全部マス目を埋めたパターン」）の総数は1京8383兆2225億7619万8308通りのさらに9! 倍ということでした。

とてつもない数のようですけど、単に9種類の数字を9個ずつ並べるだけなら 81!/((9!)^9)≒5.3×10^70通りもあるのに比べると、非常に限られた数しかないわけですね。

うち、対角線に対して線対称であるものが13056通りの9! 倍、中心に対して点対称であるものが1億5549万2352通りの9! 倍だそうです。

回答No.1

stomachman

Wikiから張ってあるリンク先の論文によれば、どうやら数独の答（つまり、「全部マス目を埋めたパターン」）の総数は1京8383兆2224億2069万2992通りのさらに9!(=9×8×‥×2)倍あるそうです。
　次に、ある数独の答を一つ持ってきて、
(1) ある数字と別の数字とを一斉に入れ替える。(9!通り）
(2) 左右裏返しにする。
(3) 90度回転する。
(4)１から3列目のブロックと、4から6列目のブロックと、7から9列目のブロックを好きなように並べ替える。
(5)１から3行目のブロックと、4から6行目のブロックと、7から9行目のブロックを好きなように並べ替える。
(6) 1行目から3列目までを、好きなように並べ替える。
(7) 4行目から6列目までを、好きなように並べ替える。
(8) 7行目から9列目までを、好きなように並べ替える。
(9) 1行目から3行目までを、好きなように並べ替える。
(10) 4行目から6行目までを、好きなように並べ替える。
(11) 7行目から9行目までを、好きなように並べ替える。
という11種類の操作を考えます。すると、これらのどの操作によって得られる結果も、また「数独の答」になっている訳です。さて、これらの操作をどんな順番ででも好きなだけ繰り返して作れるような答は、全部「同じ答」だと考えることにします。（だから、かなり見かけが違っていても「同じ答」になるものがとてもたくさんある訳ですね。）そして、「同じ答」ではない答（つまり、上記の操作をどう組み合わせていくら繰り返しても同じにならないような答）が何通りあるか。調べてみると54億7270万6619通り。
　また、上記の操作のうちで、(2)(3)を除いた操作で作れる答を「同じ答」だと考えることにした場合、「同じ答」ではない答は109億4543万7157通り。
　さらにまた、数字の入れ替え(1)と回転(3)によって作れるものだけを「同じ答」とした場合には、「同じ答」ではない答は4595兆8056億4405万2864通り。

ということが書いてあるようです。