# Split a grid into shapes that can be moved back from 4 directions

Basically I have 4 grids Left, Right, Top, Bottom. Player can choose each of them and move all the blocks on that grid to the Middle grid to fulfill it, like tetris from 4 directions:

      |0 0 0|
|0 0 0|             (0 is empty, 1 is generated block)
|0 0 1|
_ _ _         Bottom->Mid  Right->Mid  Top->Mid   Left->Mid
|0 0 0|0 0 0|0 1 0|    |1 0 0|     |1 1 0|     |1 1 1|    |1 1 1|
|0 0 0|0 0 0|0 1 1|    |1 0 0|     |1 1 1|     |1 1 1|    |1 1 1| -> Win! Generate
|1 0 0|0 0 0|0 1 1|    |0 0 0|     |0 1 1|     |0 1 1|    |1 1 1|    another game.
_ _ _
|0 0 0|
|1 0 0|
|1 0 0|


The point here is to make sure there is at least 1 way for player to combine all 4 grids.

What I've tried so far is generate the right order first (Left->Right->Top....), then generate all the blocks 1 by 1. When a block is generated, i perfomn a check with the generated order (move all the blocks in Left to Mid, then Right then Top...) to see if its still working, the code is similar to this:

// (left->right, top->right->botttom->left, top... it doesn't have to be all 4 directions)
Random the right direction order.

Generate all possible coordinates from all the directions from the path above.
Initialize an empty list to store all chosen coordinates.

While(!(Generate enough x*x block))
{
Get one coordinate from all possible coordinates

if (Perform a check with the right order and the chosen list)
Add it into the chosen list.

}


The problem here is a block can be wrong at this point, but it can become right when another block is generated:

          |0 0 0|                                      |0 0 1|
|0 0 1|                                      |0 0 1|
|0 0 1|                                      |0 0 1|
_ _ _                                        _ _ _
|0 1 0|0 0 0|0 0 0|                          |0 1 0|0 0 0|0 0 0|
|1 0 0|0 0 0|0 0 0|                          |1 0 0|0 0 0|0 0 0|
|1 0 0|0 0 0|0 0 0|                          |1 0 0|0 0 0|0 0 0|
_ _ _                                        _ _ _
|0 1 0|                                      |0 1 0|
|0 1 0|                                      |0 1 0|
|0 0 0|                                      |0 0 0|
At this point the logic is wrong          But if I add 1 more block to the
with Top->Left->Bottom order.               top grid, it'll become right.


There is no way to check if the each block is right or wrong without re-calculate all the generated blocks logic

So i want to ask if there a better way, algorithm to do it.

• Am I understanding correctly that the top and bottom get flipped, but left and right get slid (translated)? Or can any of the blocks be slid or flipped? What about rotations? – user1118321 Nov 24 '17 at 20:04
• All the blocks in a grid will be slid into the middle step by step like a tetris shape, no rotations. And all the blocks in that grid will stop when any of them touch a middle's block or moved enough step (3 steps if its a 3x3 grid). – B Teddy Nov 25 '17 at 3:15
• Ah, I see. I misunderstood how it worked. I think I get it now. – user1118321 Nov 25 '17 at 4:13

It turns out there are only 9 968 valid & solvable 3x3 puzzles of this form (if my math is right), so one simple option is to just generate ALL of them, then shuffle this list as a "deck" of puzzles to present to the player.

(The storage requirements are quite modest. As you'll see, we can store each board as a 32-bit integer with room to spare, so we can store the whole shebang in under 40 kiB without even trying to be frugal)

This eliminates any biasing in the puzzle generation process (other generation methods I thought of tend to produce big blocks for the early selections, and sparse blocks at the end, which could give unwanted order hints to the player solving them), or accidental repeats (though I am counting flips/rotations as distinct in the count above).

Here's how I derived that number:

1. Let's label each cell of the fully-assembled/completed puzzle board with the ID of the direction it came from. That gives us 4 options per cell, or 2 bits each.

Multiplied by 3x3=9 cells, that's 18 bits to represent any one completed puzzle. That's comfortably smaller than a 32-bit integer, so we can concatenate all the cells' bits together to make an index between 0 and 2^18 - 1

So, let's loop over each integer in that range, and check whether it represents a solvable puzzle! (262 144 cases to check in total)

2. First, we check whether the puzzle contains at least one cell from each of the Right, Up, Left, and Down grids. If any grid isn't represented, we'll reject the puzzle as invalid. (After all, we don't want to short-change the player and give them a puzzle with fewer choices to make)

That gets rid of 75 664 cases, off to a good start. :)

3. Next, we pick a solution order to try. There are 24 permutations of {Right, Up, Left, Down}, so I just pre-generate them and loop over the set.

For each of these solution orders in succession, we check whether the puzzle is solvable in that order.

We do this by looping over the directions in our permuted order, and looping from the near to far side of each line of cells along this direction, checking that:

• No cell that came from this direction comes later in its row/column than one from an earlier direction.

• At least one row has a cell matching the direction we're checking that directly abuts against one that arrived in an earlier pass, OR against the far side of the grid.

If either of these conditions is not met, then this puzzle can't be assembled in this order, and we try the next one.

If no order yields a solution, then we reject this puzzle as unsolvable and continue. (176 512 potential puzzles fail this test)

Now, we might get multiple solutions for some puzzles. If you like, you could limit your selection to only those with a unique solution, or sort them by decreasing solution count to create a difficulty progression. ;)

Here are the counts I get:

# Solutions       # Puzzles
---------------------------------
1  (unique)         2 224
2                   1 688
3                   3 672
4                     680
5                     832
6                     872
7+                      0


Even though this may seem like a lot of work, it only took about 10 seconds to find all of these solutions exhaustively on my little tablet PC.

(That said, a brute force search like this does NOT scale well - it's exponential in the number of cells in your grid, so bumping up to a 4x4 puzzle, well... my computer's still working away to see if it can solve it)

• Unfortunately, I want to make it work at least in 2x2, 3x3 and 4x4 grids. And fewer choices puzzles are acceptable too (bc its kind of.. boring if there is always 4 choices to make). But still a big thanks to your very detailed answer, it gives me a lot to think about. (sorry i don't even have enough reputation to upvote your answer). – B Teddy Nov 25 '17 at 4:57
• You can still use this method on 4x4 grids, it's just the pre-processing time to build the list of puzzles will be a matter of minutes or hours instead of seconds. That's fine since you only need to do this step once, and store the resulting list of levels to pull from on demand. You can also use this technique to randomly sample for puzzles: generate a random integer in the range, then check if it's a solvable puzzle. In my tests I get a usable puzzle in 1 out of every 20-30 attempts for 3x3 grids, or 1 in 200 for 4x4, fast enough to provide a new puzzle every frame if you wanted. ;) – DMGregory Nov 25 '17 at 5:55
• Yes, the idea of store the board as bits in an integer is super awesome and can be implemented in a lot of places. Thank you for letting me know about such a great technique. – B Teddy Nov 25 '17 at 7:22