Code Jam 2009 - Vòng 3

Phân tích: EZ-Sokoban

Đây là một bài toán tìm kiếm không gian trạng thái: cho một tập trạng thái (các vị trí trên bàn), một trạng thái đầu, một trạng thái cuối và các quy tắc chuyển trạng thái, hãy tìm một dãy nước đi biến trạng thái đầu thành trạng thái cuối. Trong bài này, ta cần độ dài của dãy nước đi ngắn nhất như vậy.

Về mặt khái niệm, ta có thể biểu diễn không gian trạng thái bằng một đồ thị. Các đỉnh của đồ thị là những cấu hình có thể có, còn các cạnh là những nước đi được phép. Bài toán trở thành tìm đường đi ngắn nhất trên đồ thị. Thuật toán chuẩn để giải bài toán đồ thị này là tìm kiếm theo chiều rộng (breadth-first search), hay BFS.

Hãy ước lượng số đỉnh của đồ thị. Với số thùng tối đa là 5, trước tiên xét số cấu hình trong đó mọi thùng đều liên thông. Năm thùng liên thông tạo thành một pentomino. Có 63 pentomino khác nhau nếu tính cả mọi phép quay và phản chiếu. Mỗi hình như vậy có thể được đặt ở không quá \(12 \times 12\) vị trí khác nhau. Do đó ta có cận trên \(63 \times 12 \times 12 = 9072\) cấu hình liên thông. Khó ước lượng chính xác hơn một chút số cấu hình “nguy hiểm”, nhưng từ mỗi cấu hình liên thông không có quá nhiều nước đi, nên có thể dự đoán tổng số cấu hình sẽ không quá lớn để máy tính xử lý.

Một cách là trước tiên sinh tường minh đồ thị cùng tất cả các cạnh, rồi chạy BFS trên đó. Cách khác là hoàn toàn không lưu đồ thị, mà khi duyệt đến một cấu hình thì mới tính các nước đi (các cạnh) có thể thực hiện từ cấu hình ấy, và chỉ lưu tập các cấu hình đã thăm trong một cấu trúc dữ liệu.

Một số chi tiết cần giải quyết:

• Biểu diễn cấu hình như thế nào. Một danh sách đơn giản chứa tọa độ các thùng là đủ. Ta cũng có thể dùng một mặt nạ bit cho toàn bộ bàn.
• Tra cứu cấu hình như thế nào. Ta cần thao tác này để biết một cấu hình đã được thăm chưa, hoặc để tránh tạo cùng một đỉnh của đồ thị nhiều lần. Có thể dùng một dạng cấu trúc dữ liệu từ điển — bảng băm hoặc cây tìm kiếm nhị phân.
• Sinh nước đi như thế nào. Chỉ cần thử di chuyển mọi thùng theo mọi hướng nếu ô phía trước và ô phía sau thùng đều trống. Ta cũng phải bảo đảm không di chuyển từ một cấu hình nguy hiểm sang một cấu hình nguy hiểm khác.
• Kiểm tra một cấu hình có nguy hiểm hay không. Ta cần kiểm tra từ 1 đến 5 thùng có liên thông toàn bộ không. Đây lại là một bài toán đồ thị nhỏ (tính liên thông của đồ thị). Chạy một BFS khác trên đồ thị nhỏ mà các đỉnh là các thùng, còn cạnh cho biết hai thùng có chạm nhau hay không. Một cách khác là sinh trước mọi polyomino có kích thước tối đa 5, lưu chúng trong bảng băm, rồi tra cứu hình dạng xuất hiện trong một cấu hình cho trước.

Nguồn

Bản dịch dựa trên phân tích chính thức của Google Code Jam 2009 - Round 3 - EZ-Sokoban, thuộc kho Google Coding Competitions (Apache-2.0).