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.

Mckamey

Does k vary from piece to piece or is it constant? – Warship

I'm sorry I don't see any answer good enough to be awarded the bounty I set up. I'll just let the reputation point go. Thanks for all that answered and voted. – Mckamey

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.

Peckham

thanks for your input. First, please assure mxn mod k = 0 for each run. I added this into original question, as well as the point of being random. As for backtracking, that's actually what my code misses at the current stage. However, I didn't find a good way implemented it yet. Wondering if there's a smart way to prevent singletons (holes) appearing. Thanks! – Mckamey

OK, so what would better describe your problem - do you have a set of nm/k shapes and an order in which you have to insert them and you want to determine what the optimal placement would be, or are you given one shape at a time and have to figure out what the best place to put that shape is, with no idea what will come next? That is, is the solution state deterministic? – Peckham

Also, as I said, there may not always be a way in either case to avoid holes appearing. So you will have to accept that. – Peckham

This appears to be an instance of a polyform tiling problem. en.wikipedia.org/wiki/Polyomino – Phox

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.

Drinker

Answer 3

As for the holes problem there should be an easy way of solving this... 3! (well for k<=9 that is ;))

Let me explain, every block is not only adjacent to another block or two, but it is also adjacent to EMPTY SPOTS regarding the shape of k that is is what you should care about, every count of such empty spots is ALWAYS k*2+2 so k=1 -> 4, k=2 -> 6 .... k=9 -> 20 for every item of k.length you know it's position right? In your matrix you can now step one to each side and check if it's an empty space and if so.. NOTE that (blank) position temporarily, if you outlined your k in such a way you will have a distinct number of empty spaces that is less or equal the above mentioned calculation.

If equal, you cannot have any hole in k and you can proceed, if less, then check how much less that is, if you miss ONE you made an L shape, if you miss TWO you either haven an U shape or T shape (special case k=9 an S), your good to go

if you miss THREE or more you'll need to further investigate! Now check every of those blank positions you temporarily noted for it's adjacent blocks, if the number is lesser or equal 3 for EVERY such blanks, you do not have a hole and can go on, as soon as MORE than ONE blank has 3 adjacent blocks however, you will have a hole in k.

It's hard to get that right for k=10, but up to nine these simple rules can prevent holes in your k-object.

Sorry, I'm not familiar with perl, otherwise I'd given you code not just a hint ;)

So NOT having any holes in any of your k-objects you should be assured that you can solve any m*n%k=0 grids. There is only ONE thing you should always keep in mind, and that is the classical domino-chess question* so always fill your grid starting at one corner/edge and don't leave any blanks behind until you insert the last piece to the grid, to avoid those situations.

*domino-chess question is the question if you could lay out 31 dominos (2x1 blocks) in a chessfield (8x8) if 2 chess pieces are on the board. (Answer: you can if one is on white and the other on black.. otherwise you can't)

Salmonberry