Fill up a grid/matrix with pre-defined shapes

Question

Nice to see two up votes for the question. I'll re-word my question now to avoid confusion.

The question is how to fill up a mxn grid/matrix with random but pre-defined shapes without a hole. Pre-defined shapes have a variable k which is how many blocks the shape is made of. Each block is a square and is the same size of a grid square (ie, 1x1 grid). The shape can be rotated to fit into the grid, but does not shrink or expand. k does not change for one round, in another word, m, n, and k does not change while I run the answer script. When I run the script second time, I may change one or all of them. For example, the first time, I may run the answer script with k=4, m=10, and n=20. The script finishes and print out output. The second time I'll k=3, m=6 and n=10. I'll assure m times n and the product modulate k equals zero (m x n % k = 0) to make sure they fit each other mathematically. Okay, one more condition: 1

The script need fill the grid with random shapes from the pool of preset k. When k=2, predefined shapes have just one kind, two blocks together. If you think with no rotation, then it has two kinds, horizontal and vertical. When k=4, that's basically fill up the grid with Tetris blocks, i.e., totally 7 kinds of predefined shapes (each of them can rotate, and make ~20 kinds). What are the predefined shapes for k=5, I don't know yet. The answer can compute that or can be hard-coded, since it's not difficult to find all shapes for k=5.

If the solution is limited, no random is required. For example, m=2, n=2, and k=4; or m=1, n=4, k=2. No other way around, no random.

No holes can be left anywhere in the grid. I think, no prove thought, many grid with mxn and mxn%k=0 will have a solution without hole. Intuitively it sounds reasonable, but mathematically I don't know. If m or n is k's multiples, it's guaranteed to have solution (of all straight bars).

Ideally I want k be a small integer, like k<10, but in the range of 2 to 5 is acceptable. If it is simpler, we can have a fixed k here, such as 4, since Tetris comes with well-known 7 shapes (ITOLJSZ).

I'm looking for solutions preferably in Perl. Python is okay too. Program takes m, n, and k to run each time. Again, I'll have m,n,k fit mxn%k=0.

Effort of myself, I tried in Perl, can solve some cases of k=3 and failed some cases because of singletons (holes) in the edges/corners. Need a good way to check if any block becomes singleton. My text output looks like this (m=4, n=9, k=3). You can of course use this kind or any format that makes sense.

AABB
ACCB
DCEE
DFFE
DFGH
IGGH
IIJH
KKJJ
KLLL

I'll set up bounty of 100 points (thanks those two up-vote, I now have 107 reputations) to award the best solution.

Thanks for your input.

Answer 1

Here are some drive-by thoughts on the design of your solution:

If you don't have to put every piece, you could simply skip around until you just have a bunch of straight lines or squares. The algorithm there would be very easy to come up with - figure out a configuration of pieces to fill 1 or 2 lines and repeat it. If (nm mod k != 0) then there is no solution; otherwise, I suspect there's a general set of rules you could lay out. For instance, if (m mod k = 0) or (n mod k = 0) then you can just use straight lines. Those would be fun to think about but I'll leave them to you.

Actually, reading over your problem, I saw that you wrote 2 <= k <= 5 - then this is really easy because 2, 3, and 5 are primes. Number theory gives us that if nm mod a prime p = 0 then n or m must be divisible by p, so for k = 2, 3, 5 you can just find which of n, m is evenly divisible by k and fill rows or columns in with straight lines of length k. For k = 4, either one of n, m is divisible by 4 (in which case you just use the same strategy) or they are both divisible by 2 in which case one must be (4x + 2) and you just fill each column up with straight lines and then place squares at the end.

If you do have to place every piece you're given, then you know from the start the (nm/k) pieces that you have to fill the bin. This gives you a standard case of the bin-packing problem, which is NP-hard, but there are good heuristic-based algorithms out there. A common one is the greedy heuristic of placing each shape in the first open spot it comes into.

Your problem demands an exact solution, however, which means that getting "close enough" will never be good enough. You could use a backtracking algorithm, but a better approach might be to do a bidirectional search on the state space of valid positions for your grid. Define a position as the goal position, and then make moves backwards from it that involve taking pieces out of random (not really - you should find good heuristics) positions. Then define another position as the start position and make moves forwards that involving inserting pieces. Stop when the two trees intersect and follow that path.

A problem you'll have to deal with is that sometimes it won't be possible to fill up the grid with the pieces you're given. For instance, if you had a m = 2, n = 2, k = 4, you'd only get one piece, and if it was any piece other than a square you wouldn't be able to fill up the state space.

Answer 2

This problem is certainly NP hard (it is knapsack-like), which means that the only way to solve it in general is an algorithm that checks some fraction of all feasible block placements. This will require something like a branch and bound search that assembles pieces the same way you work on a jigsaw puzzle, except there are arbitrarily many copies of each puzzle piece. Whenever you reach a point where no piece fits without introducing a hole, backtrack. In pseudocode:

place one piece to make the initial blob B containing no holes

procedure branch_and_bound
loop
  for each shape S
    for each position P that S can be added 
            to B without creating an unfillable hole
       place S in P to enlarge B
       if puzzle is complete throw DONE!
       call branch_and_bound

It sounds like you are focused on how to find positions P. One simple way to approach this is to consider each empty grid square E that touches B and try placing each square that composes S in E, throwing away all cases that cause an overlap with B. Avoiding unfillable holes can be done simply by requiring that the space not filled by B remain contiguous: don't let an "island" of unfilled space ever develop. It's easy to detect an island by picking any empty square, doing a DFS or BFS to touch all possible unfilled space, then checking for untouched unfilled squares left over.

You can use heuristics to guide the order in which shapes are selected and pieces placed.

In fact this algorithm will quickly become useless unless the heuristics are excellent or the blocks are trivially shaped (or both). This is the nature of NP hard problems. Even if the heuristics are often excellent, there are bound to be problems where they fail miserably. This also is the nature of NP hard problems.

A technique used in many puzzle solvers is to reduce complexity by considering only a limited solution set. An example here is if m = Ap and n = Bp, for some A integers A, B, p, then it is obviously sufficient to find a solution for a p x p square. This can be tiled to get the bigger solution. You can imagine a gajillion similar ideas.