Find a NxM grid that contains all possible 3x3 bit patterns

Question

Update: This is called a de Brujin torus, but I still need to figure out a simple algoritm in C#.

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

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

---

I need to combine all values of a 3x3 bit grid as densely as possible. By a 3x3 bit grid, I mean a 3x3 grid where each place is a bit similar to the hole punch concept in this question:

Find all combinations of 3x3 holepunch

3x3 Bit Grid Examples:

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

Goal

I want to pack all 512 (actually 256 because the center bit is always on) possible values so that they overlap in a single NxM grid.

Incomplete Example:

This example packs ~25 of the possible values into a 7x7 grid.

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

Things already known:

• There are 2^9 (512) unique values.
• I only care about 2^8 (256) values because I need the center bit always on.

Attempts

I tried many different techniques by hand, but could not come up with a straightforward algorithm.

So, I would like to write a C# program to create this, but I also did not see an easy way.

There is not even an obvious brute-force approach that seems possible to me. It seems any brute-force attempt would approach 512! combinations in the worse case.

Observations

Each edge only has 8 possible values.

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. 

Purpose

This is actually going to be used for a 2d tile-based game.

The game has N possible ground pieces. Given that the ground can occur in any situation, the designer needs a way to express which tile should be chosen for any given situation.

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.

Update

Example

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

The above is the base pattern that will allow the expression of 4 situations and I will modify this to use other ascii values to represent the result that should be used in each situation:

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

Where A,G,H each represent a specific pattern that should be used for each situation.

So, if the following pattern is found:

...
.XX
.XX

This matches the pattern that results in 'A' above, so 'A' will be used in that situation.

???
?A?
???

The purpose is to have an exhaustive expression of what each possible situation would result.

In Practice

I was able to attempt this, and found the results too random to work well to achieve the goals. As a human, it was difficult to choose the correct values in each situation because or the disorganization. Manual grouping of similar patterns still works better.

Answer 1

Packing all 3x3 patterns into a 3xN grid with De Bruijn sequences

Let's regard each height-3 column as a single number between 0 and 7, which we can do since there are 8 possible height-3 columns. Now, packing all 512 possible 3x3 patterns into the minimum possible 3xN-size grid is equivalent to finding a de Bruijn sequence with parameters B(8, 3). This grid will be of size 3x514: after the first 3x3, each additional 3x3 costs us only 1 extra column, which is obviously best-possible for a grid of height 3.

Based on that Wikipedia page, it seems the most efficient way to do this is to build up a series of de Bruijn sequences B(8, 1), B(8, 2), B(8, 3) by finding Eulerian cycles in the de Bruijn graph of the previous sequence (since the other suggested algorithm involves finding a Hamiltonian path, which is an NP-complete problem equivalent in difficulty to the Traveling Salesman Problem).

There are also de Bruijn tori, 2D analogues of de Bruijn sequences that more directly approach your goal of packing into an NxN grid. However it's not clear from that page how or even whether it is possible to construct a de Bruijn torus for 3x3 patterns (they only say that it is known that they can be constructed for square patterns of even size, and that a torus for a square pattern of odd size cannot itself be square -- so presumably NxN is out), and in addition, it's likely that the strong uniqueness constraint they satisfy is unnecessary for your application.

Answer 2

The 520-bit string below contains all 3x3 bit patterns as contiguous subsequences:

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

Or, if you prefer, j_random_hacker's version:

............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..

Or you could save space and simply use the numbers from 0 to 511, which, to most computers, are all 9-bit patterns.