Order Description

we introduced a problem called the checkboard problem, where you are given an n x n checkerboard, and the task of traversing the board from the bottom to top row, starting at any square in the bottom row, and ending at any square in the top row. You are only allowed to travel upwards on each move, from a square in row i to a square in row i + 1. Furthermore, you can only travel directly upwards,  or one square to the left or right of that square. From row i column j, you are only allowed to move to row i+1, column j-1 or column j or column j+1. So, if you were accessing a two-dimensional, row-major array in C/C++, Java, or Python, and your board was represented by array A, you could move from A[i][j] to one of: A[i+1][j-1], A[i+1][j], or A[i+1][j+1]. In the classic version of this problem, each square has a cost to traverse, and you pay the cost when you enter, so if you went from [3][4] to [4][4], you would add A[4][4] to the cost of the path. This also implies that while you do pay the cost for the square in the final row that you end your path on, you do not pay the cost for the square in the first row that you choose to start from.

In the version for this problem which we have to code, we want to model the problem as more of a planning a trip over physical terrain by moving from the center of a geographic square plot of land to the center of a neighboring square. We will start somewhere along the southern border of the land (row 0), and travel to the northern edge (row n-1). So, The cost to go from square [i][j] to [i+1][j] (i.e.,travelling straight north) would be (A[i][j] + A[i+1][j]) / 2; in other words, we are modelling that half our step would be travelling out of the originating square, and the other half would be travelling into the destination square, so we add half a unit’s worth of cost from each cell. To continue being more faithful to the travel analogy, when we go diagonally to the northwest or northeast, from [i][j] to [i+1][j-1] or [i+1][j+1] respectively, our cost would again be half cost of originating square and half ending square, but be scaled by √2 to reflect the fact that travelling diagonally gives a longer path. Also note that under this version of the problem, the square you pick for the starting row (at the bottom) does now contribute to the cost of the path, and the square in the top row you end in contributes half its cost.

Q1. Design an algorithm to solve this problem

Q2. Prove that the algorithm will generate a sound solution

Q3.  Write a well-structured, working implementation of your algorithm up in a language of your choice. Some implementation details:

a. We would strongly prefer C, C++, Java, or Python, and if you want to use a different language, you must get prior approval. You will also be required to demonstrate to a TA that your program does in fact run correctly.

b. We will provide an input file in the following format: the first line will contain a single value, n, indicating the dimensions of our square array. This will be followed by n additional lines, each containing n decimal numbers (i.e., floating point values). You should read this into a 2-dimensional array called A[][]. The first line of numbers would be read into A[0][0] .. A[0][n-1], and would represent the bottommost, starting row in our board. Your program should look for this file under the name “board.dat” in the current directory.

c. At the end, your program must produce the following output:

• An initial line containing a single number indicating the final cost of the optimal path

• A series of n lines, each consisting of a row and column number for a square in the optimal path. The lines should print the path from start to end, or end back to start, whichever is easier for your algorithm.

d. Your program file must be named “board_path”, (e.g., “board_path.py”). If it is written in C/C++ or Python, you must have an appropriate main() that runs the program; if you use Java, you must name your main class “board_path”, and that class should have a main() method.

Q4.  If we wanted to modify this algorithm to allow the path to also move directly left or right (e.g., from [i][j] to [i][j-1] or [i][j+1], would it be a relatively straightforward enhancement? You may either answer “yes”, and submit a second version called “board_path_plus” with the necessary updates, or answer “no” and give a detailed explanation for why the necessary modifications to the algorithm would be substantial.

Screenshots