In C++

In this assignment, you have to develop a puzzle solver using the DFS algorithm. User will insert some values from 1 to 8 (including 0 and consider it to be an empty space) in a random order. Your puzzle solver will move a tile in each step and will lead to the goal state. See the image for the goal state. In your program, you have to print the following: 1. Each board state 2. Number of moves required to reach the goal state 3. Time taken to solve the puzzle.

Sample input:

1 2 3

8 0 4

7 6 5

Sample output:

Initial state:

1 2 3

8 0 4

7 6 5

Step 1:

1 3 4

8 2 0

7 6 5

step 2:

1 3 0

8 2 4

7 6 5

step 3:

1 0 3

8 2 4

7 6 5

step 4:

1 2 3

8 0 4

7 6 5

Time taken: 1.13ms

Marking scheme:

1. use of a structure to create the nodes.

2. Use a linked list to design a stack.

3. Use a class.

4. Proper use of DFS algorithm (your program should follow the basic principles of the DFS algorithm).

Three examples starting positions are defined as follows. 6 (a) (c) (b) Three starting positions for the eight puzzle:(a) requires Asteps; (b) requires Ssteps;(c) requires 18 steps. We assume that the goal position is the following: |- 123