Appropriate subjects used for this coding problem: stacks, queues, and array lists. Please read and follow all instructions. Thank you

JAVA coding problem:: You have a frame that fits 9 square bloccks. The frame has 8 blocks from 1-8, with one block not filled. You can move a nearby block into the not filled space, and the goal is to find a grouping of moves that end up with the squares numbered 1-8 going left to right, top row to bottom, with the lower right position empty.

Call this program Mamamoo. Write a program to solve this problem with the fewest number of moves. The input consists of a 9 digit string containing one each of the digits 19. The first three digits represent the first row, the next three digits represent the second row,and the last three digits represent the last row. The digit 9 represents the space. For example, the initial state of the puzzle given above would be represented by123489765. The output is either a sequence of strings giving the configurations of a solution, or 1 if no solution exists.

IMPORTANT:

The program will not be correct if:

- the output isn't correct

- the program ends up running for more than 10 seconds

- it gets an error of java.lang.OutOfMemoryError

- the program gets the solution with more than the minimal number of moves needed

3 1 2 3 12 1 23 48 6 1 2 4 S 76 12 48 3 6 5 12 4 5 78 6 6 78 6 78 For example, if the input is 123489765 then a correct output is 123489765 123485769 123485796 123495786 123459786 123456789 If the input is 812943765 then the correct output is -1 since the problem cannot be solved. If the input is 123456789 then the correct output is 123456789 since the problem is already solved. Notice that if there is a solution with n moves, then your program should print out n +1 lines, starting with the input line. 3 1 2 3 12 1 23 48 6 1 2 4 S 76 12 48 3 6 5 12 4 5 78 6 6 78 6 78 For example, if the input is 123489765 then a correct output is 123489765 123485769 123485796 123495786 123459786 123456789 If the input is 812943765 then the correct output is -1 since the problem cannot be solved. If the input is 123456789 then the correct output is 123456789 since the problem is already solved. Notice that if there is a solution with n moves, then your program should print out n +1 lines, starting with the input line