KONSTANTA 10⁴⁰ DIPANGKAS MENJADI 30,5 UNTUK KUBUS RUBIK RAKSASA
Kubus Rubik, yang baru saja berusia 50 tahun, mungkin adalah teka-teki paling terkenal di dunia, dan salah satu pertanyaan utamanya mudah dirumuskan: dalam kasus terburuk, berapa langkah yang dibutuhkan untuk menyelesaikannya? Untuk kubus klasik 3×3×3, jawabannya diketahui secara pasti: 20 langkah, hasil yang diterbitkan pada 2014 oleh sebuah tim yang di dalamnya termasuk Tomas Rokicki, salah satu penulis makalah baru ini.
Untuk kubus yang lebih besar, dengan n lapisan di sepanjang setiap rusuk, jawaban pastinya berada di luar jangkauan — menyelesaikan sebuah kubus n×n×n tertentu secara optimal bahkan bersifat NP-lengkap. Namun pada 2011, Erik Demaine dan rekan-rekannya menunjukkan bagaimana kasus terburuk itu tumbuh: sebanding dengan n² / lg n, dengan lg adalah logaritma berbasis 2. Itu lebih baik sebesar satu faktor logaritmik daripada metode standar, yang pada dasarnya menyelesaikan kepingan-kepingan satu per satu.
Bukti dengan konstanta yang absurd
Ada satu kendala. Hasil tahun 2011 itu menjamin laju pertumbuhannya, bukan angka di depannya. Dengan menelusuri algoritma itu, para penulis menemukan bahwa konstantanya sekitar 1,01 × 10⁴⁰. Biang keladinya adalah sebuah pemeriksaan komputer yang membuktikan bahwa langkah-langkah tertentu dapat mencapai setiap susunan dari sekelompok 24 kepingan, tanpa menyebutkan seberapa cepat. Satu-satunya batas yang aman untuk panjang itu adalah ukuran kelompok susunan itu, sekitar 3,1 × 10²³ langkah, dan rumusnya akhirnya menggunakan bilangan raksasa 24! (1 × 2 × … × 24, sekitar 6,2 × 10²³) di dua tempat. Sebaliknya, batas bawahnya — jumlah langkah yang dibutuhkan hampir setiap kubus teracak — memiliki konstanta yang bersahaja, sekitar 12,88. Karena itu, banyak orang di komunitas ini percaya bahwa algoritma semacam itu tidak akan pernah praktis untuk ukuran yang wajar.
Jeremy Mrzyglocki, Tomas Rokicki, Maxine Perroni-Scharf, dan Erik Demaine, dari MIT, TU Munich, dan Palo Alto, kini telah membuat konstanta itu eksplisit dan kecil.
Jaringan pengurutan untuk kepingan kubus
Pada kubus besar, kepingan tengah mendominasi: jumlahnya tumbuh sebanding dengan n², sementara kepingan sudut dan rusuk hanya menambahkan suku yang sebanding dengan n. Kepingan tengah terbagi ke dalam keluarga-keluarga berisi 24 kepingan yang hanya bisa bertukar di antara sesamanya. Alat dasarnya adalah komutator, sebuah urutan berbentuk A B A′ B′ yang membiarkan hampir semuanya tetap di tempat dan hanya mempermutasi tiga kepingan dari satu keluarga. Tim menemukan urutan langkah untuk semua 4.000 pertukaran tiga kepingan yang dapat dipakai, masing-masing paling panjang 12 langkah.
Dua gagasan membuat jumlah langkah turun. Pertama, komutator yang sama dapat diterapkan pada banyak keluarga sekaligus, di seluruh kelompok baris dan kolom. Kedua, alih-alih menyelesaikan setiap keluarga secara terpisah, setiap keluarga mengikuti satu urutan universal pertukaran yang tetap, cukup dengan melewati pertukaran yang tidak dibutuhkannya. Sebuah lema mengikat semuanya: urutan universal dengan L tahap menghasilkan konstanta utama sebesar L/2.
Untuk memperpendek urutan itu, tim meminjam alat dari ilmu komputer, yaitu jaringan pengurutan (sorting networks), pola perbandingan tetap yang mengurutkan masukan apa pun. Sebuah jaringan pengurutan optimal dengan enam masukan menghasilkan 96 tahap, sehingga konstantanya 48. Jaringan yang membagi 24 posisi ke dalam kelompok berisi 12, lalu 4, yang ditemukan melalui pencarian komputer, menurunkannya menjadi 72 tahap (36). Akhirnya, dengan mengizinkan langkah yang mengacak lebih dari tiga kepingan sekaligus dan membagi posisi-posisi itu secara berbeda, jumlahnya turun menjadi 61 tahap.
Tiga puluh koma lima
Teoremanya: kubus n×n×n mana pun dapat diselesaikan dalam paling banyak 30,5 n²/lg n langkah, ditambah suku-suku yang menjadi dapat diabaikan untuk n yang besar. Konstantanya membaik dengan faktor lebih dari 3,30 × 10³⁸, dan berada dalam faktor 2,37 dari batas bawah (30,5 / 12,88). Untuk versi datar n×n×1, yang dipakai sebagai pemanasan, konstantanya turun dari 12 atau 18 menjadi 1,5.

Delapan bingkai berjarak sama dari penyelesaian sebuah kubus dengan 256 lapisan per sisi: sisi-sisi yang teracak berubah menjadi warna-warna polos. — Gambar 1.1, Mrzyglocki dkk. (2026), arXiv:2611.11018.
Algoritma ini berjalan dalam waktu yang sebanding dengan jumlah kepingan, dan para penulis menyediakan pemecah sumber terbuka, beserta skrip yang secara menyeluruh memeriksa setiap jaringan yang diandalkannya. Perbandingan mereka sendiri menunjukkan pemecah itu unggul atas pemecah yang sudah ada mulai dari sekitar n = 840; mereka telah merender penyelesaian kubus dengan 256 dan 65.536 lapisan per sisi.
Angka 2,37 adalah pernyataan asimtotik: suku-suku yang lebih kecil dalam rumus itu belum ditentukan secara pasti, sehingga rumus itu tidak memberikan hitungan tepat untuk kubus tertentu. Kemajuan selanjutnya, menurut para penulis, mungkin datang dari cara lain mengelompokkan kepingan ke dalam jaringan pengurutan dan dari pertukaran tiga kepingan yang lebih baik — dan perangkat yang sama dapat digunakan untuk menggarap teka-teki raksasa lainnya, atau hiperkubus empat dan lima dimensi.
