查找包含所有可能的 3x3 位模式的 NxM 网格

本文关键字：模式 NxM 网格 3x3 包含所 有可能 查找 | 更新日期: 2023-09-27 17:55:26

更新：这被称为de Brujin环面，但我仍然需要在C#中找出一个简单的算法。

http://en.wikipedia.org/wiki/De_Bruijn_torus

http://datagenetics.com/blog/october22013/index.html

我需要尽可能密集地组合 3x3 位网格的所有值。3x3 位网格是指 3x3 网格，其中每个位置都与这个问题中的打孔概念有点相似：

查找 3x3 打孔器的所有组合

3x3 位网格示例：

XXX .X. ...
XXX .X. .X.
XXX .X. ...

目标

我想打包所有 512（实际上是 256，因为中心位始终打开）可能的值，以便它们在单个 NxM 网格中重叠。

不完整的示例：

此示例将 ~25 个可能的值打包到 7x7 网格中。

.......
.X.XXX.
.......
.X.XXX.
.X.XXX.
.X.XXX.
.......

已知事项：

  • 有 2^9 （512） 个唯一值。
  • 我只关心 2^8 （256） 个值，因为我需要中心位始终打开。

尝试

我手工尝试了许多不同的技术，但无法想出一个简单的算法。

所以，我想写一个C#程序来创建这个，但我也没有看到一个简单的方法。

在我看来，甚至没有明显的蛮力方法。似乎任何蛮力尝试都会接近 512！在最坏的情况下组合。

观察

每条边只有 8 个可能的值。 

X...X.XXX. //(8+2 bits) Exhausts all values in the same problem with 1-Dimension.
.X.XXX.    //(5+2 bits) The above simplifies when the center bit must be on.

目的

这实际上将用于基于2D瓷砖的游戏。

游戏有N个可能的地面碎片。鉴于地面可能在任何情况下出现，设计师需要一种方法来表达应该为任何给定情况选择哪种瓷砖。

包含所有可能情况的紧凑网格是指定在每种情况下使用哪个磁贴并消除所有冗余的最有效方法。

更新

例

....
.XX.
.XX.
....

以上是允许表达 4 种情况的基本模式，我将对其进行修改以使用其他 ascii 值来表示应在每种情况下使用的结果：

....
.AG.
.HH.
....

其中 A，G，H 分别表示应用于每种情况的特定模式。

因此，如果找到以下模式：

...
.XX
.XX

这与上面导致"A"的模式相匹配，因此在这种情况下将使用"A"。 

???
?A?
???

目的是详尽无遗地表达每种可能的情况会产生什么结果。

实践中

我能够尝试这样做，发现结果太随机，无法很好地实现目标。作为一个人，很难在每种情况下选择正确的价值观，因为或混乱。手动分组相似模式仍然效果更好。

查找包含所有可能的 3x3 位模式的 NxM 网格

将所有 3x3 模式打包到带有 De Bruijn 序列的 3xN 网格中

让我们将每个 height-3 列视为 0 到 7 之间的单个数字，我们可以这样做，因为有 8 个可能的 height-3 列。 现在，将所有 512 个可能的 3x3 模式打包到最小可能的 3xN 大小网格中，相当于找到参数为 B（8， 3） 的 de Bruijn 序列。 这个网格的大小为 3x514：在第一个 3x3 之后，每增加一个 3x3 只需要我们多花 1 列，这对于高度为 3 的网格来说显然是最好的。

基于该维基百科页面，似乎最有效的方法是通过在前一个序列的 de Bruijn 图中找到欧拉循环来构建一系列 de Bruijn 序列 B（8， 1）、B（8， 2）、B（8， 3）（因为另一个建议的算法涉及找到哈密顿路径， 这是一个NP完全问题，其难度相当于旅行推销员问题）。

还有de Bruijn

tori，de Bruijn序列的2D类似物，更直接地接近你打包到NxN网格的目标。 然而，从该页面中不清楚如何甚至是否有可能为 3x3 图案构建 de Bruijn 圆环（他们只说已知它们可以为偶数大小的正方形图案构建，并且奇数尺寸的正方形图案的环面本身不能是正方形的——所以大概 NxN 已经出来了）， 此外，它们满足的强唯一性约束对于您的应用程序来说可能是不必要的。

下面的 520 位字符串包含所有 3x3 位模式作为连续子序列：

