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.

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 = P – p #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.
          s₁ = s\p #subtract puzzle piece p from shape s and set s₁ equal to the shape resulting from the subtraction.
           if position_puzzle_pieces(P, s₁) == 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

About these ads