Program in C or Java

A 5 puzzle is a 3 X 2 grid with 5 tiles numbered 1...5 and an empty tile as shown in the figures below. A tile next to the empty space can be moved (left, right, up or down but not diagonally) into the empty space. The objective is to have the arrangement of tiles shown in the goal state.

For simplifying the problem the empty space is considered as tile 0. A state can be represented by the traversing the tiles row-wise (or row-major) starting from the top-left corner. So the state of the left hand figure is represented as 431502 while the goal state is 123450. An action at each state would be one of L(left), R(right), U(up) or D(down). For example, the action left on the random state given above would move tile 2 to its left into the empty space. Therefore, L(431502) would give the state 431520. Similarly, D(431502) (move tile 3 down) would give the state 401532. Notice that each state will have two possible actions if the empty space (tile 0) is at one of the corner squares and three possible actions if the empty space (tile 0) is in one of the middle squares. The cost of each action is the same. Write a program to find a solution to the 5-puzzle starting from a given state (that you will input) using iterative deepening search (IDS). While inputting the start state you should keep in mind that some states are never possible or invalid because the goal state is unreachable from those states. For e.g. 132450 is an invalid state for the above start/goal state. For testing the correctness of your program you can use the start state given in the example above. The action sequence D-L-U-R-R-D-L-L-U leads to the goal state.

Format of input and output

Your program should first prompt the user to enter an initial state in the format XXXXXX, where each X corresponds to a digit between 0 and 5; e.g., 431502 (no spaces between digits). The output of the program should be printed on two lines the first line should print out the goal state as Goal State is 123450 On the second line it should print out the action sequence, each move separated by a - (e.g., Solution: D-R-D-D) found by your algorithm