Quy tắc bàn tay để thoát mê cung rất đơn giản: đặt một tay (ví dụ tay phải) lên tường và đi mãi không bao giờ nhấc tay ra; bạn sẽ đi hết dọc theo bức tường ấy và cuối cùng tới lối ra. Quy tắc luôn đúng với mê cung mà mọi bức tường nối liền với nhau và với tường bao ngoài. Nhưng nó thất bại khi mê cung có "đảo" — những cụm tường đứng riêng — hoặc khi mục tiêu nằm ở giữa mê cung. Khi đó cần phương pháp khác như thuật toán Trémaux, đánh dấu lối đã đi, giống như sợi chỉ của nàng Ariadne trong thần thoại Hy Lạp.
Mê cung một lối và mê cung nhiều lối
| Mê đạo một lối (labyrinth) | Mê cung nhiều lối (maze) | |
|---|---|---|
| Cấu trúc | Một con đường duy nhất uốn lượn từ lối vào tới trung tâm, không có ngã rẽ | Nhiều ngã rẽ, ngõ cụt, có thể có vòng |
| Có lạc không | Không, chỉ cần đi tiếp | Có |
| Ví dụ | Hình mê đạo trên sàn nhà thờ Chartres (Pháp, đầu thế kỷ 13), hình mê đạo trên đồng xu cổ ở đảo Crete | Mê cung cây cảnh ở cung điện Hampton Court (Anh, khoảng thập niên 1690), mê cung ngô ở các trang trại |
Trong tiếng Việt, cả hai thường đều được gọi là mê cung. Quy tắc bàn tay chỉ có ý nghĩa với loại thứ hai.
Vì sao quy tắc bàn tay hoạt động
Hãy tưởng tượng mọi bức tường của mê cung đều nối liền với nhau và với tường bao ngoài — các nhà toán học gọi đó là mê cung "liên thông đơn". Nếu "kéo thẳng" các bức tường ra, chúng tạo thành một sợi dây liền khép kín. Đặt tay lên tường và đi theo nó cũng giống như lần theo một sợi dây duy nhất: bạn sẽ đi dọc hết mọi chỗ của sợi dây, và lối ra — một chỗ hở trên tường bao — nằm đâu đó trên đường đi ấy.
Đường đi theo quy tắc bàn tay thường không phải đường ngắn nhất. Bạn sẽ đi vào và đi ra khỏi nhiều ngõ cụt. Nhưng bạn chắc chắn không bị lạc vòng mãi và chắc chắn tới được lối ra (hoặc trở về lối vào, nếu không có lối ra nào khác).
Khi quy tắc bàn tay thất bại
- Mê cung có đảo: nếu có một cụm tường đứng riêng không nối với tường bao, và bạn bắt đầu đặt tay lên cụm ấy, bạn sẽ đi vòng quanh nó mãi.
- Mục tiêu ở giữa: nếu đích là một khoảng trống ở trung tâm mê cung, và trung tâm nằm trên một cụm tường không nối với tường ngoài, quy tắc bàn tay đưa bạn ra lối vào chứ không vào trung tâm.
- Mê cung nhiều tầng, cầu vượt: các lối đi chéo qua nhau làm quy tắc không còn đúng.
Các nhà thiết kế mê cung thông minh thường cố ý tạo các đảo để quy tắc bàn tay không dùng được.
Thuật toán Pledge: thoát ra khỏi đảo
Năm 1980, theo một câu chuyện được nhiều sách kể lại, cậu bé 12 tuổi John Pledge ở Exeter (Anh) nghĩ ra một cải tiến: ngoài việc theo tường, đếm tổng số độ đã quay. Chọn một hướng ưu tiên (ví dụ hướng bắc). Đi thẳng theo hướng đó tới khi gặp tường, rồi theo tường bằng tay phải, cộng các góc quay (rẽ trái −90°, rẽ phải +90°). Khi tổng góc quay trở về 0 và đang hướng về phía bắc, rời tường và đi thẳng tiếp. Cách này giúp thoát khỏi mọi cụm tường đứng riêng để tìm ra mép ngoài của mê cung. Thuật toán được mô tả trong sách Turtle Geometry (1980) của Harold Abelson và Andrea diSessa.
Thuật toán Trémaux: sợi chỉ của Ariadne bằng phấn
Thần thoại Hy Lạp kể rằng anh hùng Theseus vào mê cung trên đảo Crete để giết quái vật Minotaur, và công chúa Ariadne trao cho chàng một cuộn chỉ. Chàng buộc đầu chỉ ở lối vào, vừa đi vừa thả chỉ, nhờ đó tìm được đường ra. Sợi chỉ chính là cách đánh dấu đường đã đi.
Thế kỷ 19, kỹ sư Pháp Charles Pierre Trémaux biến ý tưởng ấy thành một quy tắc chặt chẽ, được nhà toán học Édouard Lucas (người giới thiệu tháp Hà Nội) công bố năm 1882:
- Vừa đi vừa đánh dấu lối đi (bằng phấn) mỗi lần đi qua.
- Tới ngã rẽ chưa từng đến: chọn bất kỳ lối nào chưa đánh dấu.
- Tới ngã rẽ đã từng đến, theo một lối mới: quay lại theo lối vừa đi.
- Không bao giờ đi vào một lối đã được đánh dấu hai lần.
- Khi không còn lối nào để đi, quay lại theo lối chỉ đánh dấu một lần.
Thuật toán Trémaux luôn tìm được lối ra trong mọi mê cung (kể cả có đảo), và mỗi lối đi được đi qua nhiều nhất hai lần. Về bản chất, đây là thuật toán tìm theo chiều sâu (DFS) mà máy tính dùng ngày nay (bài tìm đường ngắn nhất).
So sánh các phương pháp
| Phương pháp | Cần nhớ gì | Luôn thoát được? | Đường ngắn nhất? |
|---|---|---|---|
| Đi ngẫu nhiên | Không | Cuối cùng có, nhưng có thể rất lâu | Không |
| Quy tắc bàn tay | Không | Chỉ với mê cung tường liền | Không |
| Thuật toán Pledge | Tổng góc đã quay | Thoát ra ngoài được, nhưng không tìm được trung tâm | Không |
| Thuật toán Trémaux | Đánh dấu lối đi | Có | Không nhất thiết |
| Tìm theo chiều rộng (có bản đồ) | Toàn bộ bản đồ | Có | Có |
Mê cung quanh ta
- Hampton Court ở ngoại ô London, trồng khoảng thập niên 1690 cho vua William III, là mê cung cây cảnh còn tồn tại lâu đời nhất ở Anh, rộng khoảng một phần ba héc-ta.
- Mê cung ngô: nhiều trang trại ở châu Âu, Bắc Mỹ cắt mê cung khổng lồ trên cánh đồng ngô mỗi mùa hè.
- Robot thi tìm đường: cuộc thi "micromouse" — robot chuột tự tìm đường tới trung tâm mê cung 16 × 16 ô — được tổ chức từ cuối thập niên 1970, robot phải khám phá mê cung rồi tính đường ngắn nhất.
Góc nhìn hôm nay: thử ba cách trên cùng một mê cung
- Vẽ một mê cung trên giấy, có một cụm tường đứng riêng ở giữa.
- Dùng bút đỏ đi theo quy tắc tay phải từ lối vào. Có tới lối ra không? Có đi qua trung tâm không?
- Dùng bút xanh đi theo Trémaux, đánh dấu chấm mỗi lần qua một lối.
- Dùng bút chì đánh số lan sóng (bài tìm theo chiều rộng) để tìm đường ngắn nhất.
- So sánh ba đường đi.
An toàn khi vào mê cung thật (cây cảnh, ngô): đi theo nhóm, mang điện thoại, nhớ số điện thoại ban quản lý, và dạy trẻ đứng yên chờ khi bị lạc.
Câu hỏi thường gặp
Quy tắc bàn tay để thoát mê cung là gì?
Đặt một tay lên tường và đi mãi không nhấc tay ra, luôn theo bức tường đó qua mọi ngã rẽ. Với mê cung mà mọi bức tường nối liền với tường bao ngoài, cách này chắc chắn đưa bạn tới lối ra, dù không phải đường ngắn nhất.
Khi nào quy tắc bàn tay không dùng được?
Khi mê cung có đảo, tức cụm tường đứng riêng không nối với tường bao, hoặc khi mục tiêu ở giữa mê cung, hoặc khi mê cung có cầu vượt nhiều tầng. Khi đó có thể đi vòng mãi hoặc không tới được trung tâm.
Thuật toán Trémaux là gì?
Là phương pháp thoát mọi mê cung bằng cách đánh dấu lối đi mỗi lần qua, ưu tiên lối chưa đi, quay lại khi gặp ngã rẽ cũ, và không đi vào lối đã đánh dấu hai lần. Nó được Édouard Lucas công bố năm 1882, bản chất là tìm theo chiều sâu.
Mê đạo và mê cung khác nhau thế nào?
Mê đạo một lối chỉ có một con đường duy nhất uốn lượn tới trung tâm, không có ngã rẽ nên không thể lạc. Mê cung nhiều lối có ngã rẽ, ngõ cụt và có thể có vòng, cần phương pháp để tìm đường.
Mê cung cây cảnh lâu đời nhất ở Anh là ở đâu?
Là mê cung ở cung điện Hampton Court gần London, trồng khoảng thập niên 1690 cho vua William III. Nó vẫn mở cửa đón du khách tới nay.