我正在研究一个 sudoko 求解器（python）。我的方法是使用游戏树并通过 DFS 算法探索每组数字的可能排列。
为了分析问题，我想知道可能的有效和无效sudoko 表的数量是多少？
-> 一个 9*9 的表，其中包含 9 个一、9 个二、...、9 个九。
（这个问题并不完全重复）
我的解决方案是：
1- 首先为 1 选择 9 个单元格：(*)
2- 其他数字与 (1) 类似（每次，将从剩余的可用单元格中删除 9 个单元格）： C(81-9,9) ， C(81- 9*2,9) .... =
3- 最后将结果乘以 9！（（*）中 1s-2s-3s...-9s 的排列）
这不等于这个问题的公认答案，但问题是等价的。我做错什么了？
Bertram Felgenhauer 和 Frazer Jarvis 在 2005 年计算出标准 9×9 网格的有效数独解决方案网格数为 6,670,903,752,021,072,936,960。
我认为您的解决方案的问题是每次从可用单元格中删除 9 个单元格并不一定会创建有效的网格。我的意思是仅仅删除 9 个单元格是不够的。
这就是为什么81！/ (9!)^9 比实际有效的解决方案大得多。
编辑：
如果您想要所有表格而不仅仅是有效的数独表格，那么您的解决方案几乎是正确的。
有一个公式：
(a+b+c+...)！/ [一种！乙！C！....]
假设有 5 个男孩和 3 个女孩，我们有 8 个座位，那么他们可以坐的不同方式的数量是
（5+3）！/（5！3！）
您的问题与此类似。
有 9 个 1s ， 9 个 2s ... 9 个 9s。和 81 个地方
所以答案应该是（9+9+...）！/ (9!)^9
现在，如果你再乘以 9！那么这将通过洗牌将重复的排列添加到数字中。
根据这篇维基百科文章（或这个 OEIS 序列），大约有 6.6 * 10^21 个不同的数独方块。
你做错的是最后一步：你不应该将答案乘以9!. 您已经计算了所有可能的方格。
在计算可能的数独表时，这对您没有多大帮助。您可以做的另一件事是计算“行条件”成立的表：即(9!)^9，因为您只需1..9为每一行选择一个排列 。
更接近数独问题的是计算拉丁方格。拉丁方必须同时满足“行条件”和“列条件”。这已经是一个难题，并且没有已知的封闭形式公式。数独是带有附加“子平方条件”的拉丁方格。