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?

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?

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°)

* 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°)

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

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°)

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.

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°)

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.

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.

## Premium Content

You need an Expert Office subscription to comment.Start Free Trial