Câu đố xe kẹt bãi đỗ: luật, chiến thuật và họ câu đố khối trượt

Câu đố xe kẹt bãi đỗ là loại câu đố khối trượt: trên một lưới ô vuông có nhiều chiếc xe dài ngắn khác nhau, mỗi xe chỉ tiến hoặc lùi theo chiều dọc thân xe; phải dịch chuyển các xe để giải phóng đường cho chiếc xe đỏ chạy ra cổng. Phiên bản phổ biến nhất trên lưới 6 × 6 do nhà thiết kế câu đố Nhật Bản Nob Yoshigahara sáng tác từ thập niên 1970. Nó thuộc họ hàng với câu đố "Tào Tháo chạy đường Hoa Dung" của Trung Hoa, cần ít nhất 81 nước. Phiên bản tổng quát của bài toán xe kẹt đã được chứng minh là cực kỳ khó đối với máy tính.

Luật cơ bản

• Bàn 6 × 6 ô, có một cổng ra ở mép phải, ngang hàng thứ ba.
• Các xe con chiếm 2 ô, xe tải chiếm 3 ô, nằm ngang hoặc dọc.
• Xe nằm ngang chỉ chạy sang trái, phải; xe nằm dọc chỉ chạy lên, xuống. Không xoay xe, không nhấc xe lên.
• Một nước là di chuyển một xe đi một hoặc nhiều ô theo hướng của nó (một số cách đếm tính mỗi ô là một nước).
• Mục tiêu: đưa chiếc xe đỏ (nằm ngang ở hàng thứ ba) ra khỏi cổng.

Luật đơn giản, nhưng bàn nhỏ chật chội khiến mỗi xe vừa là chướng ngại vừa là "chìa khoá" cho xe khác.

Khối trượt: một họ câu đố lâu đời

Câu đố xe kẹt thuộc họ "câu đố khối trượt" (sliding block puzzle), trong đó các khối hình chữ nhật trượt trong một khung mà không được nhấc lên.

"Hoa Dung đạo" mang tên trận Xích Bích trong tiểu thuyết Tam quốc diễn nghĩa: Tào Tháo thua trận, chạy qua đường Hoa Dung và bị Quan Vũ chặn lại, rồi được tha. Các khối nhỏ mang tên các tướng như Quan Vũ, Trương Phi, Triệu Vân, Mã Siêu, Hoàng Trung. Lưu ý đây là chi tiết trong tiểu thuyết của La Quán Trung, không phải sử liệu chắc chắn. Câu đố khối trượt mang tên này phổ biến ở Trung Quốc trong thế kỷ 20; nguồn gốc chính xác của nó vẫn còn được các nhà sử học câu đố tranh luận, có ý kiến cho rằng nó bắt nguồn từ các câu đố khối trượt phương Tây.

Vì sao câu đố xe kẹt khó

Chuỗi phụ thuộc

Muốn xe đỏ ra, phải dọn xe A đang chắn đường. Muốn dịch xe A, phải dọn xe B chắn chỗ A cần đi tới. Muốn dịch xe B lại cần dịch xe C... Câu đố khó là câu đố có chuỗi phụ thuộc dài và vòng vèo, có khi phải dịch một xe ra xa rồi lại đưa về chỗ cũ.

Nhiều nước phải đi "ngược" mục tiêu

Trong những màn khó, có lúc phải dịch xe đỏ lùi ra xa cổng để nhường chỗ cho xe khác, một điều trực giác không muốn làm. Những màn được thiết kế giỏi thường có ít nhất một khoảnh khắc như vậy.

Khó về lý thuyết

Năm 2002, Gary Flake và Eric Baum chứng minh phiên bản tổng quát của câu đố xe kẹt (trên bàn kích thước bất kỳ) là PSPACE-đầy đủ — cùng nhóm độ khó với câu đố đẩy thùng (bài câu đố đẩy thùng). Với bàn 6 × 6 thì máy tính vẫn duyệt được hết: các nghiên cứu duyệt toàn bộ các cấu hình 6 × 6 cho thấy cấu hình khó nhất cần khoảng 50 nước (tính mỗi lần dịch một xe, dù xa bao nhiêu ô, là một nước).

Chiến thuật giải

1. Tìm xe chặn trực tiếp: những xe dọc đang nằm trên hàng của xe đỏ, giữa xe đỏ và cổng.
2. Với mỗi xe chặn, hỏi: nó cần đi lên hay xuống? Xe dài 3 ô nằm dọc trên bàn 6 ô chỉ có thể tránh khỏi hàng thứ ba bằng cách đi hẳn xuống dưới (vì đi lên thì vẫn chạm hàng thứ ba nếu nó dài 3 ô và bàn chỉ có 2 hàng phía trên). Những suy luận như vậy loại bớt rất nhiều lựa chọn.
3. Lần ngược chuỗi phụ thuộc: viết ra "A cần B đi, B cần C đi"... cho tới xe có thể di chuyển ngay.
4. Làm ngược từ đích: tưởng tượng xe đỏ đã ở cổng, hàng thứ ba trống; các xe khác phải ở đâu? (bài giải ngược từ đích).
5. Đừng ngại lùi: dịch xe đỏ lùi lại hoặc đưa một xe ra xa có thể mở ra lối mới.

Câu đố xe kẹt và bãi đỗ xe thật

Ở nhiều thành phố châu Á, bãi đỗ xe chật hẹp và các hầm gửi xe chung cư đôi khi giống hệt một câu đố xe kẹt: xe đỗ kín, muốn lấy một chiếc ra phải gọi người dịch vài chiếc khác. Ở Việt Nam, các bãi giữ xe máy đông đúc, các con hẻm nhỏ nhiều xe đỗ ven cũng là "phiên bản đời thật" quen thuộc. Bài toán sắp xếp vị trí xe để lấy ra nhanh nhất là chủ đề nghiên cứu nghiêm túc trong ngành quản lý kho bãi và cảng biển — nơi các container xếp chồng phải được bốc dỡ theo thứ tự, mỗi lần nhấc một container đúng là một nước đi trong câu đố khối trượt khổng lồ.

Cũng có những hệ thống bãi đỗ xe tự động dạng xếp hình, trong đó máy móc tự dịch các tấm đỡ xe trong một khung lưới để đưa chiếc xe cần lấy ra cửa. Thuật toán điều khiển chúng giải đúng loại bài toán này mỗi lần có người lấy xe.

Góc nhìn hôm nay: tự làm câu đố xe kẹt bằng giấy

1. Kẻ một lưới 6 × 6 ô, mỗi ô khoảng 3 cm, đánh dấu cổng ra ở mép phải hàng thứ ba.
2. Cắt các mảnh bìa 3 × 6 cm (xe con) và 3 × 9 cm (xe tải), tô một mảnh xe con màu đỏ.
3. Xếp xe đỏ ở hàng thứ ba bên trái, rồi xếp các xe khác chắn đường.
4. Thử giải, rồi đổi vai: một người đặt câu đố, người kia giải.
5. Thử tìm cách bố trí mà cần nhiều nước nhất — một bài toán thiết kế hay (bài tự đặt câu đố hay).