4

I'm writing a program that needs to quickly check whether a contiguous region of space is fillable by tetrominoes (any type, any orientation). My first attempt was to simply check if the number of squares was divisible by 4. However, situations like this can still come up:

Impossible space 1. Impossible space 2.

As you can see, even though these regions have 8 squares each, they are impossible to tile with tetrominoes.

I've been thinking for a bit and I'm not sure how to proceed. It seems to me that the "hub" squares, or squares that lead to more than two "tunnels", are the key to this. It's easy in the above examples, since you can quickly count the spaces in each such tunnel — 3, 1, and 3 in the first example, and 3, 1, 1, and 2 in the second — and determine that it's impossible to proceed due to the fact that each tunnel needs to connect to the hub square to fit a tetromino, which can't happen for all of them. However, you can have more complicated examples like this:

Impossible space 3.

...where a simple counting technique just doesn't work. (At least, as far as I can tell.) And that's to say nothing of more open spaces with a very small number of hub squares. Plus, I don't have any proof that hub squares are the only trick here. For all I know, there may be tons of other impossible cases.

Is some sort of search algorithm (A*?) the best option for solving this? I'm very concerned about performance with hundreds, or even thousands, of squares. The algorithm needs to be very efficient, since it'll be used for real-time tiling (more or less), and in a browser at that.

Archagon
  • 2,470
  • 2
  • 25
  • 38
  • 1
    This seems like a NP-complete problem. What does that tell us? If you need always a correct answer (both sides: never say no if there is a solution; never say yes, if there is no solution): you will experience instances, which will be infeasible for your algorithm! Even the A*-algorithm with a very good metric won't help you in that case (but may give you good results in general). Maybe a little bit of information about your use-case can help us. – sascha Nov 19 '13 at 23:33
  • Do you get any number of copies of each tetromino, or just one copy of each? – templatetypedef Nov 20 '13 at 01:31
  • sascha: My use case is that I'm trying to fill a square with random tetrominos. The space in this square is contiguous, so the top connects with the bottom and the right connects with the left. Randomness is important: I don't want any patterns to emerge because of the techniques I'm using. My algorithm right now is very simple and inefficient: place a random tetromino with a random position and rotation in the next empty square (left to right, bottom to top). If it doesn't fit, try another; if it fits, ensure that the remaining space is still able to be filled. (Continued below...) – Archagon Nov 20 '13 at 01:49
  • Since I don't have a 100% functional "is the remaining space fillable" check, I also have backtracking support, where I remove the previous tetromino and try with a different one. All my problems happen in the last four or so vertical lines, where the jagged bottom (start) has to meet up with the growing top. Since my squares are 8x8 up to, I dunno, 64x64, there will only be 256 such empty spaces at most. The problem may be NP-complete, but most of the time, I can finish an 80% pattern by hand, so I'm sure there must be an algorithm for it! – Archagon Nov 20 '13 at 01:54
  • templatetypedef: any number of copies. – Archagon Nov 20 '13 at 01:55
  • Oh yeah, and the reason I need an efficient "is the remaining space fillable" check is because the kinds of problems that happen in those last 4 vertical lines are often caused by tiles placed at the start of the 4 lines, but only appear when trying to fill the last few tiles. This means that my dumb algorithm has to backtrack a massive amount, and even if/when it reaches the problem tetromino, there's no guarantee that the same thing won't happen again for the next few tetromino/position/rotation combos it tries! – Archagon Nov 20 '13 at 01:58
  • When you say you're "trying to fill a square", do you mean that the shape to be filled is always a completely empty square (i.e. an n by n white box), instead of some complicated shape like in your examples so far? If so, then I have a nice strategy :) – j_random_hacker Nov 20 '13 at 06:21
  • Right, it's always an empty n x n square. The shapes in my example emerge when the ends have to join. – Archagon Nov 20 '13 at 06:30
  • I see, thanks. Actually I've just realised that my approach will work either way :) – j_random_hacker Nov 20 '13 at 06:34
  • What is your approach? Please share! :) – Archagon Nov 20 '13 at 06:37
  • The basic idea is to make a perfect matching to find a domino tiling, and then to make another perfect matching *on that* to make a tetromino tiling. This will often work well, but what I'm realising is that I'm not certain it (specifically the second step) will work 100% of the time. I'm trying to see if I can sketch a proof that it will, or come up with a counterexample. – j_random_hacker Nov 20 '13 at 06:51

1 Answers1

1

Perfect matching on a perfect matching

[EDIT 28/10/2014: As noticed by pix, this approach never tries to use T-tetrominoes, so it is even more likely to give an incorrect "No" answer than I thought...]

This will not guarantee a solution on an arbitrary shape, but it will work quickly and well most of the time.

Imagine a graph in which there is a vertex for each white square, and an edge between two vertices if and only if their corresponding white squares are adjacent. (Each vertex can therefore touch at most 4 edges.) A perfect matching in this graph is a subset of edges such that every vertex touches exactly one edge in the subset. In other words, it is a way of pairing up adjacent vertices -- or in yet other words, a domino tiling of the white squares. Later I'll explain how to find a nicely random-looking perfect matching; for now, let's just assume that it can be done.

Then, starting from this domino tiling, we can just repeat the matching process, gluing dominos together into tetrominos! The only differences the second time around are that instead of having a vertex per white square, we have a vertex per domino; and because we must add an edge whenever two dominos are adjacent, a vertex can now have as many as 6 edges.

The first step (domino tiling) step cannot fail: if a domino tiling for the given shape exists, then one will be found. However, it is possible for the second step (gluing dominos together into tetrominos) to fail, because it has to work with the already-decided domino tiling, and this may limit its options. Here is an example showing how different domino tilings of the same shape can enable or spoil the tetromino tiling:

AABCDD   -->   XXXYYY   Success :)
  BC             XY

AABBDD   -->   Failure.
  CC

Solving the maximum matching problems

In order to generate a random pattern of dominos, the edges in the graph can be given random weights, and the maximum weighted matching problem can be solved. The weights should be in the range [1, V/(V-2)), to guarantee that it is never possible to achieve a higher score by leaving some vertices unpaired. The graph is in fact bipartite as it contains no odd-length cycles, meaning that the faster O(V^2*E) algorithm for the maximum weighted bipartite matching problem can be used for this step. (This is not true for the second matching problem: one domino can touch two other dominos that touch each other.)

If the second step fails to find a complete set of tetrominos, then either no solution is possible*, or a solution is possible using a different set of dominos. You can try randomly reweighting the graph used to find the domino tiling, and then rerunning the first step. Alternatively, instead of completely reweighting it from scratch, you could just increase the weights for the problematic dominos, and try again.

* For a plain square with even side lengths, we know that a solution is always possible: just fill it with 2x2 square tetrominos.

j_random_hacker
  • 50,331
  • 10
  • 105
  • 169
  • 1
    If you make your tetronimoes by gluing together dominoes, doesn't that mean you will ignore the T shaped tetronimo? – pix Oct 24 '14 at 12:07