## Description

In this homework, you will make additions to your N-Puzzle program. We will write an exhaustive

search algorithm that will find the best solution even if it takes too long to do so.

Your main class will be named NPuzzle. It will have the following public functions, most of which

are the same as HW3 (changes are marked with bold letters)

Fuction Name Explanation

print Prints the current configuration on the screen by sending it to cout

printReport Prints a report about how many moves have been done since reset and

if the solution is found

readFromFile Reads the current configuration from the file given as function

parameter. The file format is defined as in HW2. The vector of Board

objects is resized to 1. See below for details.

writeToFile Writes the current configuration to the file given as function

parameter.

shuffle Makes N random moves to shuffle the board. N is given as a function

parameter. The vector of Board objects is resized to 1. See below

for details.

reset Resets the current configuration to the solution. The vector of Board

objects is resized to 0.

setsize Sets the board size to given values. The values are given as parameters

and they can be at most 9×9. After setting the size, the boards should

be reset.

moveRandom Makes a valid random move. Move is recorded in vector of Board

objects. The vector of Board objects is resized to 1. See below for

details.

move Makes a move according to the given char parameter. If the

parameters is ‘L’ then, the blank tiles moves left, …, etc, as defined in

HW1. Move is recorded in vector of Board objects. The vector of

Board objects is resized to 1. See below for details.

solvePuzzle Runs the algorithm described below to solve the problem in

optimal number of steps.

Operator>> Prints the current configuration on the screen by sending it to

ostream object

Operator<< Reads the current configuration from the istream object. The file

format is defined as in HW2.

Your NPuzzle class defines and uses a private inner class named Board, which represents the

board configuration using a private 2D Vector. The class also has two other data members

The last move that it has performed

The number of moves make on this board from the beginning.

Your NPuzzle class does not use any other data to represent the board. This class defines the

following functions, most of which are the same as HW3 (changes are marked with bold letters)

Fuction Name Explanation

print Prints the board on the screen by sending it to cout

readFromFile Reads the board from the file given as function parameter. The file

format is defined as in HW2.

writeToFile Writes the board to the file given as function parameter

reset Resets the board to the solution.

setSize Sets the board size to given values. The values are given as parameters

and they can be at most 9×9. After setting the size, the boards should

be reset.

move Makes a move according to the given char parameter. If the parameter

is ‘L’ then the blank tiles moves left, …, etc, as defined in HW1.

isSolved Returns true if the board is a solution

Operator() Takes two indexes and returns the corresponding cell content.

Terminates program if the indexes are not valid.

Operator== Two boards are equal, if the boards are the same. This operator

does not consider last move or the number of steps

NumberOfBoards Returns the number of Board objects created so far.

lastMove Returns the last move, if there is no last move, returns ‘S’

numberOfMoves Returns the number of steps (moves) this board made

Your program will use objects of NPuzzle to perform what we did previously in HW3. Your

command line options and your user interface is very similar. The following table is repeated here

just for convenience.

Input Action

V Solves the problem from the current

configuration using the new algorithm.

T Prints a report about how many moves have been

done and if the solution is found

E Asks a file name and saves the current board

configuration as a loadable shape file.

O Asks a file name and loads the current board

configuration from the shape file.

L moves the empty cell left if there is room

R moves the empty cell right if there is room

U moves the empty cell up if there is room

D moves the empty cell down if there is room

S Shuffle- takes the board to the final solution, and

makes size*size random moves to shuffle the board.

Your new algorithm follows these steps

1. Your NPuzzle class keeps a vector of Board objects. Initially this vector contains a single

object that contains either the board from a file or shuffled board. The number of steps of this

board is 0.

2. Take the first element from this vector,

3. Apply all possible moves to this board and push_back each result back to the vector.

Before doing the push back, you should check if the same board is already in the vector. If

one of the pushed objects is the solution, then your solution is found.

4. Take another element from the vector in order and go to step 3.

Note that the above algorithm can stop in two cases: solution is found or there are no elements to take

from the vector. We expect that if there is a solution, we will find it. In order to demonstrate the

algorithm better, assume the initial 3×3 board vector in step 1 contains

1 2 3

4 5

7 8 6

Which will be represented as {((1234b5789),S,0)}, where S is the last move, 0 is the number

of moves. Step 2 takes this board and pushes back 4 new boards to the vector

{((1234b5786),S,0), ((12345b786),R,1), ((123b45786),L,1),

((1b3425786),U,1), ((1234857b6),D,1)}

Note that bold letters indicate the vector elements that are not chosen from the vector yet. Since, we

did not see the solution, we will pick the next element from the vector and go to step 3, which yields

{((1234b5786),S,0), ((12345b786),R,1), ((123b45786),L,1),

((1b3425786),U,1), ((1234857b6),D,1), ((12b453786),U,2),

((12345678b),D,2) }

We see that one of the newly added elements is the solution. We terminate the algorithm. From the

solution, we can go back to the original board by applying the inverse moves U and L. We see that

the solution needs just two moves.

Notes:

Do not use any C++ features that we did not learn during the lectures. Use all the OOPL rules

we learned in the class.

Do not forget to indent your code and provide comments.

Check the validity of the user input.

Test your programs very carefully at least with 10 different runs and submit your result

files for each.

You should submit your work to the moodle page and follow all the submission rules that will

be posted.