Prog 6: Unscrambler Undo

Create a program similar to program 5 that:

1. Implements a class to store the board and implement various moves

2. Implements a linked list using a Node class to store all moves made in the game, and

3. Allows infinite undo of moves back to the beginning of the game.

Test and submit program 6 using Zybooks section 12.12

• To earn any points on this assignment you must implement and use the Board class, and must also implement undoing moves specifically using your own implementation of a linked list using a Node class.

• No late submissions will be accepted for program 6!

Grading will be done on only the automated tests, with no grading for programming style besides verifying that your implementation uses the required classes and linked list implementation. We will still run the program comparison tool, to compare the parts of code that you do write vs. what is supplied to you. Significant details and suggestions are given in the starter code, described more fully below.

Program Output Example

Running the program looks like the following, which can alternatively be accessed using this google doc:

Dictionary Words

The datafile to use for the dictionary is commonwords.txt

The dictionary words are used to create a Board, but once that is done we don't need to use the dictionary again unless we want to regenerate the board. You can handle the dictionary completely separately from the Board class if you want to, and this is the simplest approach to use.

If you do decide to put the dictionary into the class, see the notes at the bottom of this document.

Linked List Implementation

Your first step should be to get the program to work using classes, creating class Board(). To do this you should move the functions that manipulate the board into the class. Since they are in the class you will no longer need to pass parameters for elements like the board, destination board, and list of words on the board, since these will now be stored in the class. After the class is created, in main() you should declare an instance of Board, which will be something like: Board theBoard; This board is what you will manipulate as you make moves, changing the letters that are stored as rotations are made.

Only after you have changed the starting code to work using class Board should you turn your attention to implementing the linked list features. For the most part you should not need to change the code you have already written, but rather just add new code that uses what you already have. First read through the outlines of those features given in the starter code, and then implement these in the order shown below:

1. At the beginning of your program in main() declare pHead to be a Node pointer, and initialize it to NULL. pHead will be used to keep track of the head of the list. Depending on the structure of your program you may want to also declare pTemp to be a Node pointer. pTemp will be used in allocating new memory for new Nodes.

2. After creating the initial board within main(), create a linked list node and store into it a copy of the starting board and the current move number (1). Make this node the first node on the linked list. This should be done before the loop where you get user input and play the game. This first node should always be on the list.

3. The game-play loop checking for user input should be implemented in main(), as shown in the template code. Moves should still be made using the board that you used for the program version that uses classes but did not yet use a linked list. You will need to add the code to implement option 'U' for undoing a move. When the user attempts to undo a move at the beginning of the game, you will need to check to see if there is only the single starting node on the list. If there is only this single starting node, then give the error message: " *** You cannot undo past the beginning of the game. Retry. ***" and continue back up to retry.

4. When the user selects option ‘G’ to generate a new board, you should traverse the linked list and delete all the Nodes on it. Then you should recreate everything like you did when the program first started, prompting for the board size and number of scramble steps, creating an initial board, resetting the moveNumber, and storing the initial board on a node at the beginning of the linked list.

Putting a single Dictionary into the Board Class (optional)

As mentioned previously above, the simplest way to handle the dictionary is to do it outside the class, which is fine for you to do for this assignment. If you do decide to implement it inside the Board class, read on.

You will declare a single version of the dictionary that is available to all Board objects, but exists as a shared single data structure rather than each object having its own version of the dictionary, as described in the indented comments below, which you are not required to do:

Implement the single shared dictionary by declaring it within the Board class as static. To implement this do the following within class Board:

1. As part of the private section declare the vector as: static vector<string> dictionaryWords;

2. As part of the public section declare member function: static void readWordsIntoDictionary();

3. Outside the class, have a declaration that allocates memory for the dictionary words: vector<string> Board::dictionaryWords; It belongs to the class, but has to be defined outside the class so that memory is allocated for it on the stack.

4. Write function void Board::readWordsIntoDictionary() to open the input file and read words into vector dictionaryWords. Because this is a static function, you can invoke it without using a class object but using the class scope specifier as follows: Board::readWordsIntoDictionary();