Edge Matching

Problem description

A board is an NxM grid. There are NxM tiles. Each space must contain exactly one tile. Tiles are square and each edge has a colour. Tiles can be placed in any one of the four rotations. The task is to place the tiles so that every edge of every tile has the same colour as the edge it is adjacent to.

Input format

A number of tile facts, each giving a number (a range of consecutive, ascending integers, starting at 1) that identifies the tile.

A number of colour facts (strings, starting with "red", "green", "blue") giving the names of the colours.

A number of row facts (consecutive, ascending integers, starting at 1) that identifies the rows of the grid and a similar set of col facts giving the columns.

Four rotation facts, giving the possible rotations of each tile in the finished grid. These are 0,90,180 and 360. Rotation is clockwise.

Four side facts, giving the names of the four sides of each tile. These are "top", "right", "bottom" and "left".

A number of tileEdge facts, each giving a tile number, a side and a colour.

For example:

tile(1). tile(2). tile(3). tile(4). colour(red). colour(green). colour(blue). colour(black). row(1). row(2). col(1). col(2). rotation(0). rotation(90). rotation(180). rotation(270). side(top). side(right). side(bottom). side(left). tileSide(1,top,red). tileSide(1,right,green). tileSide(1,bottom,black). tileSide(1,left,black). tileSide(2,top,blue). tileSide(2,right,red). tileSide(2,bottom,black). tileSide(2,left,black). tileSide(3,top,green). tileSide(3,right,red). tileSide(3,bottom,black). tileSide(3,left,black). tileSide(4,top,red). tileSide(4,right,blue). tileSide(4,bottom,black). tileSide(4,left,black).

Output Format

The input facts plus a chosenTile and a chosenRotation fact for each tile, giving the (X,Y) location of the tile and the rotation respectively. The X is the horizontal offset and thus refers to the column in which the square is found. Y, the second component is the vertical offset and thus corresponds to the row in which it is located. Rotation is clockwise. For example, continuing the previous example:

chosenRotation(1,1,90). chosenRotation(1,2,0). chosenRotation(2,1,180). chosenRotation(2,2,270). chosenTile(1,1,1). chosenTile(1,2,3). chosenTile(2,1,2). chosenTile(2,2,4).

Authors: Martin Brain