Quick Heuristic For Tangram Polygon Intersection

For the combinatorial approach to solving Tangram puzzles one frequent operation is to test if a puzzle piece, p, is contained in the silhouette s. Before this test is made the puzzle piece, p, is translated to a vertex, v, of s and one of the edges of p is aligned with an edge, e, coming out of vertex v.

For clarity I’ve included a figure below illustrating this.

puzzle piece and silhouette

In the above figure it’s obvious that the puzzle piece, p, does not fit in the silhouette. One way to see this computationally is to look at the edge, e, and notice that at vertex, v_1, the next edge of the silhouette, s, makes a left turn with respect to the edge e. This means that if the length of e is less than the length of all the edges in p then there is no possible way to fit p in s. That is as long as we have the condition that one of the edges of p is aligned with the edge e of s.

The above statement provides a quick way to skip vertices of the silhouette s when trying to fit the puzzle piece p in the silhouette s. Of course before skipping the vertex the same test needs to be done on the other edge coming out of v. Also we note that the above test only works if the next edge coming out of v_1 makes a left turn with respect to the edge e, otherwise the full test for polygon intersection has to be run. Also if one of the edges of the puzzle piece p has length less than or equal to the length of e then the full test for polygon intersection has to be run.

In summary this is a very specific heuristic that in general isn’t very useful but if you ever find yourself needing it, it can be just what the doctor ordered.

Advertisements

A Heuristic Solution to the Tangram Puzzle

In this post I present a short summary of the paper “A Heuristic Solution to the Tangram Puzzle” by E.S. Deutsch and K. C. Hayes Jr. I’ve uploaded a scanned copy of the paper to scribd here. Uploading the scanned copy probably violates some copyright law so if they or anyone else contacts me I’ll remove the document. Ironically it’s taken me over two-years since my post here to finally read the paper.

In their paper they talk about two possible approaches to solving tangrams. One is the combinatorial approach that I’ve taken and the other is the heuristic method that they describe in their paper. The heuristic method that they use is a little clever, what they do is take the outline of the tangram puzzle and then try to break it out into sub-puzzles. The following figure illustrates where two puzzles have both been separated out into sub-puzzles. In both cases one of the sub-puzzles exactly matches a tangram piece thus allowing the algorithm to solve that sub-puzzle.

Puzzle Illustration

The dashed lines in the figure show where the algorithm is splitting the sub-puzzles out from the original puzzle. First note that the dashed lines are called “extension lines” in the paper. They are generated to allow the extraction of the sub-puzzles. To create the extension lines the algorithm goes along the outline of the puzzle and at convex corners it generates an “extension line” that allows the possible separation of the puzzle into sub-puzzles. The following figure illustrates this. In the paper they outline various ways for eliminating extension lines that are unlikely to be of use.

Extension Lines

Once the above extension lines are created there is a set of heuristics for splitting out sub-puzzles, the heuristics are used in the following order.


1. direct-match rule

The algorithm attempts to locate puzzle pieces fully described by edges, rather than by extension lines or by combinations of edges and extension lines.

2. 2 1/2 – 3 1/2 edge-match rule
The direct-match rule while being very reliable in finding matches cannot be used in most cases this means that a more relaxed rule is needed. The 2 1/2 – 3 1/2 edge-match rule allows the location of puzzle pieces where most of the periphery is described by edges and a small portion is described by extension lines. Specifically the “2 1/2 – 3 1/2 edge-match rules requires that in the case of triangular shapes two complete sides must be defined by edges and the remaining side can be defined by a combination of collinear edges and extension lines. Moreover, the combination must include at least one portion of edge. For four sided puzzle pieces the rule requires that the additional side also be fully described by an edge.” [1]

There are an additional 8 extraction rules that are used but the above two give you their general flavor.

The organization of the extraction rules is to run them recursively and at each step try to apply the most specific one possible first. If the algorithm gets to a step where there are no possible extractions it backtracks and tries another extraction rule. This process is not guaranteed to find a solution and in fact the paper gives an example of a puzzle on page 239 for which no solution is found.

The paper is a niece example of where a little clever thinking and some very specific heuristics can solve tangram puzzles.

References

[1] Deutsch, E. S., and K. C. Hayes Jr. “A Heuristic Solution to the Tangram Puzzle”, Machine Intelligence vol. 7, 1972, p. 205–240.