Các nhà khoa học, với sự trợ giúp của Google, đã chứng minh được mọi vị trí của Rubik 3x3 đều có thể giải được trong không quá 20 bước. Đây được xem như là kết quả cuối cùng trong các nghiên cứu về Rubik 3x3, vì từ 15 năm trước, người ta đã biết rằng có những vị trí cần tối thiểu 20 bước để giải.

Kết quả trên nói rằng, trong 43.252.003.274.489.856.000 (43 tỉ tỉ) vị trí khác nhau của khối Rubik 3x3, bất kì vị trí nào cũng có thể giải trong không quá 20 bước. Kết quả này có được nhờ sự tài trợ máy chủ của Google. Các máy chủ đã giải bài toán này trong thời gian nhàn rỗi (tương tự như dự án [email protected]). Tổng thời gian sử dụng là 35 năm CPU (giải 55 triệu bài toán nhỏ, mỗi bài khoảng 20 giây). Thông tin cụ thể được nhóm tác giả đăng tải tại cube20.org.

Cuộc tìm kiếm con số 20 này khởi đầu từ những năm 1980. Người ta chứng minh được cần tối thiểu 18 bước, vì nếu chỉ dùng 17 bước, tổng số vị trí tạo ra của 17 bước này còn nhỏ hơn số vị trí của Rubik. Cận trên, vào những năm 1980 về trước, vào khoảng 80, dựa vào các thuật toán giải Rubik. Năm 1995, người ta tìm ra vị trí siêu lật (superflip): đúng góc, cạnh lật, cần đến 20 bước. Kể từ đó, cận trên liên tục được giảm dần, và vào tháng trước đã được chứng minh rằng nó bằng với cận dưới: 20 bước.




Bình luận

  • TTCN (9)
Bùi Minh Triết  1003

Có nghĩa là với vị trí bất kì của khối rubik, chỉ cần quay 18 bước là giải ra xong à?

Hải Nam  30904

20 bước. Nhưng không phải dùng các thuật toán trong tờ hướng dẫn kèm theo Rubik đâu.

Mấy bác này lập trình, giải 1 tập hợp (gồm 20 tỉ vị trí) hết khoảng 20 giây, tất nhiên, giải ở đây là mỗi vị trí tìm ra đáp số với không quá 20 bước đi, chứ không cần tìm đáp số tối ưu để khỏi mất thời gian (nghĩa là nếu 1 vị trí có thể giải trong 15 bước, cũng mặc kệ không quan tâm đến lời giải đó, chỉ cần tìm lời giải nào cũng được, miễn là không quá 20 bước).

kivt

rubik

khoi rubik 3x3 mak co den^' 43 ti vi tri khac nhau ak

Tao là ai

Cái trò khỉ bài sai thì có

Nó có tổng là 54 ô. 54 giai thừa = 43 tỉ ( gần đúng hay sao ấy )

Hải Nam  30904

Bạn vào đây để biết vì sao có 43 tỉ tỉ vị trí (chỉ tính các vị trí hợp lí)

samwar99

mọi vị trí của rubik 3x3 vs mọi rubik là khác nhau nhé

Hải Nam  30904

Nói Rubik thì ngầm hiểu là 3x3 (chính xác hơn thì là 3x3x3).

Khách_83453453

nói rubik thì nghĩ ngày đến 3*3 thôi, là laọi rubik thông dụng nhất~

Đinh Trọng Hiền  13

Nó có 6 mặt 9*6=54 ô. Số vị trí không phải là tính bằng 54 gia thừa đâu. Nó đc tính bằng 8!*3^7*((12!*2^11)/2) gần bằng 433*10^17.  54 gia thừa không bằng 49ti đâu ông nội.