I have this problem and searched around and I find this interesting Tetris forum, so I registered and guess big shots here can help. 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. So if k=4, m=10, and n=20, that's basically fill up this 10x20 grid with Tetris blocks. No holes can be left anywhere in the grid. Next run, it could be k=3, m=6 and n=10. mxn % k = 0 for all runs. K is in the range of 2 to 5. But 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. I tried in Perl, can solve some cases of k=3 and failed some runs because of singletons (holes). Yes, randomly pick one shape from the pre-defined shape pool, such as ITOLJSZ for k=4. Can not do straight lines all time. The pool of shape for k=2 has two horizontal ++ or vertical ++; for k=4, it's Tetris; for k=3, there are 4 shapes I think (difficult to write here). You only use shape from ONE pool for one case (i.e., k is set to 2, 3, 4, or 5 for one case). Actually, I should have added this to my original post. I saw posts here addressing pretty much similar question. http://tetrisconcept.net/forum/showthread.html?t=177
I have no talent for programming but had some general observations. Your rules state you can freely rotate, meaning k=2 is pointlessly trivial. There are only 2 shapes for k=3 which should make it easy enough though you're still at the mercy of RNG (need an even number of L pieces). k=4 is np-hard, even with infinite preview (at least when piece generation is truly random), but at least interesting. k=5 is just silly, holes are unavoidable.
I'm pretty sure there are sets of pools where the problem is not solvable. My general approach would be to build a recursive algorithm that just keeps putting them in a stupid-but-efficient method until it runs into an unsolvable problem, and then backs out to the last decision and makes a different choice, and keeps working that way. This is (probably) very computationally expensive. But it might not be. There aren't that many choices, truthfully. It's hard for me to estimate whether this algorithm would take a second, a minute, or a year. If it takes too long, you can simplify the problem by using the same algorithm on smaller sections. I.e. using the above algorithm to solve 4 5x10 grids, instead of one 10x20. There's probably a really elegant solution out there, but I can't think of it quickly.
Actually, I should have added this to my original post. I saw posts here addressing pretty much similar question. http://tetrisconcept.net/forum/showthread.html?t=177
Why k=5, holes are unavoidable? For what situation? Many case with k=5 can be filled without holes, such as m=5, n=5, k=5, you can just throw in five straight bars into the grid and fill it seamlessly.
Are you a familiar with a puzzle called Pentomino? (It may or may not be the game on which Tetris was based.) </s>
If I understand you, I think this is pretty much a solved problem. Try googling "Algorithm X" or "Dancing Links".
I may have misread your original post and assumed pieces were generated randomly. If there are no restrictions on piece choice then it's just not a very interesting problem - you would only use a few different pieces no matter how big k was. You also need to properly define the "Can not do straight lines all time" rule. Your extreme 5xI solution clearly fails on this point but for bigger grids is a 95% I piece solution acceptable? 90%? 80%?
