Description
You will write a C++ program that helps the user to solve the N-Puzzle problem. See descriptions
from the web to understand the problem and the rules. Sample solved 15-Puzzle (size 4) problem
board is below
An initial and a solved 8-Puzzle (size 3) game boards are below
When your program starts, it will first ask the user the size of the game (3×3, 4×4, 5×5, …, 9×9).
Then it will show a solvable random initial board configuration. There are some random
configurations that can’t be solved, be careful! Then, you will ask the user to input one of the
following and take action
Input Action
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
I makes an “intelligent” move for you. Intelligent
move moves the blank tile in a way that after the
move, the tiles are closer to their final positions. You
may add extra intelligence if you like!
S Shuffle- takes the board to the final solution, and
makes size*size random moves to shuffle the board.
Q Quits the game
Below is a sample output of your program.
Please enter the problem size
3
Your initial random board is
1 2 3
4 5
7 8 6
Your move: R
1 2 3
4 5
7 8 6
Your move: I
Intelligent move chooses U
1 2 3
4 5 6
7 8
Problem Solved!
Total number of moves 2
Notes:
Do not use any functions from the standard C library (like printf), use cout, cin, etc.
Your program should have only functions and no classes other than enums.
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.
