🧩 Image Sliding Puzzle Solver

Ứng dụng giải trò chơi xếp hình trượt (Sliding Puzzle) sử dụng các thuật toán tìm kiếm trong Trí tuệ Nhân tạo, được xây dựng bằng Python với giao diện đồ họa Tkinter.

---

https://github.com/user-attachments/assets/e1b253ec-a112-4d5e-bfc6-c8eb4a407cec

📖 Mô tả

Chương trình cho phép người dùng:

1. Tải một ảnh bất kỳ và cắt thành lưới N x M (mặc định 3×3).
2. Xáo trộn các mảnh ghép ngẫu nhiên (đảm bảo trạng thái có lời giải).
3. Tự chơi bằng phím mũi tên hoặc để AI tự giải bằng một trong 4 thuật toán tìm kiếm.
4. So sánh hiệu suất các thuật toán qua bảng thống kê (thời gian, số node sinh ra, số node duyệt, số bước giải).

---

🤖 Các thuật toán được cài đặt

Thuật toán	Loại	Heuristic	Đảm bảo tối ưu
BFS (Breadth-First Search)	Tìm kiếm mù	Không	✅ Có (theo số bước)
DFS (Depth-First Search)	Tìm kiếm mù	Không	❌ Không
Greedy Best-First Search	Tìm kiếm có thông tin	Manhattan Distance	❌ Không
A* (A-Star)	Tìm kiếm có thông tin	Manhattan Distance	✅ Có

Hàm Heuristic — Manhattan Distance

Khoảng cách Manhattan được tính bằng tổng khoảng cách di chuyển (theo hàng và cột) của mỗi ô từ vị trí hiện tại đến vị trí đích:

h(state) = Σ |row_current(i) - row_goal(i)| + |col_current(i) - col_goal(i)|

---

🖥️ Giao diện ứng dụng

• Sidebar trái: Cấu hình (chọn ảnh, kích thước lưới), nút điều khiển (Random, Reset, chạy thuật toán), bảng lịch sử so sánh thuật toán.
• Khu vực chính (phải): Hiển thị puzzle dưới dạng lưới ảnh, hỗ trợ thao tác bằng phím mũi tên.
• Giao diện Dark Mode với bảng màu hiện đại.

---

🛠️ Cài đặt & Chạy

Yêu cầu

• Python ≥ 3.8
• Thư viện Pillow (xử lý ảnh)

Cài đặt thư viện

pip install Pillow

Chạy chương trình

python program.py

---

📂 Cấu trúc thư mục

BTL_AI/
├── program.py      # Mã nguồn chính (PuzzleSolver + PuzzleApp)
├── 1.jpg           # Ảnh mẫu để chơi puzzle
└── README.md       # Tài liệu hướng dẫn

---

🎮 Hướng dẫn sử dụng

1. Chạy python program.py.
2. Nhấn nút ... hoặc nhập đường dẫn ảnh vào ô "Đường dẫn ảnh" (có thể dùng file 1.jpg kèm theo).
3. Chọn kích thước lưới (Hàng × Cột), mặc định là 3×3.
4. Nhấn "TẢI ẢNH & TẠO GAME" để tạo puzzle.
5. Nhấn "Random" để xáo trộn.
6. Chơi thủ công bằng phím mũi tên hoặc nhấn một trong các nút thuật toán (BFS / DFS / Greedy / A-Star) để AI tự giải.
7. Quan sát quá trình giải qua animation và so sánh kết quả trong bảng "Lịch sử thuật toán".

---

🏗️ Kiến trúc mã nguồn

PuzzleSolver

Lớp chứa logic giải puzzle, bao gồm:

• get_neighbors() — Sinh các trạng thái kề bằng cách di chuyển ô trống (U/D/L/R).
• manhattan() — Tính hàm heuristic Manhattan Distance.
• solve_bfs() — Giải bằng BFS (dùng hàng đợi deque).
• solve_dfs() — Giải bằng DFS có giới hạn độ sâu (mặc định 50).
• solve_greedy() — Giải bằng Greedy Best-First (dùng heapq).
• solve_astar() — Giải bằng A* (dùng heapq).

PuzzleApp

Lớp xây dựng giao diện Tkinter, bao gồm:

• Quản lý tải ảnh, cắt ảnh thành tiles.
• Kiểm tra tính giải được (is_solvable) dựa trên số nghịch thế (inversion count).
• Chạy thuật toán trên thread riêng để không block giao diện.
• Animation hiển thị từng bước giải.
• Bảng Treeview ghi lại lịch sử và thống kê thuật toán.

---

📝 Ghi chú

• DFS sử dụng giới hạn độ sâu = 50 để tránh tìm kiếm quá lâu trên lưới lớn.
• Chương trình tự động kiểm tra trạng thái có lời giải trước khi xáo trộn.
• Hỗ trợ định dạng ảnh: JPG, JPEG, PNG, BMP.
• Kích thước ảnh được tự động resize về chiều rộng 700px để phù hợp giao diện.