We help IT Professionals succeed at work.

Select patterns on a n x n grid where the number of patterns = 1

rd707
rd707 asked
on
I have a C# program that creates a series of ever increasing n x n grids.

For each created grid, I create every possible permutation of filled cells in that grid.

For each pattern created by the filled cells, I only want to retain grids where there is a single pattern on the grid - i.e.:

where the number of filled cells = the size of the largest pattern

For the purposes of this program, I only consider shapes to include cells above, below, to the left or to the right of a filled cell - not diagonally

Currently, I'm finding the first cell in the grid (actually modelled in a one-dimensional array) and then calling the following routine recursively:

- Add the passed cell index to a linked list and increment the count
- If there is a filled cell to the left, right, above or below that is not in the list, call the routine with this cell index.

If the final count = the number of filled cells in the grid then retain the pattern, else discard

This doesn't strike me as terribly efficient - is there a better way?
Comment
Watch Question

Sorry, I do not understand what your program does. Maybe you could provide examples of a grid (even a 2x2 or 3x3) and show what the program produces. Since you already have a program, then posting the output (in the code section if it's long) might be helpful for me to understand your program. If you could also annotate what patterns are being kept and what are discarded, that would also help.
You want to discard all grids with disconnected shapes. Why not draw only connected shapes?

Start at 1;1. Fill recursively up, down, right, and left (if empty). At each stage record a unique digest of your pattern (the binary representation works fine), or prune if it already exists (it was already explored). When the function is exhausted, cross out 1;1 permanently (it has to be blank in all new patterns) and explore 1;2. Continue to the last cell.

This will create all possible pattern, while never attempting to create an illegal one.

Thought?
(°v°)
Another idea: the generative approach.

* Create a cell, fill it. That is your first list of patterns (one item).
* Create a new contiguous cell. From the previous list, create all patterns where the new cell is blank (they are all legal). Then select all having at least one contiguous cell filled, and thus create all legal patterns with the new cell being filled.
* Repeat.

The first cell of a new row or column has only one contiguous cell with the existing patterns; others can have two.

It's the same idea, but with much less tests.

(°v°)

Author

Commented:
phoffric:

I've attached some output for grid size 3.
As you can see, all the reject grids have > 1 pattern in them.


 

EXAMPLES OF SOME ACCEPTED PATTERNS

.X.
XXX
.X.

X.X
XXX
X.X

XXX
.X.
XXX

XXX
X.X
XXX

XXX
XXX
XXX

EXAMPLES OF SOME REJECTED PATTERNS

..X
...
XXX

X.X
...
XXX

.XX
...
XXX

XXX
...
XXX

Open in new window

If I understand you correctly, your main goal is not pattern creation (which you do via all permutations of the NxN grid) but of pattern recognition. I just took a quick look and will give you my off the cuff comment. (I'll think more about this tomorrow, or others will correct me if I made a mistake or if they have a better algorithm.)

From your examples, I infer that a pattern is a set of connected cells. If a grid has two patterns, then there are two sets of connected cells where pattern 1 cannot reach pattern 2 via horizontal and vertical movements.

Here is a different approach than you described in your OP. Overview: There are less nodes in the linked list. There are multiple linked lists, one for each of N rows. A node represents a run of filled cells with a color designation (i.e., a number). So, if the grid is 100x100, and the first row has a single run of filled cells from 3 to 88, then there will be one node for row 0: {3,88,1}. The idea is to find the number of patterns (i.e., colors); and also include some short-circuits which can stop the algorithm quickly. I've illustrated one example where the algorithm stops in the 2nd row.

Although there could be recursion in a natural way, when scanning above or below rows for overlap, I believe that it will be easy to come up with a simple non-recursive solution (in case that is determined to be significantly more efficient).

1) define Row[N] where each element of Row[i] is a pointer to a linked list
2) Linked list consists of ordered set of {low,high,color} values corresponding to a connected horizontal run of cells that are colored (via a number); for example (x == filled in; ~ == not filled in)
3) Example of short-circuit:
0123456789
~x~xx~~xx~
xx~~~x~x~x
R[0] -> {1,1,1} -> {3,4,2} -> {7,8,3} // colors in 1st row are 1-up numbers
R[1] -> {0,1,1} -> {4,4,-1} -> {7,7,3} -> {9,9,-1} // colors in 2nd row are found from overlap in 1st row

The color -1 means that there was no overlap in the above row. That in itself is not a show-stopper.
But, then all the colors in the first row must be included in the 2nd row. If not, stop - there must be more than one pattern. In above example, you can stop immediately, since the R[0] has node {3,4,2} whose color 2 is not found in R[1].

