Additional Practice Problems: 8-Puzzle

Problem Statement 1

Initial State S0

1 2 3

4 6 _

7 5 8

Goal State

1 2 3

4 5 6

7 8 _

Heuristic Used: Misplaced Tile Heuristic

Counts number of tiles not in their goal position
Blank _ is ignored

A* Evaluation Function

f(n)=g(n)+h(n)

g(n) = number of moves so far

h(n) = misplaced tiles
Each move cost = 1

STEP 1: Evaluate Initial State S0

State S0

1 2 3

4 6 _

7 5 8

Misplaced tiles: 6, 5, 8

Lists

CLOSED = { }
OPEN = { S₀ (f=3) }

STEP 2: Expand S0

Blank position → can move Up, Down, Left

Generate successors g=1

State S1 — Blank UP

1 2 _

4 6 3

7 5 8

Misplaced tiles: 3,6,5,8 → h=4

f(S1)=1+4=5

State S2 — Blank DOWN

1 2 3

4 6 8

7 5 _

Misplaced tiles: 6,8,5 → h=3

f(S2)=1+3=4

State S3 — Blank LEFT

1 2 3

4 _ 6

7 5 8

Misplaced tiles: 5,8 → h=2

f(S3)=1+2=3

Update Lists

CLOSED = { S₀ }
OPEN = { S₁(f=5), S₂(f=4), S₃(f=3) }

STEP 3: Select Node with Minimum f

Selected: S3(f=3)

STEP 4: Expand S3

State S3

1 2 3

4 _ 6

7 5 8

Blank can move Up, Down, Left, Right

New nodes with g=2

State S4 — Blank UP

1 _ 3

4 2 6

7 5 8

Misplaced tiles: 2,5,8 → h=3

f(S4)=2+3=5

State S5 — Blank DOWN

1 2 3

4 5 6

7 _ 8

Misplaced tiles: 8 → h=1

f(S5)=2+1=3

State S6 — Blank LEFT

1 2 3

_ 4 6

7 5 8

Misplaced tiles: 4,5,8 → h=3

f(S6)=2+3=5

State S0 — Blank RIGHT

(already visited → ignored)

Update Lists

CLOSED = { S₀, S₃ }
OPEN = { S₁(f=5), S₂(f=4), S₄(f=5), S₅(f=3), S₆(f=5) }

STEP 5: Select Node with Minimum f

Selected: S5(f=3)

STEP 6: Expand S5

State S5

1 2 3

4 5 6

7 _ 8

Blank moves Right

State S7 — GOAL

1 2 3

4 5 6

7 8 _

h(S7)=0

🎯 Goal reached → STOP

FINAL OPEN & CLOSED LISTS

CLOSED = { S₀, S₃, S₅ }
OPEN = { remaining nodes (not expanded) }

CLOSED List at the End ✅

CLOSED list contains only the states that were actually expanded:

OPEN List at the End ✅

Problem statement 2:

🔹 Problem Given

Initial State S0

1 2 3

5 _ 6

4 7 8

Goal State

1 2 3

4 5 6

7 8 _

Blank tile = _

🔹 Heuristic Used: Misplaced Tile Heuristic

Counts the number of tiles not in their correct goal position
Blank tile _ is ignored

h(n)=Number of misplaced tiles

🔹 Evaluation Function (A*)

f(n)=g(n)+h(n)

Where:

g(n) = number of moves from start
h(n) = misplaced tiles
Each move cost = 1

🔹 STEP 1: Evaluate Initial State S0S_0S0

State S0

1 2 3

5 _ 6

4 7 8

Misplaced Tiles

Misplaced tiles: 5, 4, 7, 8

Lists

CLOSED = { }
OPEN = { S₀ (f=4) }

🔹 STEP 2: Expand S0

Blank is at center → can move Up, Down, Left, Right

All children have g=1

State S1: Blank UP

1 _ 3

5 2 6

4 7 8

Misplaced tiles: 2,5,4,7,8 → h=5

f(S1)=1+5=6

State S2: Blank DOWN

1 2 3

5 7 6

4 _ 8

Misplaced tiles: 5,7,4,8 → h=4

f(S2)=1+4=5

State S3: Blank LEFT

1 2 3

_ 5 6

4 7 8

Misplaced tiles: 4,7,8 → h=3

f(S3)=1+3=4

State S4: Blank RIGHT

1 2 3

5 6 _

4 7 8

Misplaced tiles: 5,6,4,7,8 → h=5

f(S4)=1+5=6

Update Lists

CLOSED = { S₀ }
OPEN = { S₁(f=6), S₂(f=5), S₃(f=4), S₄(f=6) }

🔹 STEP 3: Select Node with Minimum f

Selected node: S3(f=4)

🔹 STEP 4: Expand S3

State S3

1 2 3

_ 5 6

4 7 8

Blank can move Up, Down, Right
(All new states have g=2g=2g=2)

State S5: Blank UP

_ 2 3

1 5 6

4 7 8

Misplaced tiles: 1,4,7,8 → h=4

f(S5)=2+4=6

State S6S_6S6: Blank DOWN

1 2 3

4 5 6

_ 7 8

Misplaced tiles: 7,8 → h=2

f(S6)=2+2=4

State S0S_0S0: Blank RIGHT

Already visited → ignored

Update Lists

CLOSED = { S₀, S₃ }
OPEN = { S₁(f=6), S₂(f=5), S₄(f=6), S₅(f=6), S₆(f=4) }

🔹 STEP 5: Select Node with Minimum f

Selected node: S6(f=4)

🔹 STEP 6: Expand S6

State S6

1 2 3

4 5 6

_ 7 8

Blank moves RIGHT

State S7 (GOAL)

1 2 3

4 5 6

7 8 _

h(S7)=0

🎯 Goal reached → Stop A*

🔹 FINAL OPEN & CLOSED LISTS

CLOSED List

Open List

Contains nodes generated but not expanded: