Programming Assignment 4 - Tangrams

Advanced Programming II, Spring 2004

Due Date

This assignment is due by 2:00 p.m. on Wednesday, 7 April.

See the assignment turn-in page (last modified on 9 February 2004) for instructions on turning in your assignment.

Background

The tangram puzzle consists of 7 pieces (called tans):

tangram pieces

The objective of the puzzle is to arrange all seven tans to form a shape described only in outline. For example, the simple puzzle

a simple tangram puzzle

has the solution

the puzzle solved

Problem

Write a program that solves tangram puzzles. Your program should read from std-in a sequence of floating-point numbers that are interpreted as the x, y coordinates of vertices on the outline of a puzzle in either clockwise or counter-clockwise order starting from an arbitrary vertex on the outline. The last point read is adjacent to the first point read.

Your program should output the solution to the input puzzle or impossible if the puzzle can't be solved. If the puzzle has a solution, the tans should be output one per line, with each tan being output as a sequence of vertices in either clockwise or counter-clockwise order starting from an arbitrary vertex on the tan. The tan vertices should be given in the coordinate system defined by the input puzzle.

For example, the following input describes the square puzzle given in the Background Section: 

-1 -1 -1 3 3 3 3
-1

The solution to this puzzle would be output as 

-1 -1 -1 3 1 1
-1 3 3 3 1 1
-1 -1 0 0 2 0 1 -1
3 1 1 -1 3 -1
0 0 2 0 1 1
2 0 3 1 2 2 1 1
3 3 2 2 3 1

The input data describes one continuous outline; the shape will not consists of separate pieces. Each input shape is solid; it will have no holes.

Testing

There are a number of input files in the assignment directory /export/home/class/cs-509/pa4; these files can be recognized by their two-letter filenames.

The program tg-viewer can be used to view either the input to or output from your pprogram; in either case, tg-viewer reads fron std-in. 

$ tg-viewer < cn

$ tg-solver < cn | tg-viewer

This page last modified on 18 March 2004.