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 _{1}** =

**s\p**#subtract puzzle piece

**p**from shape

**s**and set

**s**equal to the shape resulting from the subtraction.

_{1}**if**position_puzzle_pieces(

**P**,

**s**) ==

_{1}**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

Pingback: BryanBell » Blog Archive » Tangram Applications

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

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

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

Pingback: What is a tangram | Tangram Online

Pingback: Solving Tangrams Using JTS « Math and More

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