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.
