# Logic that can traverse all possible layouts, but not checking every combination of identical pieces?

Suppose we have a grid of arbitrary size, which is filled by blocks of various widths and heights. There are many 2x2 blocks (meaning they take a total of 4 cells in the grid) and many 3x3 blocks, as well as some 5x4, 4x5, 2x3, etc.

I was hoping I could set up a program that would look at all possible layouts, and rank them, and find the best one. Simply it would look at all possible positions of these blocks, and see what setup is the best rank. (the rank based on how many of these can be connected by a roadway system of 1x1 road blocks, and how many squares can be left empty after this is done. - wanting to fit the most blocks as possible with the least roads.)

My question, is how should I traverse all the possibilities? I could take all the blocks and try them one at a time, but since all 2x2 blocks are equal, and there are a couple dozen of them, there is no point in trying every combination there, as in the following

``````AA BBB
AA BBB
CCBBB
CCEEE
DD EEE
DD EEE
``````

is exactly the same as

``````CC EEE
CC EEE
AAEEE
AABBB
DD BBB
DD BBB
``````

You notice that there are 2 3x3 blocks and 3 2x2 blocks in my two examples. Based on the model I have now, the computer would try both of these combinations, as well as many others. The problem is that it is going to try every single possible variation of my couple dozen 2x2 blocks. And that is sorely inefficient.

Is there a reasonable way to take out this duplicated work, somehow getting the computer program to treat all 2x2 blocks as equal/identical, instead of one requiring rearranging/swapping of these identical blocks?

Can this be done?

My current pseudo code

``````blocks = array of all blocks [2x2, 2x2, 2x2, 3x3, 3x3]
iterate(0)
function iterate(i) {
currentblock = blocks[i]
for each possible position of currentblocks
see if there are any more blocks to place, and if there are
iterate(i+1)
else
all blocks are placed, so get the rank
if the rank is better than thebestrank
thebestrank = rank
thebestposition = position
}
at this point, we proceed with thebestposition.
``````
-

## 4 Answers

When you iterate over each possible position of currentblocks, instead of placing it automatically, check a 'previously placed' list, and if this current combination of blocks (including the one you're considering placing) has already been tried, skip this possible position. When comparing the combinations, treat similarly sized blocks as equivalent.

When you successfully place a block, add the current combination of block positions to the 'previously placed' list before recursing.

You are basically running a depth-first search that has multiple ways of reaching equivalent goals - so you need to keep track of previous approaches to ensure that you don't duplicate them.

-
Accepting top voted answer, though I never finished this project. – George Bailey May 11 '15 at 14:24

Instead of telling the computer program to test each different type of 2x2 block separately, tell it to only test one of those types of 2x2 block.

Addendum: In your pseudocode, all you need to do to implement this is to change your first line to:
`blocks = array of all blocks [2x2, 3x3]`

-
+1. To @GeorgeBailey, As in, "Not this apple, but apples in general", a type being representative of individuals of that type. – Arcane Engineer Oct 28 '12 at 0:19

Off the top of my head to place some identically sized blocks without duplicates you'll want something like this.

``````  Firstly enumerate all legal positions for a 2x2 block.

function PlaceBlock(int blockcount, int start = 0)
{
if (blockcount <= 0) {OutputCurrentSetup(); return;}
for (int i=start; i < legal_position_count; i++)
{
if (legal_position[i].IsBlocked()) continue;
legal_position[i].Apply();
PlaceBlock(i + 1, blockcount - 1);
legal_position[i].UnApply();
}
}
``````
-

Thanks for your quick answers. I did find a simple way to edit my code to prevent duplicated iterations. However, it seems my idea of checking every possible combination is impractical, due to the sheer magnitude of the total number of possible combinations, particularly when you have blocks averaging a size of 3x3 filling over 50% of the container which is 30x40

-
Note that depending on what your notion of 'best' is, there are a number of optimization algorithms that may be able to help you find much better (if not perfect) solutions - basic hill-climbing algorithms being the most straightforward and simulated annealing being perhaps the most flexible 'good' algorithm for your problem. I'd encourage asking another question about 'how can I find a good solution to this problem?' with more details as to just what you're looking for in your layout... – Steven Stadnicki Nov 7 '12 at 22:24