[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

Problem Description

Tangram is a classic Chinese puzzle consisting of 7 pieces cut from a square - 5 triangles, a square and a parallelogram.     The object is to reassemble them to form the original square, or any of 100's of other shapes given only the outline of the final figure. 

Tangram1 contained the basic graphic processing to move and rotate figures.   Here's the "final" version which actually lets you solve Tangram puzzles.    

Background & Techniques

This is a Delphi version of an excellent freeware Tangram program written by Dr. Mark Overmars and  available from  http://www.cs.ruu.nl/~markov/kids/ .    If you just want to play the game, I recommend that you download from the that site.   This version is not as complete ( Dr. Overmars version  includes dozens of graded outlines to solve, a Tangram Editor,  and even a Help file!) .   But his program is available in executable form only, and I was curious about the code required.   As usual, it has been a fun learning experience. 

Tangram1 contained the basic graphic processing code to draw, drag and rotate the pieces.  Tangram2  adds:

Tangram1 assumed predefined shapes.  I found later that Overmars' version uses generalized polygons, some of which happen to be the classic triangle, square  and parallelogram shapes.    I decided to adopt this data structure to permit use of his set of figure definitions for testing.  The Loadpieces and LoadFigSet  procedures read files in Overmars' format.   They are text files that can be browsed and edited manually.  Figure files (.tan extension) contain the name of the associated pieces (.pcs) file.  The main problems were in figuring out how to scale the information for proper display - largely a matter of trial and error.    Also Overmars' files  assume counterclockwise rotation and may contain large and/or negative numbers so it took a bit of manipulation to interpret rotation values properly.   A new TFigSet class holds the figures file information as a Figures array in tTangram.   The ShowFigures method uses this information to construct the Solutions array of pieces when a new figure is selected.  The Solutions pieces are marked as unmovable and colored white. 

The problem of drawing figure outlines still hasn't been entirely solved (by me).   I foolishly thought that the Convex Hull procedure from Fences and Traveling Salesmen would do, but of course, not all figures are convex.  My second attempt was to identify shared edges and delete them so that the figure could be drawn by simply drawing the remaining edges.   This approach required identifying overlapping co-linear line segments.  (I finally had to solve this problem anyway for piece placement, but that was after looking at the figure drawing problem. )    I finally resorted to drawing the figure by drawing its figures in white with a white pen.  They look OK, but are not outlined as are Overmars'.   There are hull drawing algorithms which work for actual hulls,  concave as well as convex, but we'll leave that as an enhancement.   

The other major effort is in the PieceInSolution function.   It is called when the user clicks to drop a piece in the figure section of the screen.  In order to be dropped the piece must be entirely contained in the figure outline and not overlap any previously placed piece.  Easy,  right?   Wrong!  I hadn't appreciated how complex geometrical shape processing can be, at least to a novice like me.   The PointInPoly function written last time to detect mouse clicks helps identify where the vertices lie, but that's only part of the story.  A piece may have one or two vertices touching the edges of another piece with no violation,  but that gives no information about whether the area of the piece is outside or inside  of the other piece.   I finally decided that if pieces share 2 or more sides, they  must overlap.   This restricts pieces to being convex polygons, i.e. no indentations.    

The solution identification problem was solved simply by counting how many pieces had been placed successfully.  When the placed count matches the number of solution pieces, we must be done.   

Finally, flipping the pieces also turned out to be not bad.  Flipping  about either the horizontal or vertical axis (through the piece center)  can be accomplished by  translating the point so it's centered on that axis, reversing the sign of the point and translating back to the original axis location.   I.e., to translate point (Px, Py) about the Y axis for a piece centered at (Cx, Cy),   move the point to (Px, Py-Cy), reverse its Y coordinate sign to (Px,Cy-Py) and move it back to (Px, Cy-Py+Cy) or  (Px,2Cy-Py).   The TPiece method, Flip, does just this for all points in a piece and seems to work fine.  Note that the parallelogram is the only standard piece that may require flipping. 

Addendum November 11, 2004:  Viewer Max is busy converting this Delphi version of Tangram to Visual Basic and recently spotted a bug:  Figures that have a notch exactly the size of a piece can fool the program.  So    accepts  as a solution.  Or at least it did until today's update.  I fixed it by ensuring that the center of each piece lies within the solution space before it can be dropped.  

Addendum August 21, 2005:  I fixed a minor problem with pieces placement problem today.  Users could  drop a piece with one edge outside a concave portion of the solution space so long as all vertices were inside the space and all other placement constraints were met.     

Addendum August, 19, 2009:  Version 4 posted today at least partially addresses a problem that had been recognized several years ago but has no easy solution.  The scale used to define figures does results in  changing their size slightly as they are rotated.  Since the same scale is used to define the puzzles and the pieces, the distortion is normally not noticeable to users.  However in some of the more complex puzzles that happen to have pieces in their larger configuration, it's possible for smaller versions to fit within the puzzle boundaries and have some white space left over.  This version checks that the sum of areas of the pieces as placed by the user matches the area of the pieces as rotated in the original puzzle.  If the user sets all pieces with an area less than the expected area, a "Gremlin" message is given and she is asked to try again.  The program lists all of the provided puzzles with the condition, thanks to a sharp eyed viewer from Portugal.      Finding the "Gremlin" solutions can be an interesting exercise in its own right.    BTW, Overmars free version is no longer available.    

Running/Exploring the Program 

Suggestions for Further Explorations

  [Feedback]   [Newsletters (subscribe/view)] [About me]

Copyright © 2000-2018, Gary Darby    All rights reserved.