What is N-puzzle problem?

The N-puzzle problem contains N tiles (N+1 including empty tiles) where the value of N can be 8, 15, 24, etc. The puzzle is divided into the square root of (N+1) rows and the square root of (N+1) columns. These problems have an initial state or configuration and a goal state or configuration. The puzzle can be solved by shifting the tiles one by one in the empty space. The objective is to place the numbers on the tiles to match the final state using the empty space. The other name for the N-puzzle problem is the sliding puzzle.

Example: N=8, then the square root of (8+1) = 3 rows and 3 columns.

What is 8 puzzle problem?

The 8-puzzle problem is invented and popularized by Noyes Palmer Chapman in the year 1870. It is played on a 3-by-3 grid with 8 square blocks/tiles labeled 1 through 8 and a blank square. The goal of this 8-puzzle problem is to rearrange the given blocks in the correct order. The tiles can be shifted vertically or horizontally using the empty square.

Rules to solve 8 puzzle problem

To solve the 8-puzzle problem, the tiles in the puzzle are moved in different directions. Instead of moving the tiles in the empty space, the user can visualize moving the empty space in place of the tiles, basically, swapping the tile with the empty space. The empty space cannot move diagonally and can make a single move at a time. The user can move the empty space in four different directions, and they are

• Up
• Down
• Right
• Left

Search techniques

 Generally, search techniques are classified into two types:

Uninformed search

In artificial intelligence, uninformed search techniques use the following search algorithms like linear search, depth-first search (DFS), binary search, and breadth-first search (BFS). These algorithms are named uninformed search because they do not know anything about what they are searching for and where they need to search for it. The uniformed search consumes more time.

Informed search

In artificial intelligence, the exact opposite of informed search is uninformed search. In this search, the algorithm will be aware of where the best chance of finding the solution is and what should be the next move. The informed search techniques are best-first search, hill-climbing, A*, and AO* algorithm. Heuristic search/function is an informed search technique.

The heuristic function is an informed search method, which informs the search regarding the goal direction. It provides data to estimate which neighboring node should lead to the goal state. A heuristic function is used to calculate the heuristic value. A heuristic value informs the algorithm which path will give an earlier solution. Based on the search problems various heuristic values are generated from the heuristic function. Thus, to optimize the search, heuristic value is used from the heuristic search technique.

A* algorithm

A* algorithm is an informed search technique algorithm. This is widely used in pathfinding and graph traversal, the process of plotting an efficiently traversable path between multiple points, called nodes. The key feature is the algorithm is that it will keep track of each visited node which helps in ignoring the nodes that are already visited. A* algorithm has a list that holds all the nodes that are left to be explored and it chooses the most optimal node from this list, thus saving time not exploring unnecessary (less optimal) nodes.

Open list contains all the modes that are being generated and are not existing in the closed list. Each node explored after its neighboring nodes are discovered is put in the closed list and the neighbors are put in the open list and this is how the nodes are expanded.

Each node consists of a pointer to its parent so that at any given point, the algorithm can retrace to the parent node. Initially, the open list holds the start (Initial) node. The next node chosen from the open list is based on its f score, the node with the least f score is picked up and explored. The formula to calculate f-score is,

f-score = h-score + g-score

h-score: estimated distance from the current node to the goal node.

g-score: total nodes traversed from the start node to the current node.

In the 8-puzzle problem, the h-score is defined as the count of misplaced tiles while comparing the goal and current state or the summation of the Manhattan distance between the misplaced nodes.

Manhattan distance

The distance between the tiles is measured along with the axes of the right angle. Manhattan distance is the sum of the absolute value of the difference between the current state(l,m) and goal state (I,j) coordinates, i.e. |i-l|+|j-m|.

How A* algorithm solves 8 puzzle problem?

In the initial state, the f-score for each state is calculated by moving the empty space in all possible directions. This process is known as expanding the current state. Given an initial state of an 8-puzzle problem and the final state to be reached, find the most cost-effective path to reach the final state from the initial state.

Find the heuristic value required to reach the final state from the initial state. The cost function, g(n)=0, as we are in the initial state. The value 1 in the current state is one horizontal distance away from the value 1 in the final state. The same goes for 2, 5, and 6. The empty space is 2 horizontal distances away and 2 vertical distances away. So total value for h(n) is 1+1+1+1+2+2=8. Total cost function f(n)=8+0=8.

The possible states that can be reached from the initial state are found. Only two moves are possible, either move the empty space to the right or down. So, the two states that obtained these moves are:

The total cost function is calculated for these states using the same method and it turns out to be 6 and 7. Select the state with the minimum cost which is the state (1). The next possible moves can be left, right, or down. We cannot move left as we were previously in that state. So, we can move either right or down. Again, we find the states obtained from the state (1).

State (3) leads to cost function f(n)=6 and state (4) leads to 4. Also, we will consider state (2) obtained before which has the cost function f(n)=7. Choosing minimum from them leads to state (4). The next possible moves can be left or right or down. We get states:

We get costs f(n)= 5, 2, and 4 for state (5), (6), and (7) respectively. Previous states (3) and (2) have costs 6 and 7. The minimum cost state is state (6). The next possible moves are up and down where down will lead us to the final state leading to a heuristic function value equal to 0. So, it is chosen and the puzzle is solved.

Context and Applications

This topic is important for postgraduate and undergraduate courses, particularly for,

• Bachelors in computer science engineering.
• Masters in computer science.

Practice Problems

Question 1: Select the search methods used in uninformed search?

1. BFS
2. DFS
3. Binary search
4. All the above

Answer: Option d is correct.

Explanation: In artificial intelligence, the uninformed search technique uses linear search, DFS, binary search, and BFS algorithms. These algorithms are named uninformed search as they do not know either the reason for the search or what they are searching for.

Question 2: To solve the 8-puzzle problem the tiles are swapped with ____.

1. Empty space
2. Queue
3. Successor
4. None of the above

Answer: Option a is correct.

Explanation: To solve the 8-puzzle problem the tiles are swapped with the empty space. The user cannot shift the empty space diagonally and can make a single shift at a time. The user can move the empty space in four different directions, like up, down, right, and left.

Question 3: select the correct formula to calculate the f-score.

1. f-score = h-score + g-score
2. f-score = h-score-g-score
3. f-score = h-score*g-score
4. f-score = h-score/g-score

Answer: Option a is correct.

Explanation: The formula to calculate f-score is h-score + g-score. Where h-score is the estimated distance from n to goal node and g-score is the total nodes traversed from the start node to the current node. In the 8-puzzle problem, the h-score is defined as the count of misplaced tiles while comparing the goal and current state or the summation of the Manhattan distance between the misplaced nodes.

Question 4: 8-puzzle game consists of ___ grids.

1. 4X4
2. 3X3
3. 3X4
4. 4X5

Answer: Option b is correct.

Explanation: In 8 puzzle game consisting of 3X3 grind with 9 tiles, where one tile will be empty and the rest will have numbers from 1 to 8. The tiles are moved to achieve the goal state.

Question 5: What is the formula to calculate the Manhattan distance?

1.  |i-j|+|l-m|
2. |i+l|+|j+m|
3. |i-l|+|j-m|
4. |i+j|+|l+m|

Answer: Option c is correct.

Explanation: Manhattan distance is the sum of the absolute value of the difference between the current state(l,m) and goal state (I,j) coordinates, i.e. |i-l|+|j-m|.