Tangram

Predicates

• Input: sides/1, coord/3

• Output: put/4

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

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. 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).

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).

Input format

Output format

Example

Author(s)

• Author: Agostino Dovier
  • Affiliation: University of Udine, Italy
• Author: Andrea Formisano
  • Affiliation: University of Perugia, Italy
• Author: Enrico Pontelli
  • Affiliation: New Mexico State University, USA