algorithm - 选择最佳矩阵

Question

我得到 X大小矩阵 Ni*Mi其中 1<=N<=4 and 1<=M<=4, for all 1 <= i <= X

游戏包括从给定的 X 中选择任意矩形(子矩阵)矩阵并删除这个子矩阵。

例如:我们有 1 个大小为 4x4 的矩阵.玩家 1 可以选择大小为 4x4 的子矩阵(在这种情况下是整个矩阵)并将其删除。或者他们可以选择 2x2 的子矩阵或 1x1或 2x3或任何有效的子矩阵并将其从 4x4 中删除矩阵，我们还有剩余的矩阵留在游戏中。

不能下棋的玩家输了。

哪个玩家获胜？

双方球员发挥最佳。

Answer 1

此问题已通过 Sprague Grundy theorem 解决，这表示当您对各个矩阵的数字进行异或时，只有当结果为 0 时，要移动的玩家才会输(因为任何移动都会将失败的位置变成获胜的位置，然后另一个玩家可以将获胜的位置变成再次失败等等，这是 nim 类游戏的本质)。

数字是递归计算的，矩阵的数字是所有可达状态的数字的mex(最小独占=集合中不存在的最小非负整数)。

所有 0 都是 0，您没有有效的着法，因此是输 (0)。

恰好有一个 1 是 1，因为唯一可到达的位置是 0 且 mex(0) = 1。

对于两个我们要判断它们是否相邻，adjacent = mex(0, 1) = 2, not adjacent = mex(1) = 0 ...等等。

例子:

1 0 0 0     1 1 0     1 1
0 0 1 1     0 0 0     1 1
0 0 1 0     0 0 1
0 0 0 0
   =          =        =
   2    xor   3   xor  1   =   0   => player to move loses.

快速实现可能如下所示:

1. 预先计算这 16 种(10 种具有对称性)不同情况的数字并将它们存储在数组中。

2. 赋值结果=0

3. result = result xor nimbers[readRowCount()][readColCount()]

4. 重复3.直到读取所有矩阵维度

5. 如果结果 != 0 那么第一位玩家获胜，否则第二位玩家获胜

例子2:数字计算

matrix:
1 1
1 1

valid moves:
0 1*  1 0*  1 1*  1 1*  0 0   1 1+  0 0+  1 0+  0 1+
1 1   1 1   0 1   1 0   0 0   0 0   1 1   1 0   0 1
                         =
                         0 by definition

The other matrices can be grouped into 2 groups * and + because of symmetries.

Reachable positions from *:
0 1   0 1   0 0
0 1   1 0   0 1
 =     =     =
             1 = mex(0), because the only reachable position has a nimber of 0
       0 = mex(1), because the only reachable position has a nimber of 1
 2 = mex(0,1), because the reachable positions have nimbers of 0 and 1

==> the nimber for * is mex(0, 1, 2) = 3.

==> we already know now that the nimber of + is 2.

==> the nimber of the given matrix is mex(0, 2, 3) = 1.