3) Example with single pattern with more clarifications:
0123456789
~x~xxxx~xx  R[0]
~xxx~xx~~x  R[1]
~xxxx~~xxx  R[2]
~~~~xxxx~x  R[3]
~~~~~~~~~~  R[4]
. . .
~~~~~~~~~~  R[9]
R[0] -> {1,1,1} -> {3,6,2} -> {8,9,3} // colors in 1st row are 1-up numbers
R[1] -> {1,3,1} // got color from smallest overlap found
Before moving on, adjust any other overlaps from this node in R[0]
So, since {3,6,2} overlaps with {1,3,1}, then change color of {3,6,2} to {3,6,1}

R[0] -> {1,1,1} -> {3,6,1} -> {8,9,3} // changed {3,6,2} to {3,6,1}
R[1] -> {1,3,1} -> {5,6,1}
R[1] -> {1,3,1} -> {5,6,1} -> {9,9,3}
R[2] -> {1,4,1} -> {7,9,3}
R[3] -> {4,7,1}
Before moving on, adjust any other overlaps from this node moving to R[2]
R[2] -> {1,4,1} -> {7,9,1} // {7,9,3} changed to {7,9,1}
Before moving on, since an R[2] node changed, adjust any other overlaps from {7,9,1} in R[1]
R[1] -> {1,3,1} -> {5,6,1} -> {9,9,1} // changed {9,9,3} to {9,9,1}
Moving upwards, then:
R[0] -> {1,1,1} -> {3,6,1} -> {8,9,1} // {8,9,3} changed to {8,9,1}

So, now we have (and adding last node to R[3]):
R[0] -> {1,1,1} -> {3,6,1} -> {8,9,1} // {8,9,3} changed to {8,9,1}
R[1] -> {1,3,1} -> {5,6,1} -> {9,9,1} // changed {9,9,3} to {9,9,1}
R[2] -> {1,4,1} -> {7,9,1} // {7,9,3} changed to {7,9,1}
R[3] -> {4,7,1} -> {9,9,1}

4) Efficiency Enhancement
Pruning the linked list. For example, after processing Row[1], it appears that R[0] -> {1,1,1} no longer serves any purpose. So, it can be removed from the R[0] list.

