计数问题：可能的数独表？
我正在研究 sudoko 求解器（python）。我的方法是使用博弈树并通过 DFS 算法探索每组数字的可能排列。
为了分析问题，我想知道可能的有效和无效 sudoko 表的数量是多少？
->一个 9*9 的桌子，有 9 个一，9 个二，...，9 个九。
（这与这个问题并不完全重复）
我的解决方案是：
1 - 首先选择 9 个单元格 1 秒：(*)
（来源：sitmo.com)
2- 以及类似 (1) 的其他数字（每次将从剩余可用单元格中删除 9 个单元格）： C(81-9,9) , C(81-9*2,9) .... =
（来源：sitmo.com)
3- 最后将结果乘以 9！ （(*) 中 1s-2s-3s...-9s 的排列）
（来源：sitmo.com)
这不等于接受的答案这个问题但问题是相同的。我做错了什么？
I'm working on a sudoko solver (python). my method is using a game tree and explore possible permutations for each set of digits by DFS Algorithm.
in order to analyzing problem, i want to know what is the count of possible valid and invalid sudoko tables?
-> a 9*9 table that have 9 one, 9 two, ... , 9 nine.
(this isn't exact duplicate by this question)
my solution is:
1- First select 9 cells for 1s: (*)
(source: sitmo.com)
2- and like (1) for other digits (each time, 9 cells will be deleted from remaining available cells):
C(81-9,9) , C(81-9*2,9) .... =
(source: sitmo.com)
3- finally multiply the result by 9! (permutation of 1s-2s-3s...-9s in (*))
(source: sitmo.com)
this is not equal to accepted answer of this question but problems are equivalent. what did i do wrong?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
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 个 1，9 个 2 ... 9 个 9。
81 个地方，
所以答案应该是 (9+9+...)！ / (9!)^9
现在如果你再乘以 9！那么这将通过打乱它们来将重复的排列添加到数字中。
The number of valid Sudoku solution grids for the standard 9×9 grid was calculated by Bertram Felgenhauer and Frazer Jarvis in 2005 to be 6,670,903,752,021,072,936,960.
Mathematics of Sudoku |
source
I think problem with your solution is that deleting 9 cells each time from available cells does not necessarily create a valid grid. What I mean is just deleting 9 cells won't suffice.
That is why 81! / (9!)^9 is much bigger number than actual valid solutions.
EDIT:
Permutations with repeated elements
Your solutions is almost correct if you want all the tables not just valid sudoku tables.
There is a formula:
(a+b+c+...)! / [a! b! c! ....]
Suppose there are 5 boys and 3 girls and we have 8 seats then number of different ways in which they can seat is
(5+3)! / (5! 3!)
Your problem is analogous to this one.
There are 9 1s , 9 2s ... 9 9s.
and 81 places
so answer should be (9+9+...)! / (9!)^9
Now if you multiply again by 9! then this will add duplicate arrangements to the number by shuffling them.
根据这篇维基百科文章（或这个 OEIS 序列），大约有 6.6 * 10^21 个不同的数独方块。
According to this Wikipedia article (or this OEIS sequence), there are roughly 6.6 * 10^21 different sudoku squares.
你做错的是最后一步：你不应该将答案乘以
9！。您已经数出了所有可能的方格。在计算可能的数独表时，这对您没有多大帮助。您可以做的另一件事是计算“行条件”成立的表：这只是
(9!)^9，因为您只需选择1.. 的一种排列。每行 9。更接近数独问题的是计算拉丁方格。拉丁方必须同时满足“行条件”和“列条件”。这已经是一个难题，并且没有已知的封闭形式公式。数独是带有附加“子方条件”的拉丁方。
What you did wrong was the last step: you shouldn't multiply the answer by
9!. You have already counted all possible squares.This doesn't help you much when counting the possible Sudoku-tables. One other thing you could do is to count the tables where the "row-condition" holds: that is just
(9!)^9, because you just choose one permutation of1..9for every row.Still closer to the Sudoku-problem is counting Latin squares. Latin square has to satisfy both the "row-condition" and "column condition". That is already a difficult problem and no closed form formula is known. Sudoku is a Latin square with the additional "subsquare-condition".