8
\$\begingroup\$

I'm thinking of making a puzzle game where the objective is to fill a grid with shaped puzzle pieces (for example, the classic Tetris shapes).

How can I go about generating a set of pieces that can be guaranteed to be used to fill the grid, leaving no gaps? How could I adapt this algorithm to scale the difficulty of the resulting puzzle?

\$\endgroup\$
  • 2
    \$\begingroup\$ See also: en.wikipedia.org/wiki/Polyomino \$\endgroup\$ – user1430 Nov 30 '14 at 21:18
  • 1
    \$\begingroup\$ Do you allow single or small two squarenparts? \$\endgroup\$ – Steven Dec 1 '14 at 0:25
  • \$\begingroup\$ @steven "monominos" and "dominos". All the classic Tetris pieces are tetrominos. There are 12 pentominos, and 35 hexominos... \$\endgroup\$ – david van brink Dec 1 '14 at 1:23
8
\$\begingroup\$

This is a known hard problem, determining what rectangles can be tiled with certain pieces.

However, if you're building puzzles and can control the pieces, it's the opposite, constructive problem, and easier...

Build a solution constructively. Take a few pieces you like, and fill the puzzle however you want. Then throw in enough single-squares to fill it out, and you have guaranteed that there is at least one solution. Or rather, include some small pieces in your allowed set of pieces.

As for solving/laying out the pieces, a typical brute force approach is to fill it from left to right, then top to bottom. Find the first open cell (numbered L-R, T-B) and try to put in your allowed pieces in their allowed orientations (8 orientations for an asymmetric piece if you allow flipping). Perhaps check first large allowed pieces, and resort to smaller ones if necessary. When you reach a state you don't like (dead end, too many small pieces, or what not) then backtrack. If a given grid/piece set doesn't meet your criteria, that is, it backtracked all the way without finishing, try a different rectangle and piece set.

One way to make a puzzle "easier" could be to trade bigger pieces for more smaller pieces like monominoes and dominoes, since this will leave more ways to fill in the last holes. Or, equivalently, build a solution that favors those smaller pieces.

Some noted polyominologists include:

==> http://ee.usc.edu/faculty_staff/faculty_directory/golomb.htm Golomb originally coined the term "Polyomino"

==> http://www.eklhad.net/polyomino/ Dahlke has solved quite a few rectangles filled with identical pieces (a particularly rare tiling form)

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

This article (page 11-13, disclaimer: I'm one of the authors) describes an algorithm that uses dynamic programming to uniformly generate perfectly tiled rectangular regions of width w and height h, in time which is linear in h after a preprocessing that takes about 2(w.D) time/space (D being the longest dimension of an individual shape, eg 4 in the case of Tetris pieces).

The idea is similar to the one described by David above, and focuses on the upper strip, placing pieces that do not create holes. The key thing here is that is to start by precomputing the allowed alternatives for each state of the upper-strip, so that you no longer pay for the combinatorial explosion when you generate the regions.

The algorithm works for any set of (convex) shapes.

Also, an interesting aspect of a uniform random generation is that it ensures maximal diversity between consecutive generations (but you can also constrain the generation in any way you want). Here are some typical outputs:

Some randomly generated tetrises of width 6

Feel free to ask if you're having trouble with the implementation (I might even have a Python quick and dirty implementation lying around somewhere...)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ the python implementation you mentioned would be very helpful \$\endgroup\$ – user2682863 Jan 30 '18 at 20:57
1
\$\begingroup\$

Here's a technique we've used in the past to cheat a bit on more confined hardware. It's not as pure as the more complex solutions, but has the distinct advantage of being much easier to implement and works every time.

Rather than focusing on the entire puzzle, break it into smaller, uniform units. Each of these units is composed of a set number of pieces that fit together to form squares or rectangles which are much easier to fill into a puzzle. Choose randomly from the different configurations to fill up the width of the puzzle (samples below, but there are many, many configurations). Below are 4x4s, a 5x4, and even a 10x4 example.

Squares and rectangles

The idea is that you "stripe" the puzzle ... choose the widths randomly based on the available remaining room. Once a "stripe" is finished, start a new stripe.

You release pieces one stripe at a time by randomizing within each "stripe" set. If you want to increase the difficulty, randomly release from two or more stripes at a time.

Using this technique, not only have you guaranteed that the puzzle is solvable, you've also helped "cheat" the order of release to make it easier to stay alive. Of course in practice, players aren't able to perfectly solve each stripe and so chaos ensues.

Keep generating stripes until the player loses. Of course, my example is a stripe 4 blocks high, but you can choose something larger and more complex:

enter image description here

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.