The objective of this assignment is to practice writing recursive functions and to give you some introductory practice with programming in C++.
Imagine that we have an n by n chessboard. From any square on the chessboard, it is legal to move either one space directly forward, or one space forward and to the left, or one space forward and to the right (assuming such spaces exist). Associated with each such move is a point value; each point value is an integer which may be positive, negative, or zero. A path will be defined as a sequence of legal moves from any space in the first row of the chessboard to any space in the last row of the board. We can give each path a point value, which is the sum of the point values of all the moves making up the path. Our task is, given a particular chessboard with a set of point values, to find an optimal path -- that is, a path from any space in the first row to any space in the last row whose total point value is as large as possible. That is, an optimal path is a sequence of moves from some space in the first row to some space in the last row, having the highest point total of any such path. Note that there be more than one such path; there may be two (or more) sequences of moves with the highest possible point total. In that case, both would be considered optimal, and either one would be considered a valid solution for the problem.
A subpath is a path originating from any space on the chessboard (not necessarily in the first row) and extending to some space in the last row. Any subpath can be broken down into two components: a first move and the set of subsequent moves. The point value of the subpath is the point value for the first move plus the sum total of point values for all subsequent moves. In determining the optimal subpath extending from any space, we make use of the fact that whatever the correct first move is, the subpath extending from the subsequent space in the next row must be the optimal subpath extending from that space (otherwise, we could get from the next row to the last row in a shorter way, and thus the original subpath would not be optimal after all). The general solution to the problem is thus to find the optimal subpath extending from all spaces in the first row.
Since there are only (at most) three choices of where to proceed from any given square, it is easy to determine which should be the next move on the current path, if the current path is to be optimal. The next move should be whichever gives the highest total of:
1. The number of points associated with moving forward and to the left, plus the point total of the optimal subpath extending from the resulting square (if not already in the leftmost column);
2. The number of points associated with moving forward and to the right, plus the point total of the optimal subpath extending from the resulting square (if not already in the rightmost column);
3. The number of points associated with moving directly forward, plus the point total of the optimal subpath extending from the resulting square.
We begin by considering each square in the first row, finding the optimal subpath from each square, and in the process using recursion to find the optimal subpaths extending from each resulting second row square (and subsequently from each resulting third row square, etc.).
Your program must solve the optimal chessboard path problem by implementing a recursive function that finds an (any) optimal path for a particular chessboard. This function should solve for the optimal path using the recursive definition above. This function may call other functions, as you see fit. The prototype of this function is up to you; make sure to include it in the homework file detailed below.
It turns out that a call to your recursive function may make many recursive calls to itself with the same parameters, depending on how you write the function. To speed up your program, you may wish to implement a memoization table for your function. The memoization table would record, for each square of the chessboard, whether the optimal subpath from that square has already been computed, and if so, what the point total was. You would write your function so that when it is called (to compute the optimal subpath from a given square), it first checks the memoization table to see whether the optimal subpath has already been computed for that square. If so, it should simply use the point total value stored in the table rather than continue with recursive calls. If not, then the function will proceed normally, computing the optimal subpath and storing that information in the memoization table. The memoization table should also store the next move on the path, so that the optimal path itself can be reconstructed at the end. Note that the size of the memoization table depends on the size of the chessboard; however, since we have not yet covered dynamic allocation, you may assume that the chessboard will not be larger than 15 x 15.
There are two parts to the input your program must take: the number of rows / columns on the chessboard, and the set of point values associated with all possible moves on the chessboard. Your program will read all of this data in from one input file, whose name will be given as a command-line argument to your program. The first line in the file will contain the number of rows / columns, which you may assume is an integer between 1 and 15 (inclusive). Subsequent lines in the file will each contain three values: the point value to move forward and left, directly forward, and forward and right, in that order, from a particular square. Squares are listed left to right within each row, starting with the first row and ending with the next-to-last row (since you cannot move forward from the last row).
Example contents of an input file
3
0 2 4
2 0 -3
3 1 0
0 2 9
1 2 6
-2 -4 0
In the input file listed above, the chessboard contains 3 rows and 3 columns. From the middle square in the first row, moving forward and to the left carries 2 points, moving directly forward carries 0 points, and moving forward and to the right carries -3 points. From the rightmost square in the second row, moving forward and to the left carries -2 points, moving directly forward carries -4 points. Moving forward and to the right would be impossible. Note that three values appear on each line, regardless of whether all 3 moves are possible; impossible moves are given a point value of 0 as a placeholder, even though zero is a valid point value for a legal move. Thus, for any n by n chessboard, 3 values will always appear on each line of the input file (except the first line, which contains only the value of n).
Your program's output will also consist of two parts: the point total of an optimal path, and the sequence of moves in an optimal path. You should first print the point total of an optimal path, then the column where your path begins (a number between 1 and n), and finally the sequence of moves. You can use L to denote a move forward and to the left, F to denote a move directly forward, and R to denote a move forward and to the right. You should print your output to cout. (An example of correct output for a 4x4 chessboard would be: 12 3 L R F, meaning a point total of 12 on a path starting from the 3rd space from the left in the first row, and moving to the left, right, and finally forward.)
The homework portion of this project will be worth 10% of the project grade. For the homework, create a plain text file which includes the prototypes of the functions you intend to use, along with (approximately) a one- to two-paragraph description of how you intend to implement the solution to the problem and the general design of your program. You may use pseudocode if you wish. (This file is not intended to be compiled; it is only for you to express the design of your program.) Your homework will be graded both on the merits of your design and on the extent to which you follow that design in the implementation of your program. Remember to submit your homework file by the homework due date. Late homework submissions are not accepted.
You must include the following statement in a comment section of your program:
I have read and I understand the course policy on cheating. By submitting the following program, I am stating that the program was produced by my individual effort.
Turn in your program using the submit utility, by using the following command at the UNIX prompt:
submit cs202_02 <hw1 | proj1> <filenames>
where <filenames> is a list of the file(s) you wish to submit. Remember to submit a plain text file for the homework assignment (using hw1 as the assignment name), and your C++ source file(s) and makefile for the project (using proj1 as the assignment name). After entering this command, you should get a confirmation that submit was successful:
Submitting filename...OK
You can check your submission by entering the command:
submitls cs202_02 <hw1 | proj1>
This will show the names of all files you have submitted for this homework/project, along with the size and submission date and time of each.
This project is due by midnight on Sunday, 17 February 2002. We will use the system clock as the final arbiter of time and date. Projects turned in up to 24 hours late will receive a 10% penalty; project submitted between 24 and 48 hours late will receive a 25% penalty. Projects will not be accepted past 48 hours after the due date. The homework portion is due by midnight on Sunday, 10 February 2002; late homework submissions are not accepted.