java please make as sample as possible

5 star rating

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 2 3 1 2 3 1 23 1 2 3 1 2 3 1 2 3 4 8 485 48 5 4 45 4 5 6 7 6 5 76 7 6 7 8 6 78 6 78 5 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. Call your program NinePuzzle and upload it to Vocareum. Scoring: The grading will be based on five test problems, each counting two points. The tests will be run using java -Xmx1024m NinePuzzle The score will be 0 for a test problem if: (1) the output is incorrect; (2) the program runs for more than 10 seconds; (3) the program gives a java.lang. OutOfMemoryError; (4) the program obtains the solution with more than the minimal number of moves; (5) the program uses data structures that we have not covered in the course