8-Puzzle Problem in Artificial Intelligence

The 8-Puzzle Problem is one of the most important classical toy problems in Artificial Intelligence. It is used to teach state-space representation, problem formulation, search algorithms, heuristics, and optimal solution finding.

It is particularly useful for understanding BFS, DFS, Greedy Best-First Search and A*.

1. What is the 8-Puzzle Problem?

The 8-Puzzle consists of:

A 3 × 3 board
8 numbered tiles
One empty space (blank)
Tiles can be moved into the blank space.
The objective is to transform an initial arrangement into a specified goal arrangement.

A typical goal state is:

+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+
| 7 | 8 |   |
+---+---+---+

Here □ or a blank represents the empty position.

2. Example

Suppose the initial state is:

+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 |   | 6 |
+---+---+---+
| 7 | 5 | 8 |
+---+---+---+

Goal:

+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+
| 7 | 8 |   |
+---+---+---+

The AI has to determine which tiles should be moved and in what order to reach the goal.

3. Why is it called a Toy Problem?

The 8-Puzzle is called a toy problem because:

It is small.
The rules are clearly defined.
The state space can be represented systematically.
Actions are well defined.
The goal is clearly specified.
Search algorithms can be tested easily.

It is not a real-world problem itself, but it teaches concepts that are used in real-world AI systems.

4. State Representation

A state represents the current arrangement of all 8 tiles and the blank.

For example:

1 2 3
4 5 6
7 8 _

can be represented as:

(1,2,3,4,5,6,7,8,_)

Another state:

1 2 3
4 _ 6
7 5 8

can be represented as:

(1,2,3,4,_,6,7,5,8)

The AI uses this representation to compare states and search for a solution.

5. Components of the 8-Puzzle Problem

An AI problem can be formally described using:

Component	8-Puzzle
Initial State	Given starting arrangement
Actions	Move blank up/down/left/right
Transition Model	Produces new arrangement
Goal State	Desired final arrangement
Goal Test	Checks whether goal is reached
Path Cost	Usually number of moves

6. Initial State

The initial state is the starting configuration.

Example:

+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 |   | 6 |
+---+---+---+
| 7 | 5 | 8 |
+---+---+---+

The blank is in the center.

7. Goal State

The goal state is the desired configuration.

Usually:

+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+
| 7 | 8 |   |
+---+---+---+

The AI searches for a sequence of moves that transforms the initial state into this state.

8. Operators / Actions

The blank space can move:

       UP
        ↑
LEFT ← BLANK → RIGHT
        ↓
      DOWN

Therefore, possible actions are:

Move blank Up
Move blank Down
Move blank Left
Move blank Right

However, not every move is possible from every state.

Example

Suppose:

1 2 3
4 _ 6
7 5 8

The blank is in the center.

Therefore, it can move:

Up
Down
Left
Right

So four successor states can be generated.

9. State Transition

Suppose the current state is:

1 2 3
4 _ 6
7 5 8

If the blank moves Down, the 5 moves upward:

1 2 3
4 5 6
7 _ 8

This is a new state.

Similarly, moving the blank right gives:

1 2 3
4 6 _
7 5 8

Thus:

Current State
      ↓
   Action
      ↓
New State

10. State-Space Representation

The collection of all possible arrangements is called the state space.

For the 8-Puzzle, there are:\[ 9! \]

possible arrangements of the 9 positions.

However, only half of these arrangements are reachable from a given starting configuration.

Therefore, the number of reachable configurations is:\[ \frac{9!}{2} = 181,440 \]

This makes the problem much larger than the simple Water Jug Problem.

11. State-Space Search

The AI searches through the possible configurations.

For example:

                    Initial
                       |
             ┌─────────┼─────────┐
             ↓         ↓         ↓
           State     State      State
             |         |          |
          States     States      States
             |         |          |
             └─────────┼──────────┘
                       ↓
                    Goal?

The search algorithm determines which state should be explored next.

12. Search Algorithms for 8-Puzzle

Several search techniques can be used.

Uninformed Search

Breadth-First Search
Depth-First Search
Uniform Cost Search

Informed Search

Greedy Best-First Search
A* Search

The 8-Puzzle is particularly useful for demonstrating heuristic search.

13. Breadth-First Search

Breadth-First Search (BFS) explores states level by level.

Level 0
   ↓
Level 1
   ↓
Level 2
   ↓
Level 3
   ↓
Goal

If every move has equal cost, BFS can find a solution with the minimum number of moves.

Disadvantage

It can require a large amount of memory because it stores many states.

14. Depth-First Search

