Initial state
1 2 3
4 5 6
_ 7 8
Goal state
1 2 3
4 5 6
7 8 _
We’ll solve it with A* using:
- Heuristic : Misplaced tiles
Assume we generate moves in order: Up, Down, Left, Right.
What is g(n) actually?
Using Heuristic 1 – Misplaced tiles
g(n) = number of moves taken from the start state to reach the current state.
It is simply the depth / level of that node in the search tree.
Count how many tiles are not in the correct position (ignore blank).
Step 1: State S₀ (start)
1 2 3
4 5 6
_ 7 8
- Misplaced tiles: 7, 8 → h = 2
- g = 0 (no moves yet)
- f = g + h = 0 + 2 = 2
- Lists:
- Open list: { S₀ }
- Closed list: { }
- Now take S₀ from Open and expand it.
Children of S₀ (blank can go Up or Right):
Step 2: Expand S₀ → Generate S₁ and S₂
Child 1: Move blank UP → S₁
1 2 3
_ 5 6
4 7 8
Misplaced: 4, 7, 8 → h = 3
g = 1 (one move)
f = 1 + 3 = 4
Child 2: Move blank RIGHT → S₂
1 2 3
4 5 6
7 _ 8
Misplaced: only 8 → h = 1
g = 1
f = 1 + 1 = 2
Lists after expanding S₀:
- Closed list: { S₀ }
- Open list: { S₁ (f=4), S₂ (f=2) }
A* chooses the node with smallest f → S₂
Step 4: Expand S₂ → Generate S₃ and S₄
Expand S₂
Current S₂:
1 2 3
4 5 6
7 _ 8
Children (blank can go Up, Left, Right):
- Up → S₃
- 1 2 3
- 4 _ 6
- 7 5 8
Misplaced: 5, 8 → h = 2, g = 2, f = 4
- Left → S₀ again (already in closed) → ignore
- Right → S₄
- 1 2 3
- 4 5 6
- 7 8 _
This is the GOAL → h = 0, g = 2, f = 2
Now A* picks S₄ (goal) and stops.
- Move S₂ to Closed → Closed = { S₀, S₂ }
- Add S₃ to Open → Open = { S₁, S₃ }
BUT…
Since S₄ is the goal, according to A* rules:
The algorithm stops immediately.
So further updating of lists is not necessary.