Lab 2: 8-Puzzle Game with A* Search Algorithm

📋 คำสั่ง (Instructions)

ภาพรวมของโปรแกรม

ให้นักศึกษาเขียนโปรแกรม 8-Puzzle Game ที่มีคุณสมบัติดังนี้:

  1. แสดงผล Puzzle ขนาด 3×3 ที่มีตัวเลข 1-8 และช่องว่าง (แทนด้วย 0 หรือ space)
  2. รับคำสั่งจากผู้ใช้ เพื่อเลื่อนช่องว่างไปในทิศทางต่างๆ
  3. ค้นหาวิธีแก้ปัญหา ด้วย A* Search Algorithm เมื่อผู้ใช้ต้องการ

สถานะเป้าหมาย (Goal State)

┌───┬───┬───┐
│ 1 │ 2 │ 3 │
├───┼───┼───┤
│ 4 │ 5 │ 6 │
├───┼───┼───┤
│ 7 │ 8 │   │
└───┴───┴───┘

หรือในรูปแบบ Array: [[1, 2, 3], [4, 5, 6], [7, 8, 0]]

คำสั่งที่ต้องรองรับ

คำสั่ง คีย์ลัด คำอธิบาย
เลื่อนขึ้น W หรือ U เลื่อนช่องว่างขึ้นบน (สลับกับช่องด้านบน)
เลื่อนลง S หรือ D เลื่อนช่องว่างลงล่าง (สลับกับช่องด้านล่าง)
เลื่อนซ้าย A หรือ L เลื่อนช่องว่างไปซ้าย (สลับกับช่องด้านซ้าย)
เลื่อนขวา D หรือ R เลื่อนช่องว่างไปขวา (สลับกับช่องด้านขวา)
แก้ปัญหา SOLVE ใช้ A* Search หาวิธีแก้ปัญหา
รีเซ็ต RESET คืนค่า Puzzle กลับสู่สถานะเริ่มต้น (Goal State)
สุ่ม SHUFFLE สุ่มตำแหน่ง Puzzle (ต้องแน่ใจว่าแก้ได้)
ออก Q หรือ QUIT ออกจากโปรแกรม

📜 ข้อกำหนด (Requirements)

ข้อกำหนดทั่วไป

  1. ภาษาโปรแกรม: Python 3.8 ขึ้นไป
  2. ห้ามใช้ Library สำเร็จรูป สำหรับ A* Search (ต้องเขียนเอง)
  3. อนุญาตให้ใช้ Library มาตรฐาน เช่น heapq, copy, random

ข้อกำหนดด้านโครงสร้างโปรแกรม

1. Class PuzzleState

ต้องมี Class สำหรับเก็บสถานะของ Puzzle โดยมี attribute และ method ดังนี้:

class PuzzleState:
    def __init__(self, board, parent=None, move=None, depth=0):
        """
        board: 2D list ขนาด 3x3
        parent: PuzzleState ก่อนหน้า (สำหรับ backtrack)
        move: การเคลื่อนที่ที่ทำให้มาถึง state นี้
        depth: ความลึกจาก initial state (g(n))
        """
        pass
    
    def get_blank_position(self):
        """หาตำแหน่งช่องว่าง คืนค่า (row, col)"""
        pass
    
    def get_neighbors(self):
        """สร้าง state ใหม่จากการเลื่อนที่เป็นไปได้ทั้งหมด"""
        pass
    
    def is_goal(self):
        """ตรวจสอบว่าเป็น goal state หรือไม่"""
        pass
    
    def __eq__(self, other):
        """เปรียบเทียบ state"""
        pass
    
    def __hash__(self):
        """สำหรับใช้ใน set/dict"""
        pass
    
    def __lt__(self, other):
        """สำหรับ priority queue"""
        pass

2. Heuristic Functions

ต้อง implement heuristic function อย่างน้อย 2 แบบ:

Manhattan Distance (บังคับ)
h(n) = Σ |current_row - goal_row| + |current_col - goal_col|

สำหรับทุก tile (ยกเว้นช่องว่าง)

Misplaced Tiles (บังคับ)
h(n) = จำนวน tile ที่อยู่ผิดตำแหน่ง

3. A* Search Algorithm

def a_star_search(initial_state, heuristic='manhattan'):
    """
    Parameters:
        initial_state: PuzzleState เริ่มต้น
        heuristic: 'manhattan' หรือ 'misplaced'
    
    Returns:
        solution_path: list ของ moves ที่นำไปสู่ goal
        nodes_expanded: จำนวน nodes ที่ถูก expand
    """
    pass

สูตร A*: f(n) = g(n) + h(n)

4. การตรวจสอบ Solvability

