Introduction
The 8-puzzle problem is a classic example in Artificial Intelligence used to demonstrate state-space search and the difference between uninformed and informed search strategies.
It consists of a 3 × 3 grid containing eight numbered tiles (1–8) and one blank space (_).
The objective is to move the tiles (by sliding them into the blank) until they reach the goal state.
8 Puzzle Problem (Without Heuristic)
What is the 8 Puzzle?
It’s a 3×3 puzzle that contains 8 numbered tiles and 1 empty space (blank).
You can move the blank Up (U), Down (D), Left (L), or Right (R) by sliding an adjacent tile into it.
how we can solve the 8-puzzle problem using uninformed search — that means the agent has no clue how close it is to the goal.
It just tries every possible move until the solution is found.
Goal
Arrange the tiles in order like this:
1 2 3
4 5 6
7 8 _
That’s called the goal state.
Start State (given in image)
1 2 3
4 5 6
_ 7 8
Here, the blank ( _ ) is in the bottom-left corner.
Step 1: Generate Both Moves
(1) Move Up (U):
1 2 3
_ 5 6
4 7 8
(2) Move Right (R):
1 2 3
4 5 6
7 _ 8
✅ These are the first-level children of the start state.
Step 2: Expand the Next Level (BFS keeps exploring all states)
BFS now explores the next possible moves from each new state (U and R).
From state (U):
1 2 3
_ 5 6
4 7 8
Possible moves for blank ( _ ):
- Down (D) → goes back to start (we skip repeats)
- Right (R) → new state
Resulting in:
1 2 3
4 5 6
_ 7 8 ← same as start (skip)
and
1 2 3
5 _ 6
4 7 8
This one is not the goal.
From state (R):
1 2 3
4 5 6
7 _ 8
Possible moves:
- Left (L) → moves blank left to final position.
Resulting in:
1 2 3
4 5 6
7 8 _
✅ This is the goal state!
Among these, the From state (R), looks closer to the goal, but since this is without heuristic,
the algorithm doesn’t “know” that — it will explore both systematically.
The computer doesn’t know which move is good or bad — it’s not human!
It just tries all possible moves one by one.
So even if this state looks wrong (not the goal), it still checks what happens if it moves from here.
That’s why BFS or Uniform-Cost Search explores every branch of the puzzle’s tree.
Algorithm Used: Breadth First Search (BFS)
- BFS explores all possible moves level by level.
- It starts with the initial state and generates all new possible moves.
- It then continues exploring each new state until it finds the goal state.
This is why BFS is called an uninformed search — it doesn’t have any idea which path is better.
It just explores everything equally.
Time Complexity
BFS explores a lot of possibilities:
O(bᵈ)
where:
- b = branching factor (number of possible moves, usually 4)
- d = depth (number of moves needed to reach the goal)
So it can become very slow for large puzzles.
Conceptual Understanding
BFS explores all moves in layers:
- Start state
- All states one move away (U, R)
- All states two moves away (U→R, R→L, etc.)
It doesn’t skip any possibilities — that’s why it’s complete (it always finds the solution if one exists), but it’s also slow and memory-heavy.
Without heuristic → BFS explores every possible move level by level.
It guarantees a solution but is not efficient.
8-Puzzle Problem (With Heuristic)
Introduction
The 8-puzzle is a sliding-tile game that helps us understand how an AI agent can solve a problem by searching through different possibilities.
It has eight numbered tiles (1–8) and one empty space (blank) arranged on a 3×3 board.
We can move the blank up, down, left, or right by sliding an adjacent tile into it.
The aim is to reach a specific arrangement called the goal state.
Goal
Arrange the numbers in order like this:
1 2 3
4 5 6
7 8 _
Start State (Given)
1 2 3
4 5 6
_ 7 8
Here, the blank ( _ ) is in the bottom-left corner.
Our task is to move the blank around until we reach the goal state.
What is a Heuristic?
A heuristic is like a hint or intelligent guess that tells the agent
how close a given state is to the goal.
It does not guarantee the exact cost but helps the computer make smarter decisions —
it chooses the move that looks most promising.
Why Do We Need a Heuristic?
Without a heuristic (in uninformed search like BFS),
the computer explores every possible move, even those that go away from the goal.
That makes it slow and memory-heavy.
A heuristic gives direction — it tells the agent,
“which path seems closer to the goal,”
so the search becomes faster and smarter.
Heuristic Used Here: Number of Misplaced Tiles
We count how many tiles are not in their correct positions compared to the goal.
- Correct tile → 0 mistake
- Wrong tile → +1 mistake
This number is the heuristic value (h).
🪜 Step-by-Step Explanation
Step 1: Start State
1 2 3
4 5 6
_ 7 8
Compare with goal:
1 2 3
4 5 6
7 8 _
Misplaced tiles: 7 and 8 →
h(start) = 2
Possible moves of the blank (_):
- Up (U) → swaps with 4
- Right (R) → swaps with 7
Step 2: Move Up (U)
Move blank UP → swap _ with tile 4.
Resulting state:
1 2 3
_ 5 6
4 7 8
Now compare with the goal:
| Tile | Correct position? |
| 1,2,3,5,6 | Correct |
| 4 | Wrong place |
| 7 | Wrong place |
| 8 | Wrong place |
Misplaced = 3 → h(U) = 3
So this move actually makes things worse (h increases).
Step 3: Move Right (R)
Move blank RIGHT → swap _ with 7.
Resulting state:
1 2 3
4 5 6
7 _ 8
Compare with goal:
1 2 3
4 5 6
7 8 _
Only tile 8 is misplaced → h(R) = 1
This move brings us closer to the goal (h decreased).
So the algorithm will choose the Right (R) move.
Step 4: From This New State
Current:
1 2 3
4 5 6
7 _ 8
Possible moves for blank:
- Left (L) → back to previous state
- Up (U) → move blank up (creates more mistakes)
- Right (R) → swaps _ with 8
Try moving Right (R):
1 2 3
4 5 6
7 8 _
Now all tiles are correct → h = 0
Goal reached!
The computer doesn’t know which move is right —
but the heuristic gives it a clue.
When it moved UP, the puzzle looked worse (more misplaced tiles).
When it moved RIGHT, it looked better (fewer misplaced tiles).
So it kept going right until the puzzle was solved.
The 8-puzzle problem shows how heuristic search helps an AI agent think intelligently:
- It doesn’t blindly test every move.
- It uses the heuristic to measure how close each state is to the goal.
- It always chooses the move with the lowest heuristic value.
In our case, by using the heuristic “number of misplaced tiles,”
the agent solved the puzzle in just two smart moves (Right, Right) instead of exploring all possibilities.