找到包含所有可能的 3x3 位模式的 NxM 网格
Find a NxM grid that contains all possible 3x3 bit patterns
更新：这叫做 de Brujin torus，但我仍然需要在 C# 中找出一个简单的算法。
http://en.wikipedia.org/wiki/De_Bruijn_torus
http://datagenetics.com/blog/october22013/index.html
我需要尽可能密集地组合 3x3 位网格的所有值。 3x3 bit grid，我指的是一个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 图块的游戏。
游戏有N个可能的地面棋子。鉴于地面可能出现在任何情况下，设计师需要一种方式来表达在任何给定情况下应选择哪种瓷砖。
包含所有可能情况的紧凑网格是指定在每种情况下使用哪个图块并消除所有冗余的最有效方式。
更新
例子
....
.XX.
.XX.
....
以上是允许表达 4 种情况的基本模式，我将修改它以使用其他 ascii 值来表示应在每种情况下使用的结果：
....
.AG.
.HH.
....
其中 A、G、H 分别代表每种情况下应使用的特定模式。
因此，如果找到以下模式：
...
.XX
.XX
这与导致上述 'A' 的模式匹配，因此在这种情况下将使用 'A'。
???
?A?
???
目的是详尽地表达每种可能情况的结果。
实践
我能够尝试这个，但发现结果太随机，无法很好地实现目标。作为一个人，很难在每种情况下选择正确的价值观，因为组织混乱。类似模式的手动分组仍然效果更好。
使用 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 环面（他们只说已知它们可以为方形图案 of even size，并且奇数大小的正方形图案的环面本身不能是正方形的——所以大概 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..
或者您可以保存 space 并简单地使用 0 到 511 之间的数字，对于大多数计算机来说，这些数字都是 9 位模式。
"A compact grid that contains every possible situation is the most efficient way to specify which tile to use in each situation and eliminates all redundancy."
我倾向于不同意。
无论折叠练习的结果如何，对其进行索引以检索给定的 3x3 模式将需要 8 位索引，因为恰好有 256 个拼贴邻接情况。如果您的紧凑表示包含超过 256 个模式 - 也就是说，如果混合了不需要的或冗余的模式 - 那么您将需要超过 8 位的索引。
但是，如果将 8 位字节视为位掩码并以某种方式将 8 位映射到 3x3 网格的八个外部图块，则 8 位字节已经可以表示所有可能的邻接情况。这意味着折叠主网格（de Bruijn 风格或其他风格）是多余的，可以省去。
更新：这叫做 de Brujin torus，但我仍然需要在 C# 中找出一个简单的算法。
http://en.wikipedia.org/wiki/De_Bruijn_torus
http://datagenetics.com/blog/october22013/index.html
我需要尽可能密集地组合 3x3 位网格的所有值。 3x3 bit grid，我指的是一个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 图块的游戏。
游戏有N个可能的地面棋子。鉴于地面可能出现在任何情况下，设计师需要一种方式来表达在任何给定情况下应选择哪种瓷砖。
包含所有可能情况的紧凑网格是指定在每种情况下使用哪个图块并消除所有冗余的最有效方式。
更新
例子
....
.XX.
.XX.
....
以上是允许表达 4 种情况的基本模式，我将修改它以使用其他 ascii 值来表示应在每种情况下使用的结果：
....
.AG.
.HH.
....
其中 A、G、H 分别代表每种情况下应使用的特定模式。
因此，如果找到以下模式：
...
.XX
.XX
这与导致上述 'A' 的模式匹配，因此在这种情况下将使用 'A'。
???
?A?
???
目的是详尽地表达每种可能情况的结果。
实践
我能够尝试这个，但发现结果太随机，无法很好地实现目标。作为一个人，很难在每种情况下选择正确的价值观，因为组织混乱。类似模式的手动分组仍然效果更好。
使用 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 环面（他们只说已知它们可以为方形图案 of even size，并且奇数大小的正方形图案的环面本身不能是正方形的——所以大概 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..
或者您可以保存 space 并简单地使用 0 到 511 之间的数字，对于大多数计算机来说，这些数字都是 9 位模式。
"A compact grid that contains every possible situation is the most efficient way to specify which tile to use in each situation and eliminates all redundancy."
我倾向于不同意。
无论折叠练习的结果如何，对其进行索引以检索给定的 3x3 模式将需要 8 位索引，因为恰好有 256 个拼贴邻接情况。如果您的紧凑表示包含超过 256 个模式 - 也就是说，如果混合了不需要的或冗余的模式 - 那么您将需要超过 8 位的索引。
但是，如果将 8 位字节视为位掩码并以某种方式将 8 位映射到 3x3 网格的八个外部图块，则 8 位字节已经可以表示所有可能的邻接情况。这意味着折叠主网格（de Bruijn 风格或其他风格）是多余的，可以省去。