数独の解盤面の数

数独の解となり得る盤面の数はいくつか？

この問題については、すでに答えが得られています。

答えは、6670903752021072936960個です。

指数表示で書くと、6.67 * 10^21。

また、対称性などを考慮して、本質的に異なる盤面の数を数えると、

5472730538個になります。

これは、5.47 * 10^9です。

前者はBertram FelgenhauerとFrazer Jarvis、後者はEd RussellとFrazer Jarvisによるもので、Sudoku enumeration problemsのサイトに詳しい説明があります。

簡単に数え方を説明すると次のような感じです。

まず上の三行について数字を決めます。このとき、解盤面の数が同じになるような数字の並びを上手くグルーピングするのがポイントです。そして、それぞれについて網羅的に残りの数字を確定させて、解盤面の数を数えます。

上のサイトでは、プログラムとその実行結果をダウンロードすることが出来ます。

これらの各盤面に対してユニークな番号を付けようという研究も行われています。

• 数独インデックス
• 井上、奥乃、本質的に異なる数独盤面の列挙と番号付け、情報処理学会第71回全国大会

前者については、卒業研究として取り組んだようで、卒業論文や卒論発表の資料をダウンロードすることが出来ます。

なお、9x9以外のサイズの数独についても色々と調べられており、wikipediaのMathematics of Sudokuにまとめられています。