In this post I describe a modification of the algorithm previously outlined for solving tangram puzzles.

For ease of writing I’ll call the new algorithm **Vert-Solve**. The **Vert-Solve** algorithm uses the same combinatorial approach as the previously described algorithm **position_puzzle_pieces**. The most significant difference between the two algorithms is **Vert-Solve** uses vertices as a basic building block, whereas **position_puzzle_pieces** as I described the algorithm used polygons.

Before outlining **Vert-Solve** I need to show how polygons are represented (this information will also be used in future posts on algorithm implementations).

A polygon, **p**, can be completely described by a list of of vertices together with their respective line segments.

The below polygon, **p**, is represented by:

[**v _{1}**,

**v**,

_{2}**v**,

_{3}**v**], where

_{4}**v**= [(0, 0), [[(0, 0), (0, 1)], [(0, 0), (1, 0)]]]

_{1}**v**= [(0, 1), [[(0, 1), (0, 0)], [(0, 1), (1, 1)]]]

_{2}**v**= [(1, 1), [[(1, 1), (0, 1)], [(1, 1), (1, 0)]]]

_{3}**v**= [(1, 0), [[(1, 0), (1, 1)], [(1, 0), (0, 0)]]].

_{3}I note that the current **position_puzzle_pieces** algorithm implementation uses the same basic data structure to represent a polygon.

To represent a set of polygons simply use a list of polygon objects e.g. [**p _{1}**,

**p**, …,

_{2}**p**]. In general this is the representation used for a set of polygon objects but for the purposes of

_{n}**Vert-Solve**this representation is converted to a new representation based entirely on vertices. The following is an example.

Right Triangle:

**p _{1}** = [

**v**,

_{1}**v**,

_{2}**v**]

_{3}**v**= [(0, 0), [[(0, 0), (0, 1)], [(0, 0), (1, 0)]]]

_{1}**v**= [(0, 1), [[(0, 1), (0, 0)], [(0, 1), (1, 0)]]]

_{2}**v**= [(1, 0), [[(1, 0), (0, 0)], [(1, 0), (0, 1)]]].

_{3}Square:

**p _{2}** = [

**v**,

_{4}**v**,

_{5}**v**,

_{6}**v**]

_{7}**v**= [(0, 0), [[(0, 0), (0, 1)], [(0, 0), (1, 0)]]]

_{4}**v**= [(0, 1), [[(0, 1), (0, 0)], [(0, 1), (1, 1)]]]

_{5}**v**= [(1, 1), [[(1, 1), (0, 1)], [(1, 1), (1, 0)]]]

_{6}**v**= [(1, 0), [[(1, 0), (1, 1)], [(1, 0), (0, 0)]]].

_{7}The usual representation for the set of objects, **S** = {**p _{1}**,

**p**}, is [

_{2}**p**,

_{1}**p**]. But instead we’ll represent

_{2}**S**by a simple list of vertices where each vertex has a pointer (actually in python lingo a

*reference*) to the object it’s part of e.g.

**S** = [(**&p _{1}**,

**v**), (

_{1}**&p**,

_{1}**v**), (

_{2}**&p**,

_{1}**v**), (

_{3}**&p**,

_{2}**v**), (

_{4}**&p**,

_{2}**v**), (

_{5}**&p**,

_{2}**v**), (

_{6}**&p**,

_{2}**v**)]. I use

_{7}**&p**for a reference to

**p**.

At this point it doesn’t seem like this new representation has any advantages, in fact it seems worse then the previous representation for **S**. But it does have one important property, it is vertex centric versus polygon centric that is the basic object in the representation for **S** is a vertex instead of a polygon. This is a important distinction because we can build our algorithm and heuristics around vertices instead of polygons.

Here is the **Vert-Solve** algorithm:

**function** vert_solve(**P** = {set of puzzle pieces}, **s** = silhouette)

**if** P == ∅: return **true**

**for (&p, v), w ∈ P***x***s**:

#By *x* I mean the Cartesian product, so **(&p, v), w** varies over all possible vertex pairs from **P** and **s**.

**g**=position_vertex_pair(**(&p, v)**, **w**) #create a generator to position the vertex, **v**, so that it coincides with **w**, that is translate **p** so that **v** and **w** have the same coordinates. Note that there are several possible orientations of **v**‘s line segments (that’s why a generator is used).

**P’** = **P** – **p** #remove puzzle piece **p** from the set of puzzle pieces.

**while g**.next_orientation() == **true:** #continue loop, until all valid (by *valid* I mean **p** is a subset of **s**) possible orientations of **v**‘s lines segments are exhausted.

**s’** = **s\p** #subtract puzzle piece **p** from shape **s** and set **s’** equal to the shape resulting from the subtraction.

**if** vert_solve(**P’**, **s’**) == **true: return true**

**end for**

**return** **false**

The comments in the algorithm show how it works. My next post will examine several heuristics to improve the speed of **Vert-Solve** and **position_puzzle_pieces**.

Have you implemented a full algorithm for solving tangram puzzles ? did it work ?

I have been working with this subjetc for a month and got with an intersting backtraking solution using a polygon clipping algorithm (maybe the same way you do vert_solve) and a position method. I built an animated interface using OpenGL and would like to use compile it in Linux. Dow you know how to compile OpenGl in linux ? Do you have more deails about your implementation of this puzzle?

Antonio.