DATE ASSIGNED: October 24, 2000
DUE DATE:  November 9, 2000, at 9:30 a.m. (in class)
 

Objectives

1. Practice working with your own classes

2. Developing a system to solve a problem
 

Introduction

Your assignment is given below. To solve it, write a program that reads the necessary information to compute and output the indicated values, as efficiently as possible. Following the pattern in the class example, first, design your program by specifying its behavior, identifying the objects and operations it needs to solve the problem, and then organizing the objects and operations into an algorithm. Then code your design in C++ using stepwise translation. Finally, test your program thoroughly.

Project

1. Your project is to develop a program to solve the tiling problem. You are given 9 tiles, with a pattern on each edge. Your program must arrange these tiles in a 3x3 square such that the edge of one tile matches the edge of the tile next to it. The tiles are given at the start, and they can be rotated as needed, or moved to a new location.

A tile has a symbol on each edge. A symbol can be any one of { a, b, c, d, A, B, C, D }. Here is an example tile:

--------------
|      a     |
|            |
|c          D|
|            |
|      B     |
--------------
 

Matching

In order for 2 tiles to match, they must share a common letter on the edges, but one must be a capital and the other must be lower-case. For example, the two tiles below match along the common edge shown:

--------------------------
|      a     |     b     |
|            |           |
|c          D|d         C|
|            |           |
|      B     |     a     |
--------------------------
 

These two tiles below also match along the common edge shown:

--------------------------
|      a     |     d     |
|            |           |
|b          c|C         b|
|            |           |
|      B     |     a     |
--------------------------
 

But these two tiles below DO NOT match along the common edge shown:

--------------------------
|      d     |     b     |
|            |           |
|c          D|D         C|
|            |           |
|      a     |     B     |
--------------------------

All tiles must match across all shared edges in order for the configuration to be a solution. There may be no solution for the given set of tiles. Or there could be several solutions for a given set of tiles. Your program only needs to say if there is a solution, and what that solution is.
 

Rotating

You can rotate a tile as many times as you need. For example,

--------------
|      a     |
|            |
|c          D|
|            |
|      B     |
--------------

can be rotated to any of the following:

--------------   --------------   --------------
|      c     |   |      B     |   |      D     |
|            |   |            |   |            |
|B          a|   |D          c|   |a          B|
|            |   |            |   |            |
|      D     |   |      a     |   |      c     |
--------------   --------------   --------------
 

2. INPUT: Your program should read a file who's name is passed as a parameter. If the user does not pass a parameter, then prompt the user to type the filename from the keyboard.

Here is an example input file:
aDBc bCad daDc
bdAA CDca dbcB
aCBd ADcB Abbd

Each group of 4 letters correspond to the north, east, south, and west patterns on the respective tile.
That is, the top right-most tile will look like:

--------------
|      d     |
|            |
|c          a|
|            |
|      D     |
--------------
 

3. OUTPUT: Output should be sent to the standard output. It should indicate if there is a solution, and show how the tiles are arranged if there is a solution. For example:

Yes, there is a solution.

--------------------------------------
|      a     |     b     |     d     |
|            |           |           |
|c          D|d         C|c         a|
|            |           |           |
|      B     |     a     |     D     |
--------------------------------------
|      b     |     A     |     d     |
|            |           |           |
|A          d|D         b|B         b|
|            |           |           |
|      A     |     b     |     c     |
--------------------------------------
|      a     |     B     |     C     |
|            |           |           |
|d          C|c         A|a         D|
|            |           |           |
|      B     |     D     |     c     |
--------------------------------------
 

4. Name your source file 'hmwk4.cc' and store it in your Panther directory. Create your own library files as well, and give them appropriate names. In this program, you MUST create your own classes, therefore you must have your own library files.
 

5. Be sure to include the appropriate information as comments in the header of your source file, as specified in homework #1's directions. Also make sure you understand the collaboration policy, and that you follow the standards given in class. (See homework #1, sections 5, 6, and 7).
 

6. Hint: This problem will take the computer longer than you expect. To see if your program is
working, try it first on a 2x2 puzzle, then make it work for 3x3. Your final program should work for 3x3, but if you turn in a perfectly working 2x2 version, we will deduct no more than 10 points.
 

7. Submit your program to the T.A. Include comments stating how the program should be compiled and run.

TURN IN A HARD COPY OF YOUR SCRIPT FILE IN CLASS, after you have completed the steps below.

Don't forget to submit you makefile also!

When you are finally done with your program, and are ready to submit it, do the following steps.

1. script hmwk4.log

This command starts recording all the things you type and the responses from the system. "hmwk4.log" is just the name of the file it creates.
2. cat hmwk4.cc

Shows the contents of the file. You may want to include other relevant commands, such as "ls -l", which gives a file list. Make sure that you repeat this as many times as you need to show all of the files (.h, .doc, .cc) that you used.
3. g++ yourlibraryfile.cc -c

Compiles "yourlibraryfile" without linking it. Repeat this step for every library file that you have.
4. g++ hmwk4.cc -o hmwk4 [yourlibraryfile1.o yourlibraryfile2.o ..]

Compiles it.
5. ./hmwk4

Runs your program. Be sure to try multiple test cases. Three test cases may be enough, but it is up to you to decide how many cases are enough.
6. ~/../csc6001/submit file1 hmwk4/csc60XX

This calls the "submit" program which is located in the TA's account. It copies the file "file1" to the TA's file space, under the subdirectory "hmwk4/csc60XX". Since everyone will have their own subdirectory under the TA's account, you can submit all of your files without needing to re-name them. Make sure that you submit all of the source files, including the .h, .cc, and .doc files. You do not submit the executable code - we will compile it ourselves. Once you submit a homework, you can re-submit it, but be careful not to do so after the due date and time. Read the submit program's response to make sure it was submitted properly.
7. exit

This command ends the recording of the things you type/system responses. You can now view "hmwk4.log"