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

Question

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.

Answer 1

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)