← StudyX Devlog

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

Hiroki ObaraHiroki Obara · DeveloperSudoku365使い方
数独の答えの盤面は何通りあるか

前回の 数独の答えは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 の始め方 に書きました。

App Store でダウンロード Google Play で手に入れよう

Sudoku365毎日ナンプレ、2人でも