welcome: please sign in

Revision 3 as of 2011-01-19 17:17:34

Clear message
location: FinalProblemDescriptions / Tangram

Tangram

Contents

  1. Tangram
    1. Predicates
    2. Problem Description
    3. Input format
    4. Output format
    5. Example
    6. Author(s)

Predicates

Problem Description

Tangram is an ancient Chinese game of Shapes. The goal is to form a particular shape from a set of seven pieces consisting of 5 triangles (of three different sizes), a square, and a parallelogram.

The number of sides, the sizes and basic orientations of the seven blocks is defined below. The 1st argument is the block number, the 2nd is the number of sides, then there is the sequence of coordinates of successive vertexes:

size_block(1,3, 0,0, 4,0, 2,2). %%% Large triangle
size_block(2,3, 0,0, 4,0, 2,2). %%% Large triangle
size_block(3,3, 0,0, 2,0, 0,2). %%% Medium triangle
size_block(4,3, 0,0, 2,0, 1,1). %%% Small triangle
size_block(5,3, 0,0, 2,0, 1,1). %%% Small triangle
size_block(6,4, 0,0, 1,-1, 2,0, 1,1). %%% Square
size_block(7,4, 0,0, 1,1, 1,3, 0,2). %%% parallelogram

Allowed angles are represented by the number 0..7 in parenthesis. You can assume MAXX=8 and MAXY=6.

Your program needs to compute a predicate put/4 that associates to each block i in {1,...,7} one pair (X,Y) and one angle A. With that association the entire surface of the instance figure must be covered (and without overlapping, but this is a consequence for the chosen figures).

Input format

Any input instance is defined using two predicates:

sides(n).

that fixes the number of sides of the figure and

coord(1,X1,Y1).
coord(2,X2,Y2).
...
coord(n,Xn,Yn).

that are the coordinates of the consecutive vertexes 1,2, ..., n of the figure. No need to say that the perimeter of the figure is the set of segments { (X1,Y1)-(X2,Y2), (X2,Y2)-(X3,Y3), ..., (Xn-1,Yn-1)-(Xn,Yn), (Xn-Yn)-(X1,Y1) }.

Although is clear that some of the sides of the 7 blocks have an irrational length, their orientation (above) as well as the orientations of the instances are chosen so as to work with integer numbers only.

The allowed action is to "put" the vertex corresponding to (0,0) in the above "size_block" definition in a point (X,Y) with X in {0,1,...,MAXX} and Y in {0,1,...,MAXY} rotated wrt its basic orientation by 0 (0), 45 (1), 90 (2), 135 (3), 180 (4), 225 (5), 270 (6), 315 (7) degrees.

Output format

A possible output should be of the form

put(1,4,0,0). put(2,4,4,6). put(3,4,0,2). put(4,0,0,0).
put(5,3,1,2). put(6,1,1,0). put(7,3,1,0).

that is also a correct solution of the instance

sides(3).
coord(1,0,0).
coord(2,8,0).
coord(3,4,4).

Example

Author(s)