XXXXXXXXX.XXXXXXX..XXXXXX.X.XXXXXX...XXXXX.XX.XXXXX.X..XXXXX..X.XXXXX....XXXX.XXX.XXXX.XX..XXXX.X.X.XXXX.X...XXXX..XX.XXXX..X..XXXX...X.XXXX.....XXX.XXX..XXX.XX.X.XXX.XX...XXX.X.XX.XXX.X.X..XXX.X..X.XXX.X....XXX..XX..XXX..X.X.XXX..X...XXX...XX.XXX...X..XXX....X.XXX......XX.XX.XX.X..XX.XX..X.XX.XX....XX.X.XX..XX.X.X.X.XX.X.X...XX.X..X..XX.X...X.XX.X.....XX..XX...XX..X.X..XX..X..X.XX..X....XX...X.X.XX...X...XX....X..XX.....X.XX.......X.X.X.X..X.X.X....X.X..X...X.X...X..X.X......X..X..X.....X...X....X.........XXXXXXXX

或者，如果您愿意，可以使用j_random_hacker的版本：

............X..X..X..X...........X..X..X..X...........X..X..X..X...........X..X..X..X.X..X..X..XX.XX.XX.XX.X..X..X..XX.XX.XX.XX.X..X..X..XX.XX.XX.XX.X..X..X..XX.XX.XX.XX.........X..X..X..X........X..X..X..X........X..X..X..X.X..X..XX.XX.XX.XX.X..X..XX.XX.XX.XX.X..X..XX.XX.XX.XX.X..X..XX.XX.XX.XX......X..X..X..X.....X..X..X..X.X..XX.XX.XX.XX.X..XX.XX.XX.XX.X..XX.XX.XX.XX.X..XX.XX.XX.XX...X..X..X..X.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..
......X..X........X..X.....X..X........X..X.X..XX.XX.X..X..XX.XX.X..XX.XX.X..X..XX.XX.....X..X........X..X.....X..X........X..X.X..XX.XX.X..X..XX.XX.X..XX.XX.X..X..XX.XX...X..X........X..X.XX.XX.X..X..XX.XX.XX.XX.X..X..XX.XX..X..X........X..X..X..X........X..X.XX.XX.X..X..XX.XX.XX.XX.X..X..XX.XXXXXXXX.XX.XXXXXXXXXXX.XX.XXXXXXX.XX..X..X.XX.XX.XX..X..X.XX.XXXXXX.XX.XXXXXXXXXXX.XX.XXXXXXXXX.XX.XXXXXXX..X..X.XX.XX..X..X.XX.XXX.XX.XXXXXXXX.XX.XXXXXX......X..X.....X..X.X..XX.XX.X..XX.XX...X..X.XX.XX.XX.XXXXXXXXXX..
...X.....X.....X.....X.XX.X..XX.X..XX.X..XX..X.....X.....X.....X.XX.X..XX.X..XX.X..XX..X.....X.....X.....X.XX.X..XX.X..XX.X..XX..X.....X.....X.....X.XX.X..XX.X..XX.X..XXXXX.XXXXX.XXXXX.XXXX..X.XX..X.XX..X.XXX.XXXXX.XXXXX.XXXX..X.XX..X.XX..X.XXX.XXXXX.XXXXX.XXXX..X.XX..X.XX..X.XXX.XXXXX.XXXXX.XXX...X.....X.....X.XX.X..XX.X..XX..X.....X.....X.XX.X..XX.X..XX..X.....X.....X.XX.X..XX.X..XXXXX.XXXXX.XXXX..X.XX..X.XXX.XXXXX.XXXX..X.XX..X.XXX.XXXXX.XXX...X.....X.XX.X..XX..X.....X.XX.X..XXXXX.XXXX..X.XXX.XXX...X.XXX..

或者，您可以节省空间，只需使用从 0 到 511 的数字，对于大多数计算机来说，这些数字都是 9 位模式。

"包含所有可能情况的紧凑网格是指定在每种情况下使用哪个磁贴并消除所有冗余的最有效方法。

我倾向于不同意。

无论折叠练习的结果如何，为它编制索引以检索给定的 3x3 模式都需要 8 位索引，因为正好有 256 个切片邻接情况。如果您的紧凑表示包含超过 256 个模式（即，如果混合了不需要或冗余的模式），则需要 8 位以上的位进行索引。

但是，如果将 8 位字节

视为位掩码并以某种方式将 8 位映射到 3x3 网格的八个外部图块，则 8 位字节已经可以表示所有可能的邻接情况。这意味着折叠的主网格 - de Bruijn风格或其他风格 - 是多余的，可以省略。

相关文章：