ต้องมี function ตรวจสอบว่า puzzle configuration สามารถแก้ได้หรือไม่:

def is_solvable(board):
    """
    ตรวจสอบว่า puzzle แก้ได้หรือไม่
    โดยนับจำนวน inversions
    - ถ้า inversions เป็นเลขคู่ = แก้ได้
    - ถ้า inversions เป็นเลขคี่ = แก้ไม่ได้
    """
    pass

ข้อกำหนดด้าน User Interface

  1. แสดง puzzle board ในรูปแบบที่อ่านง่าย
  2. แสดงจำนวน moves ที่ผู้ใช้ทำไปแล้ว
  3. เมื่อ solve แสดง:

ข้อกำหนดด้าน Output

  1. Solution Path: แสดงเป็นลำดับทิศทาง เช่น ['UP', 'LEFT', 'UP', 'RIGHT', ...]
  2. Statistics: แสดงสถิติการค้นหา
  3. Step-by-step (Optional): แสดงแต่ละ step ของ solution

💡 ตัวอย่าง Input และ Output

ตัวอย่างที่ 1: การเริ่มต้นโปรแกรม

Output:

╔══════════════════════════════════════╗
║     8-Puzzle Game with A* Search    ║
╚══════════════════════════════════════╝

Current State:
┌───┬───┬───┐
│ 1 │ 2 │ 3 │
├───┼───┼───┤
│ 4 │ 5 │ 6 │
├───┼───┼───┤
│ 7 │ 8 │   │
└───┴───┴───┘

Status: SOLVED ✓
Moves: 0

Commands: W/U(Up) S/D(Down) A/L(Left) D/R(Right)
          SOLVE | SHUFFLE | RESET | QUIT

Enter command: _

ตัวอย่างที่ 2: การเลื่อน Puzzle

Input:

Enter command: U

Output:

Current State:
┌───┬───┬───┐
│ 1 │ 2 │ 3 │
├───┼───┼───┤
│ 4 │ 5 │   │
├───┼───┼───┤
│ 7 │ 8 │ 6 │
└───┴───┴───┘

Status: Not solved
Moves: 1
Last move: UP

Enter command: _

ตัวอย่างที่ 3: การเลื่อนหลายครั้ง

Input ต่อเนื่อง:

Enter command: L
Enter command: U
Enter command: L

Output หลังจากคำสั่งสุดท้าย:

Current State:
┌───┬───┬───┐
│ 1 │ 2 │ 3 │
├───┼───┼───┤
│   │ 4 │ 5 │
├───┼───┼───┤
│ 7 │ 8 │ 6 │
└───┴───┴───┘

Status: Not solved
Moves: 4
Move history: UP → LEFT → UP → LEFT

Enter command: _

ตัวอย่างที่ 4: การใช้คำสั่ง SHUFFLE

Input:

Enter command: SHUFFLE

Output:

Shuffling puzzle...

Current State:
┌───┬───┬───┐
│ 2 │ 8 │ 3 │
├───┼───┼───┤
│ 1 │ 6 │ 4 │
├───┼───┼───┤
│ 7 │   │ 5 │
└───┴───┴───┘

Status: Not solved (Solvable: Yes)
Moves: 0

Enter command: _

ตัวอย่างที่ 5: การใช้คำสั่ง SOLVE (A* Search)

Input:

Enter command: SOLVE

Output:

╔════════════════════════════════════════╗
║          A* Search in Progress         ║
╚════════════════════════════════════════╝

Initial State:
┌───┬───┬───┐
│ 2 │ 8 │ 3 │
├───┼───┼───┤
│ 1 │ 6 │ 4 │
├───┼───┼───┤
│ 7 │   │ 5 │
└───┴───┴───┘

Searching with Manhattan Distance heuristic...

═══════════════ SOLUTION FOUND ═══════════════

Solution Path (9 moves):
UP → UP → LEFT → DOWN → RIGHT → DOWN → LEFT → UP → UP

Statistics:
├─ Nodes Expanded  : 12
├─ Solution Length : 9 moves
├─ Time Elapsed    : 0.003 seconds
└─ Heuristic Used  : Manhattan Distance

Would you like to see step-by-step solution? (Y/N): _

ตัวอย่างที่ 6: แสดง Step-by-step Solution

Input:

Would you like to see step-by-step solution? (Y/N): Y

Output:

═══════════ STEP-BY-STEP SOLUTION ═══════════

Step 0 (Initial):        Step 1 (UP):
┌───┬───┬───┐            ┌───┬───┬───┐
│ 2 │ 8 │ 3 │            │ 2 │   │ 3 │
├───┼───┼───┤            ├───┼───┼───┤
│ 1 │ 6 │ 4 │     →      │ 1 │ 8 │ 4 │
├───┼───┼───┤            ├───┼───┼───┤
│ 7 │   │ 5 │            │ 7 │ 6 │ 5 │
└───┴───┴───┘            └───┴───┴───┘

