For this program, Design a class for representing a rectangular grid and use it to allow a user to query a grid interactively as part of a game.
Background:
Pegboard problems are single-player games played on a grid (or pegboard), in which moves are made by successively jumping and removing pegs from the pegboard. A peg can jump an adjacent peg if there is a slot adjacent to that peg in the opposite direction - horizontally, vertically, or diagonally. After a peg has been jumped, it is removed from the board (and possibly eaten). A typical objective of this problem is to begin with a full pegboard from which one peg has been removed, and determine a sequence of jumps which will result in one peg remaining, perhaps in the position from which the first peg was removed. A popular form of this problem involves a rectangular pegboard with 4 slots on a side (see below), which proves to be a challenging problem for a human being.
For instance, consider the example below, which demonstrates the first few moves of a session:
Pegboard Example
0 1 2 3
+---------+
0 | X X X X |
1 | X X X X |
2 | X X X X |
3 | X X X X |
+---------+
Which peg should be
removed to start? 3 1
Pegboard Example
0 1 2 3
+---------+
0 | X X X X |
1 | X X X X |
2 | X X X X |
3 | X O X X |
+---------+
Enter move: 1 3 3 1
Pegboard Example
0 1 2 3
+---------+
0 | X X X X |
1 | X X X O |
2 | X X O X |
3 | X X X X |
+---------+
Enter move: 2 0 2 2
Pegboard Example
0 1 2 3
+---------+
0 | X X X X |
1 | X X X O |
2 | O O X X |
3 | X X X X |
+---------+
Enter move: 1 1 1 3
A move can be characterized by the attributes (startPos, endPos), which respectively refer to the position of a peg that is about to jump (jumper) and the new position of the jumper. The position of the peg that is jumped and removed can be determined by averaging the respective row and column positions of startPos and endPos, provided those positions describe a legal move.
For instance, in the last panel of the example depicted above, the peg in position startPos=(3,3)can jump over the peg in position (2,3)and land in position endPos=(1,3). The "middle position" of the peg that gets jumped over can be found by averaging the coordinate values of startPos and endPos, i.e, ((1+3)/2,(3+3)/2) = (2,3).
The Assignment:
You will design and implement a class called Grid that represents a pegboard as described above. The underlying main data object in a Grid is a vector of vectors!!! Each row is itself a vector, where each element contains a value that designates either a full or empty cell. A Grid also knows how many rows and how many columns it has, and allows direct access to its grid elements via the [] operator -- that is, the element in row i, column j may be referred to as G[i][j]. A Grid also has an overloaded output operator so that it may be displayed on a console or saved in a file.
Your program should provide instructions for the user, print a copy of the board at each step, and allow the user to indicate the row and column numbers of the start position and end position for the next move. If the move is legal, the pegboard should be updated accordingly; otherwise the user should be prompted to enter a valid move. The user should also be permitted to quit at any time (especially when the game is over!)
NOTES:
you may NOT use the apmatrix class for your Grid definition.
You ARE allowed to use the DUPoint class, Pair class, or other classes developed in the text, labs, and/or lecture notes, as long as suitable credit is given.
You are allowed (and strongly encouraged) to use your Class Wizard to help generate your Grid code.
Details:
Your program should be designed for good usability.
Your Grid class should have a display method (for producing output with visible gridlines), as in the example above.
Notice that as an anomaly of C++ syntax, the declaration for the underlying vector in Grid class will be (assuming its name is "grid_");
vector< vector > grid_ ;
which specifically has a space separating the two ">" symbols. (Can you figure out why the space is needed?)
The overloaded subscript [] operator for a Grid is actually not complicated. It simply returns a reference to the n-th row of the underlying vector structure. Thus, its return value is a vector. (i.e, if we declare Grid g; then g[n] is the n-th row.) Because g[n] is itself a vector, we are immediately able to retrieve g[n][k] as the element in the n-th row, k-th column, without need to write additional code. Furthermore, because it is a reference to the n-th row, we are able to use g[n] (and therefore g[n][k]) on either the left-hand or right-hand side of an assignment statement.
You are to write the following methods for your Grid class, and use them in a program that allows a user to attempt to solve a pegboard problem by specifying the position of the first removed peg, and subsequently specifying moves to make.
bool isLegalMove(startPosRow,startPosColumn,endPosRow,endPosColumn)
returns true if the given move is allowable, that is:
startPos and endPos are legal positions on the board;
startPos and endPos are the correct distance apart;
there is a peg in startPos=(startPosRow,startColumn)
there is a peg in the calculated middle position, and
there is no peg in endPos=(endPosRow,endPosColumn).
For instance, given the pegboard in the example above, the move given by (0,3,2,1)is legal (and true is returned) because slots(0,3),(1,2) and(2,1)are consecutive slots along a diagonal, and there are pegs in slot(0,3)and slot(1,2)and no peg in slot(2,1).
void applyMove(startPosRow, startPosColumn, endPosRow, endPosColumn)
updates the elements of the pegboard by applying the move.