Câu đố đẩy thùng là loại câu đố trong đó một người thủ kho đi trong nhà kho dạng lưới ô vuông, đẩy các thùng hàng vào đúng vị trí đích; chỉ được đẩy, không được kéo, và mỗi lần chỉ đẩy một thùng. Câu đố ra đời ở Nhật Bản năm 1981, do Hiroyuki Imabayashi sáng tác cho máy tính cá nhân, với tên Sokoban — nghĩa là "người giữ kho". Luật đơn giản nhưng câu đố có thể cực khó: các nhà khoa học máy tính đã chứng minh bài toán đẩy thùng tổng quát thuộc loại khó nhất trong các bài toán tìm kiếm. Bí quyết giải là nhận ra các "thế chết" — những vị trí mà thùng không bao giờ cứu được.
Luật cơ bản
- Bàn là lưới ô vuông gồm tường, sàn, thùng, ô đích và người thủ kho.
- Người thủ kho đi lên, xuống, trái, phải sang ô trống kề bên.
- Khi đi vào ô có thùng, người đẩy thùng đi một ô theo cùng hướng, nếu ô phía sau thùng trống.
- Không đẩy được hai thùng một lúc, không đẩy thùng vào tường, không kéo thùng.
- Thắng khi mọi thùng nằm trên ô đích.
Hai cách đếm thường dùng: số bước đi của người, và số lần đẩy thùng. Một màn có thể có lời giải ít lần đẩy nhất khác với lời giải ít bước đi nhất.
Lịch sử ngắn
Hiroyuki Imabayashi sáng tác câu đố năm 1981; công ty Thinking Rabbit của Nhật phát hành năm 1982 cho máy tính cá nhân, với 20 màn. Câu đố nhanh chóng lan ra nhiều nền tảng máy tính, và cộng đồng người yêu câu đố trên khắp thế giới đã sáng tác hàng chục nghìn màn mới. Nhiều màn nổi tiếng được thiết kế bởi những người chơi nghiệp dư, có màn cần hàng trăm lần đẩy.
Đẩy thùng cũng trở thành một bài toán chuẩn trong nghiên cứu trí tuệ nhân tạo và lập kế hoạch tự động, giống như câu đố 15.
Vì sao đẩy thùng khó
Không thể quay lại
Trong câu đố 15, mọi nước đi đều có thể đảo ngược. Trong đẩy thùng thì không: đẩy thùng vào góc là không thể kéo ra. Một nước sai có thể biến màn chơi thành không giải được, dù người giải chưa nhận ra ngay. Đây là điểm khác biệt lớn nhất.
Không gian trạng thái khổng lồ
Mỗi trạng thái gồm vị trí của mọi thùng và vị trí người. Với 10 thùng trên một bàn vài chục ô trống, số trạng thái có thể lên tới hàng tỷ. Máy tính phải dùng nhiều mẹo để cắt bớt.
Khó về mặt lý thuyết
Năm 1997, nhà khoa học máy tính Joseph Culberson (Đại học Alberta, Canada) chứng minh bài toán đẩy thùng tổng quát (bàn có kích thước bất kỳ) thuộc lớp PSPACE-đầy đủ. Nói nôm na: nó thuộc nhóm bài toán khó nhất mà máy tính có thể giải với một lượng bộ nhớ hợp lý, và nhiều khả năng không có thuật toán nào giải nhanh mọi màn. Năm 1999, Dorit Dor và Uri Zwick (Israel) phân tích thêm nhiều biến thể của bài toán và cũng chỉ ra chúng đều rất khó.
Thế chết: những vị trí không thể cứu
| Thế chết | Mô tả | Vì sao chết |
|---|---|---|
| Thùng ở góc | Thùng bị đẩy vào góc tạo bởi hai bức tường (không phải ô đích) | Không thể đẩy ra theo hướng nào, vì người phải đứng trong tường mới đẩy được |
| Thùng sát tường không có đích | Thùng nằm sát một bức tường dài, dọc tường đó không có ô đích nào | Thùng chỉ có thể trượt dọc tường, không bao giờ rời tường được |
| Hai thùng sát nhau dọc tường | Hai thùng nằm cạnh nhau sát tường | Không đẩy được thùng nào ra khỏi tường |
| Khối 2 × 2 | Bốn ô vuông kề nhau đều là thùng hoặc tường | Không thùng nào nhúc nhích được |
Người giải giỏi đánh dấu trong đầu các "ô chết" — những ô trống mà thùng đã vào là hết đường cứu — ngay từ đầu, và tránh đẩy thùng vào đó. Các chương trình máy tính giải đẩy thùng cũng làm đúng như vậy để cắt bớt hàng tỷ trạng thái vô ích.
Chiến thuật giải
- Xác định ô chết trước khi đẩy thùng nào.
- Xác định thứ tự lấp đích: các ô đích nằm sâu trong góc, cuối hành lang thường phải lấp trước, vì một khi các đích phía ngoài đã có thùng, sẽ chặn lối vào.
- Nghĩ ngược: tưởng tượng thùng đang ở đích và "kéo" nó ngược ra (luật ngược của đẩy là kéo). Đường kéo ngược từ đích ra vị trí ban đầu chính là đường đẩy theo chiều xuôi. Đây là cách một số chương trình giải làm (bài giải ngược từ đích).
- Giữ chỗ cho người: nhớ rằng người phải đi được ra phía sau thùng mới đẩy được. Thùng có thể chặn đường đi của chính người đẩy.
- Đẩy ít, đi nhiều: đi vòng để đứng đúng phía trước khi đẩy, thay vì đẩy vội.
Đẩy thùng và đời thật
Câu đố đẩy thùng mô phỏng một vấn đề có thật: sắp xếp hàng hoá trong kho, xếp xe trong bãi đỗ chật, điều khiển robot kho hàng di chuyển kệ. Những bài toán đó cũng có tính "không quay lại được" và cần lập kế hoạch trước nhiều bước. Ngành nghiên cứu lập kế hoạch tự động dùng các câu đố kiểu này để thử nghiệm thuật toán trước khi áp dụng vào việc thật.
Cũng có điểm liên hệ với vật lý: trong đẩy thùng, thùng chỉ di chuyển khi bị đẩy, đúng một ô, rồi dừng — như một thế giới có ma sát rất lớn. Còn trong câu đố trượt trên băng, vật trượt mãi tới khi đụng vật cản — thế giới gần như không ma sát. Hai loại câu đố là hai thái cực của ma sát (bài không có ma sát thế giới sẽ ra sao).
Góc nhìn hôm nay: tự làm màn đẩy thùng trên giấy
- Kẻ một lưới 7 × 7 trên giấy kẻ ô, tô viền ngoài làm tường, thêm vài ô tường bên trong.
- Dùng nắp chai làm thùng, đánh dấu chéo các ô đích, dùng một viên bi làm người thủ kho.
- Bắt đầu với hai thùng, giải thử, rồi thêm thùng thứ ba.
- Trước khi đẩy, tô màu nhạt các ô chết; sau vài màn, trẻ sẽ tự nhận ra quy luật góc và tường.
Câu hỏi thường gặp
Câu đố đẩy thùng là gì?
Là câu đố trong đó người thủ kho đi trên lưới ô vuông và đẩy các thùng vào ô đích. Chỉ được đẩy, không được kéo, mỗi lần chỉ đẩy một thùng. Câu đố do Hiroyuki Imabayashi sáng tác ở Nhật năm 1981 với tên Sokoban, nghĩa là người giữ kho.
Vì sao câu đố đẩy thùng khó?
Vì nhiều nước đi không thể đảo ngược: đẩy thùng vào góc là không kéo ra được, màn chơi thành không giải được. Không gian trạng thái rất lớn, và bài toán tổng quát được chứng minh là PSPACE-đầy đủ năm 1997.
Thế chết trong câu đố đẩy thùng là gì?
Là vị trí mà thùng không thể được đưa tới đích nữa, như thùng nằm ở góc tường, thùng sát tường mà dọc tường không có đích, hai thùng sát nhau dọc tường, hay khối bốn ô thùng và tường kề nhau.
Mẹo giải câu đố đẩy thùng là gì?
Xác định ô chết trước, lấp các đích nằm sâu trong góc trước, nghĩ ngược bằng cách tưởng tượng kéo thùng từ đích ra, và luôn chừa đường cho người đi ra phía sau thùng để đẩy.
Đẩy thùng khác câu đố trượt trên băng thế nào?
Trong đẩy thùng, thùng chỉ di chuyển một ô mỗi lần đẩy rồi dừng, như thế giới có ma sát rất lớn. Trong câu đố trượt trên băng, vật trượt mãi tới khi đụng vật cản, như thế giới gần như không ma sát.