Java plz and Call your program NinePuzzle

Hurry really need it fast

Relevant topics: array lists, stacks, queues. You are given a frame that fits 9 square blocks. The frame contains 8 blocks, numbered 1 through 8, leaving one location empty. You can shift a neighboring block into the empty space, and your goal is to find a sequence of moves that results in the blocks numbered 1 through 8 going left to right, top row to bottom, with the lower right position empty. For example, the following sequence of configurations solves the puzzle: 1 3 1 2 3 1 2 1 2 3 2 8 4 4 5 4 8 8 6 3 5 6 1 | 2 3 4 5 7 86 4 5 7 86 1 2 3 4 5 6 78 5 7 7 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 1 - 9. 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 by 123489765. The output is either a sequence of strings giving the configurations of a solution, or -1 if no solution exists. 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. Relevant topics: array lists, stacks, queues. You are given a frame that fits 9 square blocks. The frame contains 8 blocks, numbered 1 through 8, leaving one location empty. You can shift a neighboring block into the empty space, and your goal is to find a sequence of moves that results in the blocks numbered 1 through 8 going left to right, top row to bottom, with the lower right position empty. For example, the following sequence of configurations solves the puzzle: 1 3 1 2 3 1 2 1 2 3 2 8 4 4 5 4 8 8 6 3 5 6 1 | 2 3 4 5 7 86 4 5 7 86 1 2 3 4 5 6 78 5 7 7 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 1 - 9. 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 by 123489765. The output is either a sequence of strings giving the configurations of a solution, or -1 if no solution exists. 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