I have a set of puzzle pieces (triangles and squares) of e.g. the form
{[1, 2, 3, 4], [2, 4, 5], [1 , 3, 6]}
Now, I want to check if these pieces can be put together on a grid.
A set of puzzles that would not have a valid mapping would be
{[1, 2, 3, 4], [2, 4, 5], [1 , 5, 6]}
My first ansatz is to put all numbers in the set of puzzle pieces (in the above examples it would be 1, 2, 3, 4, 5, 6) as nodes in a graph and connect them according to the puzzle pieces (if a connection occurs several times, consider it only ones). Then I check if the resulting graph is planar (this is cheap, it scales with the number of edges to the power of 2).
However, the planarity is only necessary for a valid mapping but not sufficient, since it does not take into account that the puzzle pieces have to form a square or a triangle (nothing stretched or similar).
So I thought about a list of forbidden edges, which is appended by looping over the set of puzzles, however, I am stuck. Does someone have a clever idea to answer the question: Does a given set of puzzles form a valid layout on a grid (at best in polynomial time).
The length of the set is arbitrary
Edit: For a puzzle piece such as [1, 2, 3, 4], the four numbers must form a square, and it does not matter in which order these numbers appear on the grid. The same applies to triangles. Therefore, swapping e.g. 2 and 4 in the figure above would still be a valid assignment
from Check if a set of puzzle pieces is forms a valid puzzle
No comments:
Post a Comment