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?
Answer
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
No comments:
Post a Comment