CSC2123 Assignment 1: Estimation and Measurement
Due: Monday, November 4th

Write a program to solve the problem given below. Use whatever programming language you are comfortable with. Before you start, estimate how long each phase will take. As you are working, maintain detailed records of your time spent on each phase, and of all the defects you encounter. After you are finsihed, complete a project summary, give statistics on your completed program, and write a brief (< 1 page) experience report. Use the forms indicated below.

The Problem

Write a program that solves a square slide puzzle of arbitrary size. Input the initial setup, and print out a shortest sequence of moves to solve the puzzle (hint: use a recursive backtracking algorithm that exhaustively searches all moves. To find the shortest solution iterate, searching for a solution of length n before searching for any solution of length n+1). The rules of the puzzle are as follows. The playing field is an n X n board in which all but one square contains a tile that can slide up, down, left or right (assuming an adjacent empty space). On any given move, A numbered tile may be slid (either vertically or horizontally) into the blank space. For example, consider the follwing initial and final positions for a 3x3 puzzle.
initial ->
583
 24
617
-> solved ->
123
456
78 

Phases

For consistency, divide your programming effort into the phases given at http://www.cs.toronto.edu/~penny/teaching/csc2123/phases.html. In performing these phases, you will need to circle back, or you may wish to jump ahead. This is fine. Record time into the most approrpiate phase. For example, if you start coding and realize that your design is bad. Re-think the design, charging that time to the design phase, and then continue coding, charging that time to the coding phase. If you discover design and significant coding errors during testing, charge time back to those phases (do not double-count into testing as well, though).

Forms

The forms you will fill in are as follows:

Hand in the completed forms, the program source code, and a brief (1 page) experience report discussing how and why your estimates diverged from the actuals. Also, e-mail me a tar file with the Makefiles and source code so that I can try out your program myself.

BE HONEST (sometimes great managers are poor coders!).
Only I will see your results (I will only display aggregates to the class).