全體數獨題總解數問題再探

• 2021 年 10 月 24 日
• 筆記
• 數學

在上一篇（探究一個問題：全體數獨題的總解數是多少？）里只對 S 的值做了上界估算，嚴格來說，還應對 S 的值做下界估算。另外，其中對 S 值的上界估算還是顯著偏大，還可以做精確度更高的估算。

由於 H = S / (6! · 6!)，以下嘗試對 H 值，即如下 1R1B1C 數獨題的總解數，做更高精確度的估算。

123 456 789
456 000 000
789 000 000
200 000 000
300 000 000
500 000 000
600 000 000
800 000 000
900 000 000

 考察第 2 行的空位，先看第三節，顯然只能填 {1,2,3}；再看第二節，顯然只能填 {7,8,9}，這樣，第 2 行的 6 個空位整體會有 3! · 3! = 36 種可能（比上一篇里的 6! 的估算小很多）。選取其中一種，得到如下的 12R1B1C 型數獨題的一個代表：

123 456 789
456 789 123
789 000 000
200 000 000
300 000 000
500 000 000
600 000 000
800 000 000
900 000 000

為避免佔用太多的字母標記不同數獨題的總解數而引起的混亂，以下用 ss(Q) 來表示數獨題 Q 的總解數，ss 是 solution sum 的縮寫。全空數獨題記作 ALL0，於是有：

δ := ss(ALL0)，S := ss(1R)，H := ss(1R1B1C)

δ = 9! · S                        ①

S = 6!² · H                      ②

H = 3!² · ss(12R1B1C)     ③

② 和 ③ 這兩個等式，實際上並沒有給出嚴格的證明，後面再考察是否要把其中的 = 換成 ≈。

繼續估算這個 12R1B1C 型數獨題代表的總解數，考察第 3 行的空位，第二節只能填 {1,2,3}，第三節只能填 {4,5,6}，同樣，第 3 行的 6 個空位整體會有 3! · 3! 種可能。選取其中一種，得到如下的 123R1C 數獨題：

123 456 789
456 789 123
789 123 456
200 000 000
300 000 000
500 000 000
600 000 000
800 000 000
900 000 000

並有：

H = 3!² · ss(12R1B1C) = 3!⁴ · ss(123R1C)   ④

繼續估算 123R1C 的總解數，考察第 2 列的空位，先看第三節，這一節是第 2 列和第 7 宮的共同部分，由於

{2,5,8} ∪ {6,8,9} = {2,5,6,8,9}

這一節能填值的集合為 {1,3,4,7}，而且 3 必需填在這一節（第 2 列的第二節也屬於第 4 宮，且第 4 宮已經有 3），先填 3，有 3 種可能，再填另兩個位置，有 3 · 2 中可能，即第 2 列第三節整體有 3 · 3 · 2 = 18 種填值可能。這時第 2 列第二節要填 6 和 9，以及 {1,4,7} 中填完第三節後剩下的那個數，即第二節有 3! 種填值可能。所以，第 2 列的 6 個空位整體有 18 · 3! = 3 · 3!² 種填值可能。選取其中一種，作為 123R12C 型數獨題的代表，如下所示：

123 456 789
456 789 123
789 123 456
260 000 000
390 000 000
570 000 000
630 000 000
810 000 000
940 000 000

此時有：

H = 3!⁴ · ss(123R1C) = 3 · 3!⁶ · ss(123R12C)  ⑤

接着考察 123R12C 型數獨題的這個代表，依次考察第 4 宮和第 7 宮，等效於考察第 3 列，可知第 3 列的第二節可填值為 {1,4,8}，第 3 列的第三節可填值為 {2,5,7}，且都可以獨立選值，因此，第 3 列的 6 個空位整體有 3! · 3! 種取值可能。選取其中一種，作為 123R123C 數獨題的代表，如下所示：

123 456 789
456 789 123
789 123 456
261 000 000
394 000 000
578 000 000
632 000 000
815 000 000
947 000 000

此時有：

H = 3 · 3!⁶ · ss(123R12C) = 3 · 3!⁸ · ss(123R123C)   ⑥

接着考察 123R123C 數獨題的這個代表，來看第 5 行，[5,5] 和 [5,8] 兩個空位的填值只能選自 {1,6,7} …慢着！此時剩餘的空位並不多，可以考慮直接用 SudokuSolver 2.5 求解，具體如下：

D:\read\num\Release>sudoku.exe

Order please:
load-quiz s.txt
Quiz loaded.

Order please:
show
123 456 789
456 789 123
789 123 456

261 000 000
394 000 000
578 000 000

632 000 000
815 000 000
947 000 000

Order please:
runrun 10000
...
17682) No more solution (solution sum is 2600).
Run-run time: 1091 milliseconds; current solutions: 2600
 steps: 0 # 0 # 17682
 total solutions: 0 # 0 # 2600.

Order please:

總解數為 2600 個。於是由 ⑥，有

H = 3 · 3!⁸ · ss(123R123C) 

   = 3 · 1679616 · 2600 = 13,101,004,800

再由 ②，有

S = 6!² · H

   = 720² · 13,101,004,800

   = 6,791,560,888,320,000

 這裡的 H 和 S 的估值比上一篇里的估算值小多了。還用 2 秒一萬的速度計算，一天是 4.32 億

13,101,004,800 / 432,000,000 = 30.3264 天

這是直接求 H 值大約需要的時間。這樣看，上一篇里的估算（2.75 億年）太離譜了。

比較這一組數：

                           H = 13,101,004,800

                          232 = 4,294,967,296

                    S = 6,791,560,888,320,000

             264 = 18,446,744,073,709,551,616

   δ = 9! · S = 2,464,521,615,153,561,600,000

 296 = 79,228,162,514,264,337,593,543,950,336

 可以看到，H 剛超出 2³² 的界限，是 2³² 的 3 倍左右；而 S 沒有超出 2⁶⁴；δ 也沒有超出 2⁹⁶。

本篇里黃色標註的等式都沒有經過嚴格證明，現在來具體分析一下。