8-Puzzle Problem in Artificial Intelligence

Definition:

“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”.

Procedure:

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)

Where

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)

Step 1:

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.

Step 2:

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.

Step 3:

The tray F can have 4 different states as the empty positions can be filled with b4 values i.e.2, 4, 5, 8.

Step 4:

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.

Comments:

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.

8 Puzzle Problem and Solution:

We also know the eight puzzle problem by the name of N puzzle problem or sliding puzzle problem.

N-puzzle that consists of N tiles (N+1 titles with an empty tile) where N can be 8, 15, 24 and so on.

In our example N = 8. (that is square root of (8+1) = 3 rows and 3 columns).

In the same way, if we have N = 15, 24 in this way, then they have Row and columns as follow (square root of (N+1) rows and square root of (N+1) columns).

That is if N=15 than number of rows and columns= 4, and if N= 24 number of rows and columns= 5.

So, basically in these types of problems we have given a initial state or initial configuration (Start state) and a Goal state or Goal Configuration.

Here We are solving a problem of 8 puzzle that is a 3x3 matrix.

Initial state Goal state

Solution:

The puzzle can be solved by moving the tiles one by one in the single empty space and thus achieving the Goal state.

Rules of solving puzzle

Instead of moving the tiles in the empty space we can visualize moving the empty space in place of the tile.

The empty space can only move in four directions (Movement of empty space)

Up
Down
Right or
Left

The empty space cannot move diagonally and can take only one step at a time.

All possible move of a Empty tile

o- Position total possible moves are (2), x - position total possible moves are (3) and

#-position total possible moves are (4)

Let's solve the problem without Heuristic Search that is Uninformed Search or Blind Search ( Breadth First Search and Depth First Search)

Breath First Search to solve Eight puzzle problem

Note: If we solve this problem with depth first search, then it will go to depth instead of exploring layer wise nodes.

Time complexity: In worst case time complexity in BFS is O(b^d) know as order of b raise to power d. In this particular case it is (3^20).

b-branch factor

d-depth factor

Let's solve the problem with Heuristic Search that is Informed Search (A* , Best First Search (Greedy Search))

To solve the problem with Heuristic search or informed search we have to calculate Heuristic values of each node to calculate cost function. (f=g+h)