数独の答えの盤面は何通りあるか

前回の 数独の答えは1つだけ では、ヒントが最低17個いるという2012年の結果を紹介しました。そのなかで、完成した盤面が全部で約 6.67×10²¹ 通りあること、本質的に異なるものは約54億7千万通りあることに、さらっと触れました。
この記事では、その二つの数をもう少しくわしく見ていきます。どうやって数えたのか、「本質的に異なる」とはどういう意味か、という話です。
数えるのは「答えの盤面」
ここで数えるのは、問題ではなく、すべてのマスが埋まった答えの盤面です。どの行にも、どの列にも、どの3×3のブロックにも、1から9が1回ずつ入っている盤面が、全部で何通りあるか、という問いです。
問題の数は、答えの盤面よりずっと多くなります。1つの答えの盤面から、ヒントの残し方を変えれば、唯一解になる問題がたくさん作れるからです。問題の数は数え方が難しく、ここでは扱いません。
小さな数独で考える
いきなり9×9を考えると途方に暮れるので、まず4×4の数独を考えます。1から4を使い、どの行にも列にも、2×2のブロックにも同じ数字が入らないようにするものです。
こちらは、完成盤面が288通りしかありません(数列の辞典 OEIS の A107739 にこの数が載っています)。288通りなら、紙と鉛筆でも根気があれば全部書き出せます。
9×9は約66.7垓通り
9×9になると、話が一変します。完成盤面の数は、
6,670,903,752,021,072,936,960 通り
です。日本語の単位でいえば、66垓7090京3752兆0210億7293万6960通りです。この数は、2005年にベルトラム・フェルゲンハウアーと、イギリスのシェフィールド大学のフレイザー・ジャーヴィスが計算して発表しました。英語版 Wikipedia の Mathematics of Sudoku にも、この数が載っています。
全部を一つずつ作って数えたわけではありません。考え方の骨組みは、次のようなものです。
まず、左上のブロックに入る数字の並びは、9個の数字の並べ方なので 9×8×7×…×1 = 362,880 通りあります。ところが、どの並びでも、そのあとの埋め方の数は同じです。数字の名前を付け替えれば、どの並びも「1 2 3 / 4 5 6 / 7 8 9」に直せるからです。そこで、左上を「1 2 3 / 4 5 6 / 7 8 9」に固定して残りを数え、最後に362,880を掛ければよいことになります。
左上を固定したときの埋め方は、1京8383兆2224億2069万2992通りです。二人は、上の3段(左上を含む横長の帯)の入り方を、残りの埋め方が同じになるもの同士でまとめて44種類に減らし、それぞれの残りの埋め方を計算機で数えました。手で全部調べる方法ではありませんが、数え漏れや二重数えが起きないよう、場合分けをきちんと組み立てた計算です。
どれくらい大きな数か
6.67×10²¹ という数は、大きすぎて実感がわきません。
仮に、1秒に1枚ずつ完成盤面を眺めていくとします。眠らずに続けても、全部を見終わるには約211兆年かかります。宇宙の年齢は約138億年といわれているので、その1万5千倍ほどです。
「本質的に異なる」盤面とは
ただ、この膨大な盤面の多くは、互いによく似ています。ある完成盤面に、次のような操作をしても、ルールは守られたままです。
- 数字の付け替え。盤面のすべての1を5に、すべての5を1に変える、というような入れ替えです。9個の数字の付け替え方は362,880通りあります。
- 同じ帯のなかで行を入れ替える。上の3行の順番を入れ替えても、ブロックの中身は変わらないので、ルールは崩れません。
- 帯ごと入れ替える。上の3行のかたまりと、下の3行のかたまりを丸ごと交換する操作です。
- 列についても同じで、同じ縦の帯のなかで列を入れ替えたり、縦の帯ごと入れ替えたりできます。
- 対角線で折り返す。左上から右下への対角線を軸に、行と列を入れ替える操作です。
回転や鏡に映した形は、これらの組み合わせで作れます。たとえば90度の回転は、対角線での折り返しと、列の並びを逆にする操作を続けたものです。
行と列の入れ替えと折り返しを組み合わせると、1つの盤面から最大で3,359,232通りの盤面が作れます。数字の付け替えまで含めると、約1兆2190億通りになります。
こうした操作で移り合う盤面を「同じもの」とみなして数えたのが、本質的に異なる盤面の数です。見た目は違っても、数字の名前を変えたり、行を並べ替えたりしただけの盤面は、パズルとしての骨格が同じだと考えるわけです。
本質的に異なる盤面は約55億通り
本質的に異なる盤面の数は、
5,472,730,538 通り
です。2005年から2006年にかけて、エド・ラッセルとフレイザー・ジャーヴィスが計算しました。
単純に考えると、6.67×10²¹ を約1兆2190億で割れば答えが出そうです。実際に割ると約54億7245万になり、正しい値より少しだけ小さくなります。差が出るのは、ある操作をしても元とまったく同じ盤面に戻ってしまう、対称性を持った盤面が少しだけあるからです。そういう盤面は、操作をしても1兆2190億通りの別の盤面には増えません。その分を数学の定理(バーンサイドの補題と呼ばれるもの)で補正して、正確な数を出しています。
約55億通りなら、1秒に1枚ずつ眺めると、約173年で見終わります。宇宙の年齢の1万5千倍と比べると、ずいぶん人間の手の届く数になりました。前回の記事で紹介した、ヒント16個の問題がないことの証明は、この約55億通りの盤面を1つずつ調べることで成り立っています。最初の 6.67×10²¹ 通りのままでは、計算機でも調べきれなかったはずです。
ラテン方陣との違い
数独とナンプレの違い に書いたように、完成した数独の盤面は「ラテン方陣」の一種です。ラテン方陣は、行と列に同じ数字がないことだけを求めます。数独はそこに3×3のブロックの条件が加わるので、ラテン方陣の中から、さらに条件を満たすものだけを選んだことになります。それでも6.67×10²¹通り残ります。
1200問と66.7垓通り
Sudoku365 には、4つの難易度に300問ずつ、計1200問が入っています。1日1問ずつ解くと、全部で約3年3か月かかります。
一方で、答えの盤面の数と比べると、1200は比べものにならないほど小さな数です。数独のネタが尽きる心配は、当分しなくてよさそうです。
アプリには、全世界共通の1日1問のデイリーチャレンジもあります。解き方の手筋から始めたい人は 初心者が最初に覚える手筋 を、難しさの違いが気になる人は ナンプレの難易度は何で決まるか を読んでみてください。
アプリは無料で、広告が入ります。「広告を削除」の買い切り(1,500円)で広告を消せます。最初の一問の始め方は Sudoku365 の始め方 に書きました。
Sudoku365毎日ナンプレ、2人でもアプリを見る →