Depth-First Search (DFS) follows one path deeply before backtracking.

Start
 ↓
State
 ↓
State
 ↓
State
 ↓
Backtrack

DFS uses less memory than BFS in many situations, but it does not guarantee the shortest solution.

It can also spend a long time exploring an unproductive branch.

15. Why Do We Need Heuristics?

The state space can be large.

Searching every possible state blindly can be expensive.

Therefore, AI uses heuristics.

A heuristic gives an estimate of:

How far is the current state from the goal?

We commonly use two heuristics for the 8-Puzzle:

Misplaced Tiles
Manhattan Distance

16. Heuristic 1 — Misplaced Tiles

The misplaced tiles heuristic counts the number of tiles that are not in their correct positions.

Consider:

Current:

1 2 3
4 _ 6
7 5 8

Goal:

1 2 3
4 5 6
7 8 _

Compare the tiles:

1 → Correct
2 → Correct
3 → Correct
4 → Correct
5 → Wrong
6 → Correct
7 → Correct
8 → Wrong

Therefore:\[ h(n)=2 \]

So the heuristic value is:

2 misplaced tiles.

Usually the blank is not counted.

17. Heuristic 2 — Manhattan Distance

The Manhattan Distance measures how many horizontal and vertical movements each tile needs to reach its goal position.

It is calculated as:\[ h(n)=\sum |x_i-x_i^*|+|y_i-y_i^*| \]

where:

\(x_i,y_i\) = current position
\(x_i^*,y_i^*\) = goal position

Example

Current:

1 2 3
4 _ 6
7 5 8

Goal:

1 2 3
4 5 6
7 8 _

Tile 5 is one position away from its goal.

Tile 8 is one position away.

Therefore:\[ h(n)=1+1=2 \]

So:

Manhattan Distance = 2

18. Misplaced Tiles vs Manhattan Distance

Feature	Misplaced Tiles	Manhattan Distance
Measures	Number of wrong tiles	Distance of tiles from goal
Accuracy	Less informative	More informative
Calculation	Simple	More detailed
Common use	Basic heuristic	A* search
Example	2	2

Manhattan Distance usually provides more information because it considers how far a tile is from its destination.

19. A* Search

A* is one of the most important algorithms for solving the 8-Puzzle.

The evaluation function is:\[ f(n)=g(n)+h(n) \]

where:

\(g(n)\) = actual cost from initial state to current state
\(h(n)\) = estimated cost from current state to goal
\(f(n)\) = estimated total cost

Example

Suppose:\[ g(n)=5 \]

and\[ h(n)=3 \]

Then:\[ f(n)=5+3=8 \]

A* generally selects the state with the lowest f(n).

20. A* Example

Suppose we have three possible states:

State	g(n)	h(n)	f(n)=g+h
A	3	5	8
B	4	2	6
C	2	7	9

A* selects:

because:\[ f(B)=6 \]

is the smallest.

This demonstrates how A* combines:

Actual cost + Estimated future cost

21. Why A* is Suitable for 8-Puzzle

A* is highly suitable because:

The state space is relatively large.
We can calculate useful heuristics.
It avoids exploring many obviously poor states.
With an admissible heuristic, A* can find an optimal solution.
It demonstrates intelligent search rather than blind search.

22. Complete Example

Consider:

Initial State

1 2 3
4 _ 6
7 5 8

Goal

1 2 3
4 5 6
7 8 _

Step 1

Move blank down:

1 2 3
4 5 6
7 _ 8

Step 2

Move blank right:

1 2 3
4 5 6
7 8 _

Goal reached.

Therefore:

Initial
   ↓
Move Down
   ↓
Move Right
   ↓
Goal

Number of moves:\[ 2 \]

23. Problem Formulation

For examination purposes, formulate the 8-Puzzle as follows:

Initial State

Any valid arrangement of 8 tiles and one blank.

Actions

Move the blank:

Up
Down
Left
Right

when the move is legal.

Transition Model

Moving the blank exchanges its position with an adjacent tile.

Goal Test

Check whether the board matches the goal configuration.

Path Cost

Usually:\[ 1 \]

for every move.

Therefore:\[ Total\ Cost = Number\ of\ Moves \]

24. Important Concept — Admissible Heuristic

A heuristic is called admissible if it never overestimates the actual minimum cost to reach the goal.

For example:

Misplaced Tiles

If 3 tiles are misplaced, at least 3 moves are required to correct them.

Therefore:\[ h(n) \leq h^*(n) \]

where \(h^*(n)\) is the actual minimum cost.

