Protected: A Modified Algorithm for Solving Tangram Puzzles

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:
[v1, v2, v3, v4], where
v1 = [(0, 0), [[(0, 0), (0, 1)], [(0, 0), (1, 0)]]]
v2 = [(0, 1), [[(0, 1), (0, 0)], [(0, 1), (1, 1)]]]
v3 = [(1, 1), [[(1, 1), (0, 1)], [(1, 1), (1, 0)]]]
v3 = [(1, 0), [[(1, 0), (1, 1)], [(1, 0), (0, 0)]]].

p:
Square

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. [p1, p2, …, pn]. In general this is the representation used for a set of polygon objects but for the purposes of Vert-Solve this representation is converted to a new representation based entirely on vertices. The following is an example.

Right Triangle:
p1 = [v1, v2, v3]
v1 = [(0, 0), [[(0, 0), (0, 1)], [(0, 0), (1, 0)]]]
v2 = [(0, 1), [[(0, 1), (0, 0)], [(0, 1), (1, 0)]]]
v3 = [(1, 0), [[(1, 0), (0, 0)], [(1, 0), (0, 1)]]].

Square:
p2 = [v4, v5, v6, v7]
v4 = [(0, 0), [[(0, 0), (0, 1)], [(0, 0), (1, 0)]]]
v5 = [(0, 1), [[(0, 1), (0, 0)], [(0, 1), (1, 1)]]]
v6 = [(1, 1), [[(1, 1), (0, 1)], [(1, 1), (1, 0)]]]
v7 = [(1, 0), [[(1, 0), (1, 1)], [(1, 0), (0, 0)]]].

The usual representation for the set of objects, S = {p1, p2}, is [p1, p2]. But instead we’ll represent 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 = [(&p1, v1), (&p1, v2), (&p1, v3), (&p2, v4), (&p2, v5), (&p2, v6), (&p2, v7)]. I use &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 ∈ Pxs:
#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’ = Pp #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.

Advertisements

One thought on “Protected: A Modified Algorithm for Solving Tangram Puzzles

  1. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s