It have to be a c++ code.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).

//Plz dont give any java idea thanks.