數獨百科 · 數學與電腦

數獨的數學

更新於2026-10-05

帶有宮的拉丁方陣

在拉丁方陣中，每個符號在每一橫行和每一直列中各出現一次。完成的數獨是一個9階拉丁方陣，再加多一個條件：九個3×3宮各自亦包含每個數字各一次。

方格有多少個

伯特倫·費根豪爾 (Bertram Felgenhauer) 和弗雷澤·賈維斯 (Frazer Jarvis) 於2005年計算出完成的9×9方格數目：共有6,670,903,752,021,072,936,960個，約為6.67 × 10²¹。其中許多其實是換了包裝的同一個方格。若一個方格能透過重新標記數字、旋轉或翻轉，或以保持方格有效的方式重新排列橫行和直列而變成另一個方格，就把兩者算作一個，這樣便剩下5,472,730,538個本質上不同的方格；這個數字由艾德·羅素 (Ed Russell) 和弗雷澤·賈維斯計算得出。

資料來源: Felgenhauer and Jarvis, Enumerating possible Sudoku grids (2005), OEIS A107739: number of Sudoku grids, Wikipedia: Mathematics of Sudoku

17個提示數的下限

提示數為16個或以下的標準9×9數獨，沒有一道恰好只有一個答案。加里·麥奎爾 (Gary McGuire)、巴斯蒂安·圖格曼 (Bastian Tugemann) 和吉勒·西瓦里奧 (Gilles Civario) 以窮舉式電腦搜尋證明了這一點，並於2012年1月公布結果。17是最少數目，而非保證：許多有17個提示數的方格仍然有多於一個答案。

資料來源: McGuire, Tugemann and Civario, There is no 16-Clue Sudoku (arXiv 1201.0749)

作為圖著色問題的數獨

為81個格子各畫一個點，凡兩個格子位於同一橫行、直列或宮，就把對應的兩點連起來。這個數獨圖共有810條連線，每個點都恰好有20個相鄰點。解謎題即是把提示數所固定的顏色延伸出去，使相連的點永不同色。至少需要九種顏色，因為每一橫行、直列和宮都是一組九個彼此相連的點；而任何一個完成的方格都顯示九種顏色已經足夠。

資料來源: Wikipedia: Sudoku graph

一般而言很難，9×9則很快

對於可以無限擴大的數獨方格（宮為n×n的n²×n²方格），判斷一個部分填好的方格能否完成是NP完全問題，這是 Takayuki Yato 與 Takahiro Seta 於2003年發表的結果。高效的電腦程式通常能在零點幾秒內解出普通的9×9謎題，但所需時間取決於程式、電腦和謎題本身。

資料來源: Wikipedia: Mathematics of Sudoku, Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle

另見

資料來源

所有文章 →