MÔ HÌNH MÃ ĐI TUẦN - HEURISTIC SEARCH ALGORITHM

Mô tả

Dự án này triển khai bài toán Mã Đi Tuần (Knight's Tour) sử dụng các thuật toán tìm kiếm heuristic. Bài toán yêu cầu quân mã di chuyển qua tất cả các ô trên bàn cờ, mỗi ô chỉ được thăm đúng một lần.

Thuật toán được triển khai

1. Warnsdorff's Rule (Quy tắc Warnsdorff)

• Nguyên lý: Tại mỗi bước, chọn nước đi có ít lựa chọn tiếp theo nhất
• Ưu điểm: Rất nhanh, hiệu quả cao
• Nhược điểm: Không đảm bảo luôn tìm được lời giải
• Độ phức tạp: O(n²) với n là kích thước bàn cờ

2. Backtracking với Heuristic

• Nguyên lý: Kết hợp backtracking (quay lui) với heuristic để sắp xếp thứ tự thử các nước đi
• Ưu điểm: Đảm bảo tìm được lời giải nếu tồn tại
• Nhược điểm: Chậm hơn Warnsdorff, đặc biệt với bàn cờ lớn
• Độ phức tạp: O(8^(n²)) trong trường hợp xấu nhất, nhưng được tối ưu bởi heuristic

Cấu trúc mã nguồn

knight_tour.py
├── Class KnightTour
│   ├── __init__()              # Khởi tạo bàn cờ
│   ├── is_valid_move()         # Kiểm tra nước đi hợp lệ
│   ├── get_valid_moves()       # Lấy danh sách nước đi hợp lệ
│   ├── count_accessible_squares()  # Đếm số ô có thể tiếp cận
│   ├── warnsdorff_heuristic()  # Hàm heuristic Warnsdorff
│   ├── solve_warnsdorff()      # Giải bằng Warnsdorff
│   ├── solve_backtracking_heuristic()  # Giải bằng Backtracking + Heuristic
│   ├── solve_with_backtracking()  # Wrapper cho backtracking
│   ├── print_board()           # In bàn cờ
│   ├── get_solution_path()     # Lấy đường đi
│   └── visualize_path()        # Trực quan hóa đường đi
└── main()                      # Hàm chính

Cách sử dụng

🎨 Giao diện đồ họa (Khuyến nghị)

Chạy chương trình với giao diện đồ họa trực quan:

python knight_tour_gui.py

Tính năng giao diện:

• ✅ Hiển thị bàn cờ dạng lưới với màu sắc
• ✅ Hiển thị số thứ tự từng bước đi
• ✅ Animation đường đi của quân mã
• ✅ Điều chỉnh tốc độ animation
• ✅ Chọn kích thước bàn cờ (3-15)
• ✅ Chọn vị trí bắt đầu
• ✅ Chọn thuật toán (Warnsdorff hoặc Backtracking)
• ✅ Hiển thị thời gian giải và số bước

💻 Chương trình dòng lệnh

Chạy chương trình dòng lệnh:

python knight_tour.py

Chương trình sẽ yêu cầu:

1. Kích thước bàn cờ: Nhập số nguyên (mặc định 8)
2. Vị trí bắt đầu: Tọa độ (hàng, cột) để bắt đầu (mặc định 0, 0)
3. Thuật toán: Chọn 1 (Warnsdorff) hoặc 2 (Backtracking + Heuristic)

Ví dụ sử dụng trong code

from knight_tour import KnightTour

# Tạo bàn cờ 8x8
knight = KnightTour(board_size=8)

# Giải bằng Warnsdorff
success = knight.solve_warnsdorff(0, 0)
if success:
    knight.print_board()
    knight.visualize_path()

# Hoặc giải bằng Backtracking + Heuristic
knight2 = KnightTour(board_size=8)
success = knight2.solve_with_backtracking(0, 0)
if success:
    knight2.print_board()

Đặc điểm kỹ thuật

Hướng di chuyển của quân mã

Quân mã có 8 hướng di chuyển:

(-2, -1)  (-2, 1)
(-1, -2)  (-1, 2)
( 1, -2)  ( 1, 2)
( 2, -1)  ( 2, 1)

Heuristic Function

Hàm heuristic đếm số lượng ô có thể tiếp cận từ một vị trí:

• Giá trị nhỏ hơn = ưu tiên cao hơn
• Giúp tránh "bẫy" (dead ends) sớm

Kết quả mẫu

Bàn cờ 8x8 với Warnsdorff

=================================
BÀN CỜ 8x8 - MÃ ĐI TUẦN
=================================
|  0|  3| 18| 21| 36| 39| 54| 57|
| 17| 20|  1|  4| 53| 56| 37| 40|
|  2| 19| 16| 35| 22| 41| 52| 55|
| 15| 34| 23| 42| 51| 38| 43| 48|
| 24|  9| 32| 45| 44| 49| 46| 59|
| 33| 14| 11| 50| 47| 60| 31| 62|
| 10| 25|  8| 29| 12| 27| 58| 61|
|  7| 28| 13| 26|  5| 30| 63| 64|

Yêu cầu hệ thống

• Python 3.6 trở lên
• Giao diện GUI: Tkinter (thường có sẵn trong Python, nếu chưa có thì cài đặt python-tk)
• Chương trình dòng lệnh: Không cần thư viện bên ngoài (chỉ sử dụng thư viện chuẩn)

Cài đặt Tkinter (nếu cần)

Windows: Thường đã có sẵn khi cài Python

Linux (Ubuntu/Debian):

sudo apt-get install python3-tk

macOS: Thường đã có sẵn

Tối ưu hóa

1. Sắp xếp heuristic: Các nước đi được sắp xếp trước khi thử, giảm số lần backtracking
2. Early termination: Dừng sớm nếu không còn nước đi hợp lệ
3. Efficient validation: Kiểm tra nhanh tính hợp lệ của nước đi

Mở rộng trong tương lai

• Thêm thuật toán A* search
• Hỗ trợ bàn cờ hình chữ nhật
• Trực quan hóa bằng matplotlib
• So sánh hiệu suất các thuật toán
• Tìm tất cả các lời giải có thể

Tác giả

Dự án được phát triển để minh họa các thuật toán heuristic trong bài toán Mã Đi Tuần.

Giấy phép

Dự án này là mã nguồn mở và có thể sử dụng tự do cho mục đích học tập và nghiên cứu.