Tổng quan
Được công bố trên Life International năm 1962 và thường được gán cho Einstein, đây là nguyên mẫu của bài toán thỏa ràng buộc: mười bốn câu văn siết hai mươi lăm ẩn số xuống đúng một cách bố trí.
Cách giải Câu Đố Ngựa Vằn Của Einstein từng bước
- Hãy vẽ bảng 5 × 5 và chỉ viết một giá trị khi có dữ kiện bắt buộc. Bắt đầu từ các dữ kiện tuyệt đối: người Na Uy ở nhà 1, sữa ở nhà 3.
- Dùng các dữ kiện lân cận để đặt nhà xanh dương, rồi cặp ngà/xanh lá — dữ kiện về sữa loại bỏ phương án (3,4).
- Từ đó mỗi dữ kiện còn lại loại đúng một khả năng mỗi lần cho tới khi bảng được lấp đầy. Không bao giờ cần đoán.
Mấu chốt
Câu đố này là một bộ lan truyền ràng buộc chạy bằng tay. Mỗi bước là 'giá trị này chỉ còn đúng một chỗ hợp lệ', đúng là quy tắc lan truyền đơn vị mà một bộ giải SAT áp dụng hàng triệu lần mỗi giây.
Biến thể & liên hệ
- Sudoku, hình vuông Latin và n-hậu thuộc cùng họ; cả ba đều bị hạ bởi lan truyền-rồi-quay-lui.
- Viết dưới dạng chương trình logic, cả câu đố chỉ khoảng chục dòng Prolog hay MiniZinc và giải ra ngay lập tức.
Câu hỏi thường gặp
Einstein có thật sự viết nó không?
Gần như chắc chắn là không, và tuyên bố chỉ 2% người giải được cũng là truyền thuyết. Đây là một câu đố được dựng tốt, cần sự kiên nhẫn chứ không cần thiên tài.