5
$\begingroup$

Inspired by Mosaic with tetris blocks I was wondering if there were any generic algorithms to solve or show there was a solution to these types of problems (i.e. placing polyominos on a 2D board).

Breaking it down to the simplistic form of dominos, there's the classic puzzle of placing them a checkerboard with either two white or black squares missing. This is known to be impossible and left as an exercise for the reader =). But what if we're given a less uniform board. Is there any known algorithms other than brute-force to show there is a solution or to even solve the puzzle? We know there have to be an even number of square and an equal number of white and black squares, but that doesn't mean there is a solution.

Moving up in complexity, there's another classic problem of filling an $n \times n$ board with L-triominos except for one marked square. Recursive solutions exist here, but I've never seen anything for non-uniform board or allowing non-L blocks.

Finally we hit the Mosaic puzzle. What if we're given a set of tetris pieces and an irregular board? Can we easily determine if there's a solution? Is it easier if we aren't constrained by the number of each piece we can use?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

The problem is a type of "Packing Problem". Regarding polyominoes we are interested in tiling specific regions.

It is known that the problem of answering whether a specific region can be filled with tiles is undecidable. And that finding a solution, in general, is NP-Complete. So we can never do much better than trying all possible configurations - i.e. pick something and exhaustively show that it doesn't work, backtrack and try again.

As to the "simpler" problems like L-trominoes, it is essentially the same problem.

So, to answer directly: there is no easy way to determine whether there is a solution. Just as there is no easy solution for the travelling salesman problem, the tiling problem, or the boolean satisfiability problem (SAT) (on a personal note, I immediately think of this problem, and could fairly easily cast the polyomino problem as a SAT problem).

Related:
More Papers
Be Bruijn's Theorem

Improve this answer
$\endgroup$
4
  • $\begingroup$ I hadn't thought of trying to prove that these problems were NP-complete. That makes total sense and I can see how they could be expressed as SAT problems. Thanks! $\endgroup$
    – Ric
    Commented Nov 19, 2014 at 20:39
  • $\begingroup$ @Ric Always a pleasure :D $\endgroup$
    – d'alar'cop
    Commented Nov 19, 2014 at 20:40
  • $\begingroup$ In what sense is the question of tiling of a specific region undecidable? It is a finite problem, you can do an exhaustive search. It might be hard, but why undecidable? $\endgroup$
    – Florian F
    Commented Dec 4, 2022 at 15:20
  • $\begingroup$ IIRC, that's if the region/set of possible regions in question is infinite, such as the full/half/quarter plane, the complement of any given finite region, or some scaled copy of a particular non-tiling polyomino (without specifying the scale) $\endgroup$
    – Zomulgustar
    Commented Jan 26, 2023 at 1:05
1
$\begingroup$

For the case of dominos, you can see it as a maximum cardinality bipartite matching problem.

The domino covering problem can be seen as the problem of pairing black squares with neighboring white squares in a way to maximize the number of pairs. There are fast algorithm to solve that. If you manage to pair all squares then a solution exists.

This doesn't extend to larger pieces, though.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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