math - 尝试计算带有 5 个数字的棋盘的状态空间

Question

我有一个 5x5 的棋盘，棋盘的第一行有 1..5 个数字。

只要不在另一个数字之上，每个数字最终都可以位于任何位置。

每个数字都可以在一次移动中向上、向下、向左或向右移动，但是我认为这不会对状态空间产生影响，因为最终每个数字都可以在无限移动的情况下结束。

因为除了在另一个数字之上之外，每个数字最终都可以在任何地方的任何地方，我假设一个数字可以在任何时候处于 1/21 位置？即棋盘空间 (25) 减去它不能位于 (4) 之上的数字。

我最初的计算是 ((n*n)-(n-1))^n 因为我试图考虑到一个数字不能在另一个数字之上但是我发现了以下计算:

我在 wiki 页面上发现这是一种计算围棋棋盘状态空间的方法。

每个空间可以有 6 个不同的可能值(1..5 和空)，棋盘有 25 个正方形，所以等式为 (n+1)^(n*n) = 6^25 = 2.843x10^ 19

这是正确的吗？单个数字在任何时刻只能出现在 25 个空格中的 21 个空格这一事实不会影响它吗？

如果不正确，请告诉我原因或/并提供可行的解决方案。

非常感谢! :)

Answer 1

Is this correct? Does the fact that a single number can only be in 21 spaces out of the 25 at any single moment not affect it?

不，这是不正确的。与围棋棋盘的不同之处在于，您只有 5 个数字，因此 25 个位置中始终有 20 个是空的，并且每个非空状态只能出现一次。

所以数字所在的五个位置有25 `choose` 5种可能，五个数字在这五个位置上可以5!方式排列.

因此你有一个总的状态空间

25!/20! = 21*22*23*24*25 = 6375600

状态。