Về mê cung - từ mê cung cổ đại đến câu đố do máy tạo

Con người đã vẽ và xây mê cung từ hàng nghìn năm, từ mê cung trong truyền thuyết Hy Lạp đến mê cung hàng rào cây trong vườn. Ngày nay máy tính tạo một mê cung mới chỉ trong tích tắc, và cách nó làm là ví dụ thú vị về việc quy tắc đơn giản tạo ra hình dạng phức tạp.

Chơi Mê cung
Một mê cung vuông trên nền xanh đậm, với dấu vết từ điểm xuất phát đến người chơi màu vàng
Một mê cung vuông trên nền xanh đậm, với dấu vết từ điểm xuất phát đến người chơi màu vàng

Mê cung một lối và mê cung nhiều nhánh

Mê cung cổ điển một lối chỉ có một con đường quanh co không có lựa chọn. Mê cung nhiều nhánh có ngã rẽ và ngõ cụt, nên bạn phải quyết định đi hướng nào. Mê cung hàng rào cây trở nên phổ biến trong các khu vườn châu Âu từ thế kỷ 16, và câu đố mê cung trên giấy được yêu thích từ đó.

Mê cung hoàn hảo

Mê cung hoàn hảo không có vòng lặp và không có vùng bị khép kín: giữa hai ô bất kỳ có đúng một đường đi. Theo toán học, các lối đi tạo thành một cây khung của lưới, nên mê cung có n ô có đúng n - 1 lỗ mở giữa các ô.

Máy tính tạo mê cung thế nào

Thuật toán quay lui đệ quy đi ngẫu nhiên qua lưới, phá tường sang các ô chưa đi qua và lùi lại khi bị kẹt. Nó tạo các hành lang dài với ít nhánh. Thuật toán Prim thì phát triển mê cung từ một ô ra ngoài, mỗi lần nối thêm một ô lân cận ngẫu nhiên, tạo ra nhiều ngõ cụt ngắn.

Mẹo giải

Trong mê cung hoàn hảo, bạn luôn đến được lối ra nếu giữ một tay trên tường và đi theo nó. Đó không phải đường ngắn nhất nhưng luôn hiệu quả. Nhìn từ lối ra ngược về điểm xuất phát cũng giúp ích, và dấu vết giúp bạn không đi vào cùng một ngõ cụt hai lần.

Hỏi thường xuyên

Mê cung nhiều nhánh khác mê cung một lối thế nào?

Mê cung một lối chỉ có một đường không có lựa chọn; mê cung nhiều nhánh có ngã rẽ và ngõ cụt. Trong đời thường cả hai đều được gọi là mê cung.

Quy tắc đi theo tường có luôn hiệu quả không?

Trong mê cung hoàn hảo thì có, vì mọi bức tường đều nối với nhau. Trong mê cung có vòng lặp, bạn có thể đi vòng quanh một hòn đảo mãi mãi.

Mê cung có thể lớn đến mức nào?

Ở đây tối đa 100 x 100 ô, tức 10.000 ô với một đường duy nhất giữa điểm xuất phát và lối ra.

Công cụ liên quan

Ví dụ Mê cung trong PictorX

Mê cung

Chơi mê cung miễn phí trên trình duyệt. Tìm đường từ điểm xuất phát màu xanh lá đến lối ra màu đỏ trong các mê cung từ 5 x 5 đến 100 x 100, đua với thời gian hoặc trong sương mù.

 Ví dụ Yahtzee trong PictorX

Yahtzee

Chơi Yahtzee miễn phí trên trình duyệt. Gieo năm viên xúc xắc tối đa ba lần, giữ những viên bạn muốn và điền 13 ô. Một mình, tối đa 4 người hoặc đấu với máy.

 Ví dụ Tháp Hà Nội trong PictorX

Tháp Hà Nội

Chuyển một tháp đĩa qua ba cọc ngay trên trình duyệt. Mỗi lần một đĩa, không bao giờ đặt đĩa lớn lên đĩa nhỏ. Lời giải ngắn nhất là 2ⁿ − 1 nước.

 Năm viên xúc xắc phía trên bảng điểm Yahtzee hai người chơi, một số viên đang được giữ

Về Yahtzee - trò xúc xắc của may mắn và lựa chọn

Cách chơi Yahtzee: năm viên xúc xắc và ba lần gieo, 13 ô, phần thưởng phía trên, thưởng Yahtzee, luật Joker và mẹo để ghi nhiều điểm hơn.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt của bạn — không cài đặt, không cần thiết thẻ tín dụng để khởi động.

Chơi Mê cung