Protected: Solving tangram puzzles

A description of the tangram puzzle is available at wikipedia.
My sister Katy and I had the opportunity to play tangrams while traveling on the trains in Europe last summer. It was then that I had the idea of trying to solve the puzzle computationally.

There are several different heuristics for solving a tangram puzzle. But first we need to make some definitions:

1. Silhouette means the given shape that we need to form.

2. Puzzle piece means one of the elements from the set of 7 shapes to be used in forming the silhouette (on the wikipedia page these pieces are called tans.)

The following are possible methods/algorithms to solve a tangram puzzle.

1. Use a heuristic to cut the given silhouette into a number of shapes, then check if the resulting set of shapes matches the set of puzzle pieces.

The following images demonstrate the above algorithm, using a set of two puzzle pieces.

Cut Algorithm

2. A Heuristic Solution to the Tangram Puzzle, E. S. Deutsch & K. C. Hayes Jr., Machine Intelligence v7, p205-240, 1972 (TODO: Lookup algorithm and give short description)

3. Use a combinatorial approach, that is try each shape in all possible positions and quit when one of the configurations is a solution. In more detail the following is the algorithm. Note that the algorithm can solve more general problems than just tangram puzzles.

function position_puzzle_pieces(P = {set of puzzle pieces}, s = silhouette)
if P == ∅: return true
for p ∈ P:
  g=position_puzzle_piece(p, s) #create a generator to position the puzzle piece p, inside the shape s.
    P = Pp #remove puzzle piece p from the set of puzzle pieces.
   while g.next_starting_position() == true: #continue loop, until p is in the last possible position inside of s.
          s1 = s\p #subtract puzzle piece p from shape s and set s1 equal to the shape resulting from the subtraction.
           if position_puzzle_pieces(P, s1) == true: return true
end for
return false

I’ve coded up method (3) for solving tangram puzzles. The algorithm name for position_puzzle_pieces is Poly-Solve. There are a number of low level issues to deal with when implementing Poly-Solve, but for this blog we’re interested in just the high level details.

My next post will go into some of the applications for method (3), maybe more of the high level details in implementing method (3) and running time/space analysis, and other related problems to tangram puzzles.l

Advertisements

7 thoughts on “Protected: Solving tangram puzzles

  1. Pingback: BryanBell » Blog Archive » Tangram Applications

  2. Pingback: More Computational Geometry :) « A blog on math

  3. Pingback: Solving Tangrams Using the Java Topology Suite (jts) « A blog on math

  4. Pingback: A Heuristic Solution to the Tangram Puzzle « A blog on math

  5. Pingback: What is a tangram | Tangram Online

  6. Pingback: Solving Tangrams Using JTS « Math and More

  7. Dear Author,

    I am a beginner of programming and I am really interested in your method (3). Could you share your program of method (3) with me for purely learning purpose ?

    Best Regards

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