c# - 找到包含所有可能的 3x3 位模式的 NxM 网格

Question

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

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

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

---

我需要尽可能密集地组合 3x3 位网格的所有值。所谓 3x3 位网格，我指的是 3x3 网格，其中每个地方都有点类似于这个问题中的打洞概念:

Find all combinations of 3x3 holepunch

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 tile 的游戏。

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

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

更新

例子

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

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

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

其中 A、G、H 分别代表一种特定模式，应该用于每种情况。

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

...
.XX
.XX

这与上面产生“A”的模式相匹配，因此在这种情况下将使用“A”。

???
?A?
???

目的是详尽地表达每种可能情况的结果。

实践

我能够尝试这样做，但发现结果过于随机，无法很好地实现目标。作为一个人，很难在每种情况下选择正确的值(value)观，因为组织困惑。类似模式的手动分组仍然效果更好。

Answer 1

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

让我们将每个高度为 3 的列视为 0 到 7 之间的单个数字，我们可以这样做，因为有 8 个可能的高度为 3 的列。现在，将所有 512 个可能的 3x3 模式打包到最小可能的 3xN 大小的网格中等同于找到一个 de Bruijn sequence with parameters B(8, 3)。 .此网格的大小为 3x514:在第一个 3x3 之后，每个额外的 3x3 仅花费我们额外的 1 列，这显然对于高度为 3 的网格来说是最可行的。

根据该维基百科页面，似乎最有效的方法是通过查找建立一系列 de Bruijn 序列 B(8, 1), B(8, 2), B(8, 3)前面序列的 de Bruijn 图中的欧拉循环(因为另一个建议的算法涉及寻找哈密顿路径，这是一个 NP 完全问题，难度等同于旅行商问题)。

还有de Bruijn tori ，de Bruijn 序列的二维类似物，更直接地接近您打包到 NxN 网格中的目标。然而，从该页面上不清楚如何甚至是否有可能为 3x3 图案构造 de Bruijn 环面(他们只说已知它们可以为 均匀大小 的方形图案构造，并且奇数大小的正方形图案的环面本身不能是正方形的——因此大概 NxN 不成立)，此外，它们满足的强唯一性约束很可能对您的应用程序来说是不必要的。