2

这更像是一个数学问题而不是编程，但我认为这里的很多人都非常擅长数学！:)

我的问题是：给定一个 9 x 9 网格（81 个单元格），每个网格必须包含数字 1 到 9 恰好 9 次，可以生成多少个不同的网格。数字的顺序无关紧要，例如第一行可能包含九个 1 等。这与数独有关，我们知道有效数独网格的数量是 6.67×10^21，所以因为我的问题不受限制就像数独一样，必须在每一行、每一列和每一框中都有 9 个数字，那么答案应该大于 6.67×10^21。

我的第一个想法是答案是 81！然而，进一步思考，这假设每个单元格可能的 81 个数字是不同的、不同的数字。它们不是，每个单元格有 81 个可能的数字，但只有 9 个可能的不同数字。

我的下一个想法是，第一行中的每个单元格都可以是 1 到 9 之间的任何数字。如果碰巧第一行恰好都是相同的数字，比如说全 1，那么第二行中的每个单元格只能有 8 种可能性，2-9。如果这一直持续到最后一行，则可以通过 9^2 * 8^2 * 7^2 ..... * 1^2 计算不同排列的数量。但是，如果每行不包含 9 个相同的数字，这将不起作用。

自从我研究这些东西以来已经有一段时间了，我想不出办法来解决它，我将不胜感激任何人可以提供的帮助。

4

2 回答 2

9

想象一下，拿 81 张空白纸条，在每张纸条上写一个从 1 到 9 的数字（每个数字九个）。洗牌，开始将纸牌放在 9x9 网格上。

你可以创造81！如果您认为每个单据都是独一无二的，则可以使用不同的模式。

但相反，您想将所有 1 视为等价的。

对于任何特定配置，由于 1 都相同，该配置将重复多少次？答案是 9！，您可以排列写有 1 的九张纸条的方法数。

因此，排列总数减少到 81!/9!。（你除以不可区分排列的数量。想象一下只有 2 个不可区分排列，而不是 9!

啊，但是您还希望 2 和 3 等价，等等。同样的道理，这减少了排列的数量

81!/(9!)^9

根据斯特林的近似值，大约是 5.8 * 10^70。

于 2010-03-25T01:38:04.073 回答
4

首先，让我们从 1 到 81 的 81 个数字开始。排列的数量是81P81, 或81!。很简单。

但是，我们有 9 个1s，它们可以排列成9!难以区分的排列。与2,3等相同。

所以我们得到的是棋盘排列的总数除以所有数字的所有不可区分的排列，或81! / (9! ** 9)。

>>> reduce(operator.mul, range(1,82))/(reduce(operator.mul, range(1, 10))**9)
53130688706387569792052442448845648519471103327391407016237760000000000L
于 2010-03-25T01:38:11.870 回答