algorithm - 找到 3x3 打洞的所有组合

Question

我参加了一个狂欢节，在每个地点，他们都会用特殊的打洞器标记您的节目。打洞器是一个 3x3 空间的网格。在每个空间中，要么有一根针会刺破你的纸，要么没有。这让我想知道您可以使用此工具制作多少种不同的图案。我的第一个想法是:2^9 = 512，但所有 9 个空格都没有针并不是真正的一拳，所以真的:511。

然后复杂性击中了我。特别是因为 worker 们在给你的纸打洞时并不那么小心，所以这些看起来都是一样的:

x..  .x.  ...  etc.
.x.  x..  .x.
...  ...  ..x

问题:如何编写测试来说明旋转和移动？

---

迄今为止的努力和想法:

• 二进制感觉像是这个等式的明显部分
• 当找到一个独特的模式时，将其存储在内存中，以便 future 的模式可以针对它进行测试
• 有 4 种旋转可能性。
  编辑:我所说的“旋转”是指您可以采用任何形状并将其旋转 90 度。考虑在左上角是一个点的图案。您可以将其旋转/旋转 90 度，并在右上角获得圆点。再做一次，它就在右下角。再次，它在左下角。使用纯 2^9 计算，这些是 4 种不同的组合。然而，对于这个问题，这些正是我试图清除的重复项。
• 对于每次旋转，有 25 种方法可以使 3x3 网格重叠:

重叠:

/ = the spaces in the new one to test
\ = the spaces in a verified unique one

1               2               25
/ / / . . . .   . / / / . . .   . . . . . . .
/ / / . . . .   . / / / . . .   . . . . . . .
/ / X \ \ . .   . / X X \ . .   . . \ \ \ . .
. . \ \ \ . .   . . \ \ \ . .   . . \ \ \ . .
. . \ \ \ . .   . . \ \ \ . .   . . \ \ X / /
. . . . . . .   . . . . . . .   . . . . / / /
. . . . . . .   . . . . . . .   . . . . / / /

• 如果任一图案包含不在重叠区域中的引脚，则无需测试重叠。按位 AND 可以在这方面提供帮助。
• 如果将 2 种模式中的每一种的每个位置都放入字符串中，则可以只检查相等性
• 能否结合前两个想法来提高效率？

Answer 1

我们只需要考虑在第一行和第一列有冲孔的模式。如果第一行是空的，图案可以向上移动。如果第一列为空，则图案可以向左移动。在任何一种情况下，我们都可以推导出我们确实考虑过的类似模式。

对于这些模式，我们需要检查旋转后的版本是否相同。为此，我们最多应用三个 90 度旋转，可能会向左移动以删除前导空列(第一行永远不会为空)并找到具有最低数值的模式。

然后我们可以将这个值添加到哈希集中，它只会保留唯一值。

不包括空模式，因为它的所有行都是空的。

为了实现这一点，我们将模式编码为连续的位:

012
345
678

我们需要的操作大多非常简单:

Test for an empty row:    (n & 7) == 0     // bits 0,1,2 not set
Test for an empty column: (n & 73) == 0    // bits 0,3,6 not set
Shift pattern up:         n -> (n >> 3)
Shift pattern left:       n -> (n >> 1)

最棘手的部分是旋转，实际上只是重新排列所有位:

n -> ((n & 1) << 2) + ((n & 2) << 4) + ((n & 4) << 6)
   + ((n & 8) >> 2) + (n & 16) + ((n & 32) << 2)
   + ((n & 64) >> 6) + ((n & 128) >> 4) + ((n & 256) >> 2);

在 C# 中:

public static int Count3x3() {
    HashSet<int> patterns = new HashSet<int>();
    for (int i = 0; i < 512; i++) {
        if ((i & 7) == 0 || (i & 73) == 0)
            continue;
        int nLowest = i;
        int n = i;
        do {
            nLowest = Math.Min(nLowest, n);
            n = ((n & 1) << 2) + ((n & 2) << 4) + ((n & 4) << 6)
                + ((n & 8) >> 2) + (n & 16) + ((n & 32) << 2)
                + ((n & 64) >> 6) + ((n & 128) >> 4) + ((n & 256) >> 2);
            while ((n & 73) == 0)
                n >>= 1;
        } while (n != i);
        patterns.Add(nLowest);
    }
    return patterns.Count;
}

此函数返回 116。在我的机器上花费的时间是 0.023 毫秒。

编辑:通过使用 4 次观察，您可以获得额外 7 倍的改进:

1. 我们可以使用简单的访问数组来代替散列集。如果以前看到过某种模式，我们不会将其计算在内。这也消除了跟踪内部循环中“最低”模式的需要。如果访问了一个模式，那么它的最低旋转模式也被访问了。
2. 如果我们没有 180 度旋转对称性，那么第 3 次旋转将不会产生原始图案。第 4 次轮换将始终如此，因此没有必要。
3. 旋转表达式可以稍微简化。

因此，如果我们应用这些观察结果并展开内部 do 循环，我们将得到以下结果:

static int Rotate(int n) {
    n = ((n & (1+32)) << 2) + ((n & 2) << 4) + ((n & 4) << 6)
        + ((n & (8+256)) >> 2) + (n & 16)
        + ((n & 64) >> 6) + ((n & 128) >> 4);
    while ((n & 73) == 0) 
        n >>= 1;
    return n;
}
public static int Count3x3_3() {
    bool[] visited = new bool[512];
    int count = 0, r;
    for (int i = 0; i < 512; i++) {
        if (visited[i])
            continue;
        if ((i & 7) == 0 || (i & 73) == 0)
            continue;
        count++;
        if ((r = Rotate(i)) == i) continue;
        visited[r] = true;
        if ((r = Rotate(r)) == i) continue;
        visited[r] = true;
        visited[Rotate(r)] = true;
    }
    return count;
}

这在同一台机器上运行大约 3 微秒。