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.

Devilfish

When you say compact, do you mean that when you store the grid it needs to be smaller than 512 bits (64 bytes)? – Grown

Does the grid you are "packing" these 3x3 patterns into need to be NxN? Or can it be 3xN? If so, I know a cute way to do this. – Chromatid

@MartinParkin The ideal case would have 512 bits plus the border. There is no better solution. (I guess if wrapping were allowed, even the border could be eliminated.) – Devilfish

@Chromatid It can be any size of NxM including 3xM. Ideally, it should be easy to read by a human, but that is not my main concern yet. – Devilfish

@RickLove: OK, but for future reference, writing "NxN" implies that the grid has to be square -- if you want to allow arbitrary rectangular grids, use 2 different variable names for its dimensions. – Chromatid

@Chromatid Right, I saw the problem just as you were commenting...Fixed – Devilfish

BTW, while I'm griping :-P the word "packing" in computer science usually implies that the things being packed need to be disjoint (nonoverlapping). I'd call this "Finding an NxM grid that contains all possible 3x3 bit patterns". – Chromatid

Ah, I did not know that packing implied non-overlap... using your suggested Title – Devilfish

Can you say more about how the grid would be accessed in real-time? It seems to me that simply the numbers from 0 to 511 not only express but are all 9-bit patterns. – Cutter

As an optimisation strategy this is futile (seeing that the platforms where C – Scranton

As an optimisation strategy this is futile (seeing that the platforms where C# is available don't include 8-bit CPUs); there are plenty better, simpler ways to accomplish that functionality. From the POV of an intellectual exercise: the constraint that the centre bit of a 3x3 pattern be 1 means that patterns with a 0 bit in the centre of the right column cannot have a successor. E.g. if the current pattern is ??? ?x? ?.? and you add any column then the right-most three columns make ?x? ?.? ???. There are more such problems. Hence any solution must contain unwanted, redundant sub-patterns. – Scranton

@Scranton This is not for optimization. This is to express what tile to use in any given situation. I will change the X to a different letter to express what tile to use in that situation. – Devilfish

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.

Chromatid

Well, that is a bit more efficient than having each 512 3x3 grid listed. It reduces the work by 1/3... However, I was hoping for something a little better than that. – Devilfish

The article on de Brujin tori is very helpful – Devilfish

Compared to the naive solution it reduces the size to 1/3, i.e., by 2/3. – Chromatid

Ok, so I need to construct a de Brujin torus for a 3x3 grid. It is known from the article that the result cannot be square, but it implies that it should be possible... I'm going to look at how to code this next. – Devilfish

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.

Instrumentation

What algorithm did you use to obtain this value? – Devilfish

@RickLove the algorithm was j_random_hacker's idea. – Cutter

Answer 3

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

I'm inclined to disagree.

Regardless of what the result of your folding exercise looks like, indexing it to retrieve a given 3x3 pattern will require 8-bit indices since there are exactly 256 tile adjacency situations. If your compact representation contains more than 256 patterns - that is, if there are unwanted or redundant patterns mixed in - then you will need more than eight bits for indexing.

However, an 8-bit byte can already represent all possible adjacency situations, if you treat it as a bitmask and map the eight bits to the eight outer tiles of a 3x3 grid in some fashion. This means that the folded master grid - de Bruijn style or otherwise - is superfluous and can be dispensed with.

Scranton

I am not trying to list all possible index values. As you stated, each possible index is a 8 bit value. I am using this as a mapping from each index to a specific value to use for that index. I will do this by changing the X to another character in each situation. – Devilfish

In that case a byte lookup table (permutation) is the most compact simple data structure that allows you to specify arbitrary mappings from 8-bit index to 8-bit bit mask (pattern), including arbitrary permutations. A solution of the de Bruijn problem would give you only one fixed mapping; besides f(i) = i there are other fixed mappings/permutations that are easy to compute, like the Gray Code f(i) = (i >> 1) ^ i and many others. In general, a look at things from the POV of Information Theory (entropy/coding) is often helpful; it explains why even de Bruijn can't beat Shannon. – Scranton

@RickLove I don't understand how you intend to use the sequence - can you give an example of what you call "index" and "value" would actually be? And why you could not simply use numbers between 0 and 511, which are all 9-bit patterns? – Cutter

My purpose is to have an exhaustive expression of what each pattern will result: Updating the Question to demonstrate. – Devilfish