Step 2 (UP):             Step 3 (LEFT):
┌───┬───┬───┐            ┌───┬───┬───┐
│   │ 2 │ 3 │            │ 2 │   │ 3 │
├───┼───┼───┤            ├───┼───┼───┤
│ 1 │ 8 │ 4 │     →      │ 1 │ 8 │ 4 │
├───┼───┼───┤            ├───┼───┼───┤
│ 7 │ 6 │ 5 │            │ 7 │ 6 │ 5 │
└───┴───┴───┘            └───┴───┴───┘

... (แสดงต่อจนครบทุก step) ...

Step 9 (Final - GOAL):
┌───┬───┬───┐
│ 1 │ 2 │ 3 │
├───┼───┼───┤
│ 4 │ 5 │ 6 │
├───┼───┼───┤
│ 7 │ 8 │   │
└───┴───┴───┘

🎉 Puzzle Solved!

Press Enter to continue...

ตัวอย่างที่ 7: การเปรียบเทียบ Heuristics

Input:

Enter command: COMPARE

Output:

═══════════ HEURISTIC COMPARISON ═══════════

Testing on current puzzle state...

┌─────────────────────┬────────────────┬──────────────────┐
│ Heuristic           │ Nodes Expanded │ Time (seconds)   │
├─────────────────────┼────────────────┼──────────────────┤
│ Manhattan Distance  │ 12             │ 0.003            │
│ Misplaced Tiles     │ 28             │ 0.008            │
└─────────────────────┴────────────────┴──────────────────┘

Both found solution of length: 9 moves

Analysis:
Manhattan Distance is more efficient because it provides
a tighter lower bound on the actual distance to goal.

Enter command: _

ตัวอย่างที่ 8: กรณีที่ Puzzle แก้ไม่ได้

Input (ถ้ามีการ set state ที่แก้ไม่ได้):

Enter command: SOLVE

Output:

⚠️  WARNING: This puzzle configuration is NOT solvable!

Current inversions: 21 (odd number)

A puzzle is solvable only if the number of inversions is even.

Would you like to shuffle to a solvable configuration? (Y/N): _

ตัวอย่างที่ 9: คำสั่งไม่ถูกต้อง

Input:

Enter command: X

Output:

❌ Invalid command: 'X'

Available commands:
  Movement : W/U(Up), S/D(Down), A/L(Left), D/R(Right)
  Actions  : SOLVE, SHUFFLE, RESET, COMPARE, QUIT

Enter command: _

ตัวอย่างที่ 10: การเลื่อนที่ไม่สามารถทำได้

Input (เมื่อช่องว่างอยู่ขอบบน):

Enter command: U

Output:

⚠️  Cannot move UP - blank is at the top edge

Current State:
┌───┬───┬───┐
│ 1 │   │ 3 │
├───┼───┼───┤
│ 4 │ 2 │ 6 │
├───┼───┼───┤
│ 7 │ 5 │ 8 │
└───┴───┴───┘

Enter command: _

📎 แนวทางการพัฒนา (Hints)

1. โครงสร้างไฟล์แนะนำ

8puzzle/
├── puzzle.py          # PuzzleState class
├── astar.py           # A* Search algorithm
├── heuristics.py      # Heuristic functions
├── game.py            # User interface & game loop
├── utils.py           # Helper functions
└── main.py            # Entry point

2. Priority Queue ใน Python

import heapq

# สร้าง priority queue
pq = []

# เพิ่ม item (priority, item)
heapq.heappush(pq, (priority, item))

# ดึง item ที่มี priority ต่ำสุด
priority, item = heapq.heappop(pq)

3. การแปลง 2D Board เป็น Tuple (สำหรับ hash)

def board_to_tuple(board):
    return tuple(tuple(row) for row in board)

4. Algorithm Pseudocode

function A_STAR(initial_state):
    open_set = priority queue with initial_state
    closed_set = empty set
    
    while open_set is not empty:
        current = pop state with lowest f(n) from open_set
        
        if current is goal:
            return reconstruct_path(current)
        
        add current to closed_set
        
        for each neighbor of current:
            if neighbor in closed_set:
                continue
            
            g_score = current.g + 1
            f_score = g_score + heuristic(neighbor)
            
            if neighbor not in open_set or g_score < neighbor.g:
                neighbor.g = g_score
                neighbor.f = f_score
                neighbor.parent = current
                
                if neighbor not in open_set:
                    add neighbor to open_set
    
    return failure (no solution)