In my past posts on solving tangram puzzles I’ve given two slightly different algorithms. Neither algorithm as I gave it had any heuristics. I aim to show you a few simple heuristics that should work in non-pathological cases.

The most obvious heuristic for the **Poly-Solve** algorithm is to sort the puzzle pieces by size (or bounding box) before you pass them into position_puzzle_pieces. When I implemented **Poly-Solve** this did substantially speed up the running time. The reason this heuristic works is because large puzzle pieces have fewer possible orientations inside the silhouette which implies that fewer combinations need to be tried. The pathological case for this algorithm is when the largest puzzle piece must be fitted last, which when you think about it, is truly pathological.

For the **Vert-Solve** heuristics I define **P** to be the set of puzzle pieces, where each element is a vertex **v** together with a pointer to its puzzle piece.

1. One heuristic for the **Vert-Solve** algorithm is to try using vertices from the puzzle pieces that are perfect matches. By perfect match for a vertex, **v**, I mean **v** is identical modulo translations, rotations, and reflections to a vertex in the silhouette. With this heuristic the complexity of the new silhouette should be reduced each time **vert_solve** recurses.

2. Another possible heuristic for **Vert-Solve** is to sort the vertices in **P** from largest to smallest, where by size I mean the length of the shortest line segment of the vertex. And also sort the vertices in **s**. Thus when we select the first tuple ((&**p**,**v**), **w**) from **P***x***s**, the **v, w** are the largest possible vertices. The logic behind this heuristic is similar to the above heuristic for **Poly-Solve**.

3. We can combine **1** and **2** to create a new sorting algorithm for **P**, using weights for the importance of **1** and **2**. In fact there are lots of ways to sort **P** but the running time of the sorting algorithm can be important.

That is all for today. It’s easy to think of more heuristics for both algorithms but I need to test them before posting because otherwise I’m only speculating.