Sói, Dê & Bắp Cải

Tổng quan

Câu đố sói, dê và bắp cải là một trong những bài toán qua sông cổ nhất được ghi lại, xuất hiện trong một bản chép tay khoảng thế kỷ 9. Người nông dân phải đưa ba thứ qua sông bằng chiếc thuyền mỗi lần chỉ chở được một món, trong khi hai cặp sẽ 'chết' nếu bị bỏ lại không ai trông.

Đây là bài toán tìm kiếm kinh điển: mỗi cách bố trí trên bờ là một trạng thái, mỗi lượt qua sông an toàn là một bước chuyển trạng thái. Điều khiến nhiều người bối rối là phải nhận ra đôi khi bạn cần mang một món quay ngược lại.

Cách giải Sói, Dê & Bắp Cải từng bước

1. Ghi nhớ hai cặp bị cấm: sói + dê, và dê + bắp cải. Con dê là 'thủ phạm' trong cả hai, nên không bao giờ được để nó ở cùng bất kỳ món nào kia.
2. Chở dê qua trước — sói và bắp cải ở cùng nhau vẫn an toàn — rồi quay về một mình.
3. Chở sói qua, nhưng mang dê về để nó không bao giờ ở lại cùng sói.
4. Chở bắp cải qua (để dê lại bờ gần), rồi quay về một mình.
5. Cuối cùng chở dê qua. Cả ba được đưa sang trong bảy lượt.

Mấu chốt

Nước đi không ai ngờ tới là mang dê quay lại ở lượt thứ ba. Lời giải không phải là một đường tiến thẳng — hoàn tác một bước đôi khi lại là cách duy nhất để tiến lên, đúng như cách tìm kiếm trên đồ thị thoát khỏi ngõ cụt.

Biến thể & liên hệ

• Bài toán nhà truyền giáo và người ăn thịt là cùng ý tưởng nhưng với ràng buộc an toàn theo số lượng thay vì theo cặp.
• Nó mô hình hóa mọi bài toán vận chuyển mà các trạng thái trung gian nguy hiểm — chẳng hạn xếp các hóa chất kỵ nhau.
• Đồ thị trạng thái chỉ có vài nút, nên tìm kiếm theo chiều rộng tìm ra lời giải tối ưu bảy bước ngay lập tức.

Câu hỏi thường gặp