Hành trình tìm kiếm cách xáo Rubik's Cube hoàn hảo của một lập trình viên đã tiết lộ một sự thật toán học đáng kinh ngạc: trong số hơn 43 tỷ tỷ cách sắp xếp có thể, chỉ có một giải pháp duy nhất đáp ứng tất cả các tiêu chí cho một cách xáo hoàn hảo. Khám phá này đã khơi dậy những cuộc thảo luận hấp dẫn trong cộng đồng giải đố về tính ngẫu nhiên, giới hạn tính toán và điều gì tạo nên một cách xáo thực sự hoàn hảo.
Thử thách bắt đầu khi lập trình viên cố gắng tạo ra một cách xáo mà không có hai ô cùng màu nào chạm vào nhau - một nhiệm vụ tỏ ra khó khăn bất ngờ qua các nỗ lực thủ công. Điều bắt đầu như một mục tiêu đơn giản đã phát triển thành một vấn đề tính toán phức tạp với sáu yêu cầu nghiêm ngặt, bao gồm việc có mọi màu trên mọi mặt và đảm bảo mỗi mặt hiển thị một mẫu khác nhau.
Yêu cầu Xáo trộn Hoàn hảo:
- Mọi màu sắc phải xuất hiện trên mọi mặt
- Không quá hai ô vuông của bất kỳ màu nào trên mỗi mặt
- Không có các ô vuông cùng màu chạm nhau theo chiều ngang hoặc dọc
- Không có các ô vuông cùng màu chạm nhau theo đường chéo trên bất kỳ mặt nào
- Không có các ô vuông cùng màu chạm nhau theo đường chéo qua các mặt khác nhau
- Mọi mặt phải có một mẫu hình khác nhau
Thử Thách Tính Toán Tiết Lộ Những Ràng Buộc Bất Ngờ
Việc tìm kiếm đòi hỏi phải kiểm tra các cách sắp xếp một cách có hệ thống thay vì ép buộc tất cả các khả năng. Ngay cả với tốc độ một triệu đánh giá mỗi giây, việc kiểm tra mọi cách sắp xếp sẽ mất hơn 1,3 triệu năm. Lập trình viên đã phát triển một phương pháp duyệt cây tinh tế, loại bỏ sớm các nhánh không thể để giảm 88 triệu cách sắp xếp góc xuống chỉ còn 130.632 ứng viên trong vòng chưa đầy một giây.
Các thành viên cộng đồng đã lưu ý đến sự mỉa mai trong những kết quả này. Các ràng buộc được thiết kế để làm cho khối lập phương trông ngẫu nhiên thực tế đã tạo ra kết quả bị ràng buộc nhất có thể - một giải pháp duy nhất với chỉ 48 hướng độc đáo. Điều này làm nổi bật cách nhận thức của con người về tính ngẫu nhiên thường xung đột với tính ngẫu nhiên toán học, tương tự như cách Spotify phải làm cho tính năng xáo trộn của họ ít ngẫu nhiên hơn để xuất hiện ngẫu nhiên hơn đối với người dùng.
Thống kê chính:
- Tổng số cách sắp xếp có thể có của Rubik's Cube: 43,252,003,274,489,856,000
- Giải pháp xáo trộn hoàn hảo được tìm thấy: 1 giải pháp duy nhất (48 hướng)
- Thời gian tính toán: 3 ngày
- Sắp xếp góc được giảm: 88,179,840 → 130,632 ứng viên
- Số nước để giải xáo trộn hoàn hảo: 18 nước (so với tối đa 20 nước có thể)
God's Number và Cuộc Tranh Luận Về Cách Xáo Hoàn Hảo
Cách xáo hoàn hảo được khám phá có thể được giải quyết chỉ trong 18 nước đi, thấp hơn nhiều so với mức tối đa đã được chứng minh là 20 nước đi cần thiết cho bất kỳ cách sắp xếp Rubik's Cube nào (được gọi là God's Number). Điều này đã dẫn đến những cuộc tranh luận thú vị về điều gì tạo nên một cách xáo thực sự hoàn hảo.
Một số thành viên cộng đồng cho rằng một cách xáo hoàn hảo nên yêu cầu đầy đủ 20 nước đi để giải quyết, đại diện cho độ khó tối đa có thể. Nghiên cứu từ năm 2010 đã xác định khoảng 490 triệu vị trí như vậy, mặc dù chúng chiếm ít hơn một phần tỷ trong tất cả các cách sắp xếp có thể. Những người khác gợi ý rằng cách xáo hoàn hảo không nên có mảnh nào ở vị trí ban đầu của chúng, điều mà giải pháp hiện tại không đáp ứng được.
Chuỗi nước đi:
- Tạo trạng thái xáo trộn hoàn hảo:
U' L2 F' D' U' R' F' D2 R B2 D2 U' L2 U - Giải trạng thái xáo trộn hoàn hảo:
U' L2 F2 D2 U' F B2 R' D2 F' R U D L2 U - Con số của Chúa (số nước đi tối đa cần thiết): 20 nước đi
- Các vị trí khoảng cách-20: ~490 triệu (ít hơn 1 trên tỷ)
Toán Học Đằng Sau Phép Màu
Quá trình giải quyết đã tiết lộ những hiểu biết hấp dẫn về toán học khối lập phương. Lập trình viên phải tính đến ba hạn chế chính: hướng của các mảnh góc phụ thuộc lẫn nhau (hướng của góc cuối cùng được xác định bởi bảy góc đầu tiên), hướng của các mảnh cạnh tuân theo các quy tắc tương tự, và tổng số lần hoán đổi phải là chẵn để khối lập phương vẫn có thể giải được.
Cuộc thảo luận của cộng đồng cũng đã đề cập đến các ứng dụng rộng hơn, từ việc mã hóa dữ liệu vào các vị trí khối lập phương (mặc dù không đủ an toàn cho mật mã học hiện đại) đến câu hỏi triết học về điều gì làm cho thứ gì đó xuất hiện ngẫu nhiên so với việc ngẫu nhiên về mặt toán học.
Kết Luận
Thành tựu tính toán này chứng minh cách các ràng buộc toán học có thể tạo ra những kết quả độc đáo bất ngờ. Trong khi cách xáo hoàn hảo có thể không trông ngẫu nhiên như một cách xáo thông thường, nó đại diện cho một giao điểm đáng chú ý của lập trình, toán học và lý thuyết đố. Thực tế rằng một tập hợp các yêu cầu cụ thể như vậy mang lại chính xác một giải pháp trong số hàng tỷ tỷ khả năng cho thấy trật tự ẩn giấu trong sự hỗn loạn rõ ràng - một lời nhắc nhở rằng trong toán học, sự hoàn hảo thường đi kèm với những hạn chế bất ngờ.
Tham khảo: The Rubik's Cube Perfect Scramble