找到 3x3 打孔的所有组合

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

然后复杂性让我震惊。特别是因为工作人员在打孔时并不那么小心，所以这些看起来都是一样的：

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

问题：如何编写测试来考虑旋转和移位？

迄今为止的勤奋和想法：

• 二进制感觉像是这个方程的一个明显的部分
• 找到独特的模式后，将其存储在内存中，以便将来的模式可以针对它进行测试
• 有 4 种旋转可能性。
  Edit:我所说的“旋转”是指你可以采用任何形状并将其旋转 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 / /
. . . . . . .   . . . . . . .   . . . . / / /
. . . . . . .   . . . . . . .   . . . . / / /

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

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

对于这些模式，我们需要检查旋转后的版本是否相同。为此，我们应用最多三个 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);

In 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.023ms。

EDIT：通过使用 4 个观察结果，您可以获得额外 7 倍的改进：

1. 我们可以使用简单的访问数组来代替哈希集。如果以前见过某种模式，我们就不会计算它。这也消除了跟踪内循环中“最低”模式的需要。如果访问了一个模式，那么它的最低旋转模式也会被访问。
2. 如果我们没有 180 度旋转对称性，那么第三次旋转将不会产生原始图案。第四次旋转总是会发生，所以没有必要。
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μs。