“It has set off a 3x3 board having 9 block spaces out of which 8 blocks having tiles bearing number from 1 to 8. One space is left blank. The tile adjacent to blank space can move into it. We have to arrange the tiles in a sequence for getting the goal state”.
The 8-puzzle problem belongs to the category of “sliding block puzzle” type of problem. The 8-puzzle i s a square tray in which eight square tiles are placed. The remaining ninth square is uncovered. Each tile in the tray has a number on it.
A tile that is adjacent to blank space can be slide into that space. The game consists of a starting position and a specified goal position. The goal is to transform the starting position into the goal position by sliding the tiles around.
The control mechanisms for an 8-puzzle solver must keep track of the order in which operations are performed, so that the operations can be undone one at a time if necessary. The objective of the puzzles is to find a sequence of tile movements that leads from a starting configuration to a goal configuration such as two situations given below.
Figure (Starting State) (Goal State)
The state of 8-puzzle is the different permutation of tiles within the frame. The operations are the permissible moves up, down, left, right. Here at each step of the problem a function f(x) will be defined which is the combination of g(x) and h(x).
i.e. F(x)=g(x) + h (x)
g (x): how many steps in the problem you have already done or the current state from the initial state.
h (x): Number of ways through which you can reach at the goal state from the current state or Or
h (x): is the heuristic estimator that compares the current state with the goal state note down how many states are displaced from the initial or the current state. After calculating the f value at each step finally take the smallest f (x) value at every step and choose that as the next current state to get the goal
Let us take an example.
Figure (Initial State) (Goal State)
f (x) is the step required to reach at the goal state from the initial state. So in the trayeither 6 or 8 can change their portions to fill the empty position. So there will be two possible current states namely B and C. The f (x) value of B is 6 and that of C is 4. As 4 is the minimum, so take C as the current state to the next state.
In this step, from the tray C three states can be drawn. The empty position will contain either 5 or 3 or 6. So for three different values three different states can be obtained. Then calculate each of their f (x) and take the minimum one.
Here the state F has the minimum value i.e. 4 and hence take that as the next current state.
The tray F can have 4 different states as the empty positions can be filled with b4 values i.e.2, 4, 5, 8.
In the step-3 the tray I has the smallest f (n) value. The tray I can be implemented in 3 different states because the empty position can be filled by the members like 7, 8, 6.
Hence, we reached at the goal state after few changes of tiles in different positions of the trays.
This problem requires a lot of space for saving the different trays. Time complexity is more than that of other problems.
The user has to be very careful about the shifting of tiles in the trays. Very complex puzzle games can be solved by this technique.