UMA CONSTANTE DE 10⁴⁰ REDUZIDA A 30,5 PARA CUBOS DE RUBIK GIGANTES
O cubo de Rubik, que acaba de completar 50 anos, é talvez o quebra-cabeça mais conhecido do mundo, e uma de suas questões centrais é simples de enunciar: no pior caso, quantos movimentos são necessários para resolvê-lo? Para o cubo clássico 3×3×3, a resposta é conhecida exatamente: 20 movimentos, um resultado publicado em 2014 por uma equipe que incluía Tomas Rokicki, um dos autores deste novo artigo.
Para cubos maiores, com n camadas ao longo de cada aresta, a resposta exata está fora de alcance — resolver de forma ótima um dado cubo n×n×n é até NP-completo. Mas em 2011 Erik Demaine e colegas mostraram como o pior caso cresce: proporcionalmente a n² / lg n, onde lg é o logaritmo na base 2. Isso é um fator logarítmico melhor que os métodos padrão, que resolvem as peças essencialmente uma de cada vez.
Uma prova com uma constante absurda
Havia um porém. O resultado de 2011 garantia a taxa de crescimento, não o número que a multiplica. Destrinchando esse algoritmo, os autores constatam que sua constante é de cerca de 1,01 × 10⁴⁰. O culpado é uma verificação por computador que provou que certos movimentos podiam alcançar todos os arranjos de um grupo de 24 peças, sem dizer com que rapidez. O único limite seguro para esse comprimento era o tamanho desse grupo de arranjos, cerca de 3,1 × 10²³ passos, e a fórmula acaba usando o número enorme 24! (1 × 2 × … × 24, cerca de 6,2 × 10²³) em dois lugares. Em contraste, o limite inferior — o número de movimentos de que quase todo cubo embaralhado precisa — tem uma constante modesta, de cerca de 12,88. Por isso, muitos na comunidade acreditavam que um algoritmo desse tipo nunca poderia ser prático para tamanhos razoáveis.
Jeremy Mrzyglocki, Tomas Rokicki, Maxine Perroni-Scharf e Erik Demaine, do MIT, da TU de Munique e de Palo Alto, agora tornaram essa constante explícita e pequena.
Redes de ordenação para peças de cubo
Num cubo grande, as peças centrais dominam: seu número cresce como n², enquanto cantos e arestas só acrescentam termos proporcionais a n. As peças centrais se dividem em famílias de 24 que só podem trocar de lugar entre si. A ferramenta básica é o comutador, uma sequência da forma A B A′ B′ que deixa quase tudo no lugar e permuta apenas três peças de uma família. A equipe encontrou sequências de movimentos para todas as 4.000 trocas utilizáveis de três peças, cada uma com no máximo 12 movimentos.
Duas ideias fazem a contagem cair. Primeiro, o mesmo comutador pode ser aplicado a muitas famílias de uma vez, através de grupos inteiros de linhas e colunas. Segundo, em vez de resolver cada família separadamente, todas as famílias seguem uma mesma sequência universal fixa de trocas, simplesmente pulando as de que não precisam. Um lema amarra tudo: uma sequência universal de L etapas dá uma constante principal de L/2.
Encurtar essa sequência exige emprestar ferramentas das redes de ordenação da ciência da computação, padrões fixos de comparações que ordenam qualquer entrada. Uma rede de ordenação ótima de seis entradas dá 96 etapas, e portanto uma constante de 48. Redes que dividem as 24 posições em grupos de 12, depois de 4, encontradas por busca computacional, levam a 72 etapas (36). Por fim, permitir movimentos que embaralham mais de três peças de uma vez e dividir as posições de outra forma leva a 61 etapas.
Trinta vírgula cinco
O teorema: qualquer cubo n×n×n pode ser resolvido em no máximo 30,5 n²/lg n movimentos, mais termos que se tornam desprezíveis para n grande. A constante melhora por um fator de mais de 3,30 × 10³⁸ e fica a um fator de 2,37 do limite inferior (30,5 / 12,88). Para a versão plana n×n×1, usada como aquecimento, a constante cai de 12 ou 18 para 1,5.

Oito quadros igualmente espaçados da resolução de um cubo com 256 camadas por lado: as faces embaralhadas se transformam em cores sólidas. — Figura 1.1, Mrzyglocki et al. (2026), arXiv:2611.11018.
O algoritmo roda em tempo proporcional ao número de peças, e os autores disponibilizam um solucionador de código aberto, com scripts que verificam exaustivamente cada rede da qual ele depende. Na comparação feita por eles próprios, ele passa à frente dos solucionadores existentes a partir de cerca de n = 840; eles renderizaram resoluções de cubos com 256 e 65.536 camadas por lado.
O 2,37 é uma afirmação assintótica: os termos menores da fórmula não estão determinados com precisão, então ela não dá uma contagem exata para um cubo específico. Ganhos futuros, sugerem os autores, podem vir de outras formas de agrupar peças em redes de ordenação e de trocas de três peças melhores — e a mesma maquinaria poderia enfrentar outros quebra-cabeças gigantes, ou hipercubos de quatro e cinco dimensões.
