Puzzle Solving

Write a program to find solutions to the 16 piece triangle matching puzzles.

These puzzles consist of a board and 16 pieces. Each piece has the head or tail of an animal on each of the three sides. The board contains the outline of a triangle built from 16 triangles fit together. Each edge of the board contains the head or tail of an animal.

Solutions contain the placement of each piece on the board such that every edge matches with the adjacent edge to produce a whole animal. For example, the head of an elephant must be next to the tail of an elephant.

Your program must read an input file named "input.txt". This file contains 21 lines. The first 16 lines define the pieces, and the last 5 lines define the board.

Each of the piece lines contains 3 letters followed by a newline. Upper case letters are used to represent the head of an animal and lower case letters are used to represent the tail of an animal. Each animal will be represented by a different letter, o for ostrich, l for lion, etc. For example, OzL describes a piece with the head of an ostrich, the tail of a zebra, and the head of a lion, in clockwise rotation.

Each row of the board description defines a row in the board edges, from top to bottom. The first 4 rows have a left and a right edge, while the last row contains 4 edges along the bottom of the board.

This is a sample input file for the example puzzle handed out in class:

OzL

coe

ooc

Elz

lgZ

oEc

gZO

gez

zEL

ZGC

oCc

Zog

OlG

GCe

zEE

eZL

Gz

OZ

LO

OZ

Clze

The program must produce an output file named "output.txt". This file consists of 17 lines per solution. Each of the first 16 lines describing the orientation and placement of a piece. The pieces should be described from top to bottom, from left to right. For all pieces the left edge of the triangle should be printed first, and the edges should be displayed in clockwise order. The final line is an empty line.

This is a sample output file for the example puzzle handed out in class:

gZO

oCc

coE

ezg

lgZ

GCZ

zEl

eGC

coo

oec

EzE

eZL

zLO

ogZ

GOl

LzE

A correct program will provide all solutions for each solvable puzzle that is given as input. For unsolvable puzzles, it will store the string Unsolvable in the output file.

For grading, the program will be run several times with different input puzzles. At least one puzzle will be solvable, and at least one puzzle will not be solvable. The program will be limited to ??? seconds of cpu time per puzzle. The score on this assignment will be based on the percentage of the puzzles that are correctly solved.