数独百科 · 数学与计算

数独的数学原理

更新于 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

另见

来源

全部文章 →