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 (3x3, 4x4, 5x5, …, 9x9). 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
Rmoves the empty cell right if there is room
Umoves the empty cell up if there is room
Dmoves 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.