5) You may need to keep track of the number of distinct colors (or just scan the pruned linked lists when done). When you are done that number is the number of patterns in your grid. (This is just a first-cut guess; maybe some tweaking/revamping needed.) (p.s. - I see you have no code, which is fine, since I know C, C++, but not C#.)
phoffric,

This vaguely reminds me of maze creation algorithms. It's perhaps possible to do what you suggest without backtracking to earlier rows, though.

I'm afraid I have only obfuscated code at hand...

    http:/Q_10247651.html#2285783
    http:/Q_22476938.html#18814116

(°v°)

Author

Commented:
Sorry, looking at this between other things:

> You want to discard all grids with disconnected shapes. Why not draw only connected shapes?

I'm not sure that would be any simpler and it would be difficult to say with confidence that you'd covered all the permutations without bit masking the grid.

I think there may be some mileage in checking the grid as it is built though. In the attached (4 x 4) example we could immediately discard this pattern build once we'd started a new disconnected pattern in row 2.
XX..
..X

Open in new window

Author

Commented:
That is superb.

Thanks very much.
You are very welcome. It was just a thought. The short-circuit considerations is one useful optimization. After seeing your 4x4 example, I now think that you are trying to create all single pattern examples. I will think about that since it changes the problem.

The following may possibly overlap with some of harfang's ideas, but to be honest, I didn't completely follow, and didn't have time to decipher the obfuscated code. I hope harfang will elaborate on the OC if he has time. :)

I'm trying to get a little greedy at least for the easy stuff.

Say you have a 8x8 grid (consider the grid as 8 bytes). My initial thinking is that certainly for some patterns, the next pattern is quickly determined. For example, start off with all 0's giving 0 pattern. Work on first row treating it as a binary number. First the naive approach:
add 1 ==> 1 one pattern (no effort)
add 1 ==> 2 one pattern (no effort)
add 1 ==> 3 one pattern (no effort)
add 1 ==> 4 one pattern (no effort)
add 1 ==> 5 two pattern (disjoint - little effort)
and so on. But for this first case there are 256 naive permutations. But, all that really has to be done is take a single 1 and walk it across the first row for 10 cases (all are single patterns). Then take 3 (two consecutive 1's) and walk them across for 9 cases (all are single patterns). Then take 7, and 0xF, and so on to 0xFF. And this was for rows R[1] - R[7] being all 0's.

Naturally, after working R[0] and getting all the patterns, those R[0] patterns apply equally well to any other R[i] with all other rows being 0.

Now we fill up R[1] to create good patterns. This time R[0] is filled with 0xFF and to break it up, we do the walk, not of consecutive 1's, but of consecutive 0's sandwiched between two 1's. Now R[0] will see all cases of two disjoint runs of 1's. For each of these cases, R[1] has an obvious set of a single pattern that overlaps both patterns in R[0].

Again, these two consecutive rows can be walked down the grid so that every single pattern in the first two rows will be repeated for the 2nd and 3rd rows, and the 3rd and 4th rows, etc.

I suspect that there is a lot more optimization that can be greedily obtained once a configuration is understood. We can shoot out some ideas and see if there is a simple algorithm to take advantage of these thoughts even as the design gets more complicated.
BTW - if you don't mind, I am very curious as to what kind of application this will be used for.
> I hope harfang will elaborate on the OC if he has time. :)

I wish! I studied the algorithm of the second example with my brother (I got stuck at some point) many years ago, and the idea is to maintain row-by-row chains of connected cells. When writing a new row, each chain needs at least one exit; when writing the last row, all chains need to connect. That way, the inside of the maze is one shape... Your suggestion reminded me of that.

Cheers!
(°v°)

Author

Commented:
Pattern selection comes up in a number of problems which is why it is of interest to me.

Problem 275 in Project Euler (http://projecteuler.net) relates to selection of patterns on a grid.

I'm also interested in why seed population patterns always seem to be irregular for continual population growth in Conway's game of life (http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life).

OK, I looked at:
     http://projecteuler.net/index.php?section=problems&id=275
and to understand what they were talking about, I looked at:
    http://en.wikipedia.org/wiki/Polyomino

So, I suppose that you are looking for all Polyomino of order 1 to N^2 that are confined

 with or without holes and including reflections and translations around any axis. If N=10, then there are 2^100 permutations to consider. Too long to compute by brute force.

Have you thought more about short-circuit or heuristics to reduce the number of cases? For example, here's one simple heuristic: Suppose you already have determined a single pattern (i.e., all colors are 1). You are permuting a particular row, R[k]. You change a single 1 to a 0. Now let that cell be the center of a 9 cell square. If all the 1's on the perimeter of the square are connected to each other, then changing the center from a 1 to a 0 did not result in more than one pattern; so you are done with this permutation.
>> This vaguely reminds me of maze creation algorithms. It's perhaps possible to do what you suggest without backtracking to earlier rows, though.

Yes. No backtracking is needed.
REVISION 1:
Idea is to define a graph of nodes that represent the colors. When one color merges with another as you go down the rows, then the adjacency matrix connects those two color nodes in the graph. So, now you don't have to recolor the runs in the upper rows.
REVISION 2:
Original Example in http:#32968775
3) Example of short-circuit (Now modified so it does not short-circuit in order to illustrate new color scheme)
0123456789
~x~xx~~xx~
xx~x~x~x~x
R[0] -> {1,1,1} -> {3,4,2} -> {7,8,3} // colors in 1st row are 1-up numbers
R[1] -> {0,1,1} -> {3,3,2} -> {5,5,-1} -> {7,7,3} -> {9,9,-1} // colors in 2nd row are found from overlap in 1st row
No longer set a color to -1. Instead, just keep using 1-up numbers. In R[0], we have three nodes:
  1  2  3 (all disconnected)
In R[1], we have a run of (5,5) and (9,9) with no inherited color from R[0]. So, instead of coloring them as -1, instead give them 1-up numbers 4 and 5.
R[1] -> {0,1,1} -> {3,3,2} -> {5,5,4} -> {7,7,3} -> {9,9,5}
Every node that exists before reviewing R[1] must be present in R[1] (or connected to a color in R[1] via the newly defined graph. As you see now, nodes 1, 2, 3 are represented in R[1], so no longer do we have a short circuit.

Now there are five nodes:
  1  2  3 4 5 (all disconnected)

Suppose R[2] is added as follows:
0123456789
~x~xx~~xx~  R[0]
xx~x~x~x~x  R[1]
~x~xxx~xxx  R[2]
R[1] -> {0,1,1} -> {3,3,2} -> {5,5,4} -> {7,7,3} -> {9,9,5}
R[2] -> {1,1,1} -> {3,5,2} -> {7,9,3}
When choosing the inherited color, select the lowest number. Since (3,5,2) also overlaps with (5,5,4), then nodes 2 and 4 are now connected; and likewise nodes 3 and 5 are now connected. The graph now looks like:
      1  2-4  3-5
So, from this point on, it is not necessarily true that a short circuit occurs if the next row, R[3] does not have all 5 colors represented explicitly, since R[2] has only colors 1, 2, and 3.
In subsequent rows, there may still be inherited values of 4 and 5 (well not for the graph shown, but in more complex graphs), and those colors can remain.

So, let me know if you agree that this eliminates the need for backtracking with just a relatively small graph.

BTW - if you want to eliminate patterns with holes (so that there are cycles in the paths), then this color scheme should be able to detect cycles. For example, if a run inherits colors from two or more runs in the previous row, and at least two of the preceding colors are the same, then we have a hole, don't we? Likewise, if the colors are different, but the graphs show that two of the colors are connected, then we also have a hole.
Your enthusiasm is communicative... I almost reached for pen and paper! -- (^v°)

Author

Commented:
Thanks for the further help but I'm really more interested in the process. That is to say, building a toolkit to solve further problems rather than the actual problems themselves.