Kỹ thuật BFS tìm đường ngắn nhất trong Klotski

Khái niệm

Mỗi thế cờ Klotski là một trạng thái; mỗi nước đẩy một khối sang ô trống liền kề chuyển sang một trạng thái mới. Tìm đường ngắn nhất nghĩa là tìm chuỗi trạng thái ngắn nhất từ vị trí xuất phát tới trạng thái "khối chính đã ra cửa".

BFS (Breadth-First Search) duyệt các trạng thái theo từng lớp độ sâu: trước hết thử mọi nước 1 bước, rồi 2 bước, rồi 3 bước... Lần đầu tiên chạm đích chính là đường ngắn nhất.

Để tránh lặp vô hạn, các khối cùng kích thước được chuẩn hoá (hoán đổi vị trí không đổi bản chất thế cờ), giúp giảm không gian trạng thái từ hàng chục triệu xuống còn ~65.880 thế cờ cho Hoa Dung Đạo kinh điển.

Ví dụ

Bài "Hoành Đao Lập Mã" kinh điển cần đúng 116 bước (mỗi bước là một lần đẩy một ô). Bộ giải của Logicholic tính được con số này chính xác bằng BFS, khớp với tài liệu chuẩn quốc tế về sliding-block puzzle.

Nhờ đó gợi ý trong game luôn là nước đi tối ưu: mỗi lần nhấn gợi ý, số bước còn lại giảm đúng một bước.

Minh hoạ động