Manhattan Distance

Manhattan Distance is also commonly used as an admissible heuristic for the standard 8-Puzzle because it does not overestimate the number of required tile moves.

This is important because an admissible heuristic allows A* to find an optimal solution under the usual conditions.

25. 8-Puzzle and Artificial Intelligence

The 8-Puzzle demonstrates several fundamental AI concepts:

8-Puzzle
   ↓
Problem Formulation
   ↓
State Representation
   ↓
State Space
   ↓
Operators
   ↓
Search
   ↓
Heuristics
   ↓
A* Algorithm
   ↓
Optimal Solution

Therefore, it is an excellent example for teaching intelligent problem solving.

26. 8-Puzzle vs Water Jug Problem

Feature	Water Jug	8-Puzzle
Type	Toy problem	Toy problem
State	`(x,y)`	Board configuration
Actions	Fill, empty, pour	Move blank
State space	Small	Larger
Heuristic	Usually not required	Very useful
BFS	Yes	Yes
DFS	Yes	Yes
A*	Possible	Very important
Main concept	State-space search	Heuristic search

27. Applications and Importance

Although the 8-Puzzle itself is a toy problem, its concepts are applicable to:

Robot path planning
Automated planning
Route planning
Game AI
Scheduling
Configuration problems
Puzzle solving
Planning and decision-making

The important idea is not the puzzle itself, but the ability to:

Represent a problem as states and actions and search intelligently for a goal.

28. Advantages

Simple to understand.
Excellent for teaching AI search.
Demonstrates state-space representation.
Demonstrates heuristic functions.
Useful for understanding A*.
Provides a controlled environment for comparing algorithms.
Shows the difference between uninformed and informed search.

29. Limitations

It is a simplified problem.
It has a relatively small state space compared with real-world problems.
Actions are deterministic.
There is no uncertainty.
There are no changing environmental conditions.
Real-world problems usually contain much more complex states and actions.

30. Exam-Oriented Answer

Definition

The 8-Puzzle is a classical toy problem in Artificial Intelligence consisting of eight numbered tiles and one blank space arranged on a 3×3 board. The objective is to transform an initial configuration into a specified goal configuration by moving tiles into the blank position. It is used to demonstrate state-space representation, search algorithms, heuristic functions and A search.*

Problem formulation

Initial State  → Any valid arrangement

Actions        → Move blank Up/Down/Left/Right

Transition     → Exchange blank with adjacent tile

Goal State     → Desired arrangement

Goal Test      → Compare current state with goal

Path Cost      → Number of moves

Important heuristics

\[ h_1(n)=\text{Number of misplaced tiles} \]\[ h_2(n)=\text{Manhattan Distance} \]

**A* Formula**

\[ \boxed{f(n)=g(n)+h(n)} \]

where:

g(n) = cost already incurred
h(n) = estimated remaining cost
f(n) = estimated total cost

Key takeaway for students

The 8-Puzzle demonstrates how AI can intelligently search a large state space by representing states, generating legal actions, evaluating states using heuristics, and selecting a path toward the goal.

A very useful sequence for remembering the topic is:

Initial State → Operators → Successor States → State Space → Goal Test → Heuristic → A* → Solution.

8-puzzle

8-Puzzle Problem in Artificial Intelligence

1. What is the 8-Puzzle Problem?

2. Example

3. Why is it called a Toy Problem?

4. State Representation

5. Components of the 8-Puzzle Problem

6. Initial State

7. Goal State

8. Operators / Actions

Example

9. State Transition

10. State-Space Representation

11. State-Space Search

12. Search Algorithms for 8-Puzzle

Uninformed Search

Informed Search

13. Breadth-First Search

Disadvantage

14. Depth-First Search

15. Why Do We Need Heuristics?

16. Heuristic 1 — Misplaced Tiles

17. Heuristic 2 — Manhattan Distance

Example

18. Misplaced Tiles vs Manhattan Distance

19. A* Search

Example

20. A* Example

21. Why A* is Suitable for 8-Puzzle

22. Complete Example

Initial State

Goal

Step 1

Step 2

23. Problem Formulation

Initial State

Actions

Transition Model

Goal Test

Path Cost

24. Important Concept — Admissible Heuristic

Misplaced Tiles

Manhattan Distance

25. 8-Puzzle and Artificial Intelligence

26. 8-Puzzle vs Water Jug Problem

27. Applications and Importance

28. Advantages

29. Limitations

30. Exam-Oriented Answer

Definition

Problem formulation

Important heuristics

A* Formula

Key takeaway for students

**A* Formula**