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

Question

更新:这被称为de Brujin torus,但我仍需要在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?
???

目的是详尽地说明每种可能的情况会产生什么.

在实践中

我能够尝试这一点,并发现结果太随意,无法很好地实现目标.作为一个人,很难在每种情况下选择正确的值,因为或者是混乱.类似模式的手动分组仍然可以更好地工作.

Answer 1

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

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

根据该维基百科页面，似乎最有效的方法是通过在前一个序列的 de Bruijn 图（因为另一个建议的算法涉及寻找哈密顿路径，这是一个 NP 完全问题，其难度相当于旅行商问题）。

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