Cubo

Há um tempo eu queria entender melhor a matemática por trás do cubo mágico, então fiz um projeto que basicamente roda em loop infinito: um cubo embaralhado fazendo movimentos aleatórios até que, em algum momento, ele volte ao estado resolvido. A premissa é o teorema do macaco infinito clássico: dado tempo suficiente, qualquer evento improvável acontece.

Coloquei o iframe rodando aqui no blog também. Você pode deixar aberto numa aba e voltar daqui a uns... bilhões de anos pra ver se deu certo.

A parte engraçada é que, pra qualquer pessoa que olhe o cubo de longe, parece que "deve resolver em algum momento, né?". Afinal, são só 6 faces, 9 quadradinhos cada. Quão difícil pode ser?

A resposta envolve teoria de grafos, geração de números pseudo-aleatórios, o tempo de vida do universo e um número que, sinceramente, eu não consigo nem visualizar direito.

Imagem 1 (hero, Gemini-gerada): Um macaco em frente a uma máquina de escrever, mas no lugar do papel há um cubo mágico que ele está girando. Atmosfera de "experimento mental" com livros e cubos embaralhados ao redor.

O número que ninguém consegue visualizar

O cubo de 3x3x3 tem 43.252.003.274.489.856.000 estados possíveis. Se você quiser sentir esse número, é mais ou menos isso:

• 43 quintilhões.

• 6 mil vezes a quantidade estimada de grãos de areia em todas as praias da Terra.

• Se cada estado fosse um milissegundo, você precisaria de 1.4 bilhão de anos pra contar todos.

A fórmula que dá esse número é (8! × 3⁷) × (12! × 2¹¹) / 2. Os dois primeiros termos são as permutações e orientações dos cantos, os dois seguintes são das arestas, e a divisão por 2 é porque metade das configurações é fisicamente inalcançável (você não consegue chegar nelas só girando, precisaria desmontar o cubo).

Esses 43 quintilhões são o tamanho do espaço de estados do cubo. E é aí que a brincadeira do random walk começa a ficar perversa.

A primeira ironia: algoritmos sempre voltam pra casa

Antes de falar do random walk, vale entender uma coisa que parece óbvia mas não é: todo algoritmo de cubo, repetido infinitamente, eventualmente volta ao estado inicial.

Pega o famoso "sexy move", o R U R' U' que todo mundo que aprende a resolver cubo decora primeiro. Repete ele 6 vezes e o cubo volta exatamente como começou. A "ordem" desse algoritmo é 6.

Outros exemplos clássicos:

• T-Perm (R U R' U' R' F R2 U' R' U' R U R' F'): ordem 2. Aplica duas vezes e volta.

• Sune (R U R' U R U2 R'): ordem 6.

• Y-Perm: ordem 2.

Até a sequência mais simples possível, R U (apenas dois movimentos), tem ordem 105. Repita R U cento e cinco vezes seguidas e o cubo volta ao estado original. Isso é contraintuitivo, mas é uma propriedade inevitável de qualquer grupo finito: toda sequência de operações tem uma ordem finita.

Imagem 2 (Excalidraw): Um diagrama circular tipo "relógio" com 6 nós, cada um representando o estado do cubo após cada iteração do R U R' U'. O nó superior é o estado inicial, e as setas formam um ciclo fechado. Anotação: "Ordem 6: depois de 6 iterações, volta ao estado original".

A intuição aqui é simples: o cubo é um grupo finito. O conjunto de todos os estados possíveis é fechado. Se você fica aplicando uma mesma transformação, eventualmente vai cair em um estado que já visitou, e a partir daí tudo se repete. Isso é o teorema de Lagrange aplicado a um brinquedo.

E é nessa linha de raciocínio que muita gente comete o erro de pensar: "ah, então um random walk também vai voltar pro estado resolvido em algum momento". Vai, sim. O problema é o "em algum momento".

O cubo é um grafo (e isso muda tudo)

Aqui o post fica interessante pra quem programa.

Imagine o cubo não como um objeto físico, mas como uma estrutura de dados. Cada estado possível é um vértice num grafo. Cada movimento é uma aresta que liga um estado a outro. Esse grafo tem nome: Grafo de Cayley do grupo do cubo.

Vamos contar:

• Vértices: 43.252.003.274.489.856.000 (os estados).

• Arestas por vértice: 18 (são 6 faces, e cada face permite 3 movimentos: 90°, 180°, 270°).

• Total de arestas: ~3.9 × 10²⁰.

Imagem 3 (Excalidraw): Visualização simplificada do Grafo de Cayley. Uns 12-15 nós representando estados do cubo (alguns com mini-ilustrações do cubo em cores diferentes), conectados por arestas rotuladas com movimentos como "R", "U", "F". Um nó central destacado em verde representando o estado resolvido. Anotação no canto: "43.252.003.274.489.856.000 vértices · grau 18".

Isso muda completamente o problema. Agora resolver o cubo deixa de ser uma questão de "girar até funcionar" e vira um problema clássico de busca em grafo: achar o caminho mais curto do vértice atual até o vértice resolvido.

A palavra-chave aqui é "mais curto", e é onde a coisa fica absurda.

O Número de Deus

Em 2010, depois de 35 CPU-anos rodando em servidores doados pela Google, um time de matemáticos provou um resultado que tinha décadas em aberto: o diâmetro do Grafo de Cayley do cubo é 20.

Em português: a partir de qualquer um dos 43 quintilhões de estados possíveis, existe uma sequência de no máximo 20 movimentos que resolve o cubo. Esse número 20 é o que ficou conhecido como God's Number ou Número de Deus, porque é a quantidade mínima de movimentos que uma entidade onisciente precisaria para resolver qualquer cubo.

Não importa o quão embaralhado esteja seu cubo. Não importa se você passou 3 horas embaralhando ele com força. A solução ótima nunca está a mais de 20 movimentos.

Imagem 4 (Excalidraw): Diagrama de "camadas concêntricas". No centro, um cubo resolvido (verde). Em volta, anéis numerados de 1 a 20 com a contagem aproximada de estados em cada distância. O anel mais externo (20) com anotação: "490.000.000 estados · diâmetro do grafo". Anotação geral: "Qualquer estado está a ≤20 movimentos da solução".

E aqui mora a primeira ironia cruel: enquanto a solução ótima sempre está a no máximo 20 movimentos, o random walk não está nem aí pra isso. Ele vai pegar caminhos de centenas, milhares, milhões de movimentos, contornando a solução várias vezes sem nunca cair nela por acaso.

Achar esse caminho mínimo de 20 passos é outro problema. BFS tradicional precisaria carregar boa parte do espaço de estados na memória, o que é inviável (43 quintilhões × ~20 bytes por estado = ~900 exabytes). É por isso que solvers modernos como o algoritmo do Kociemba usam tabelas pré-computadas (pattern databases) e busca heurística com IDA*. Mas isso é assunto pra outro post.

A matemática do passeio aleatório

Vamos pro coração do post: por que o random walk é tão ruim?

Existe uma fórmula clássica em teoria de grafos para o tempo de retorno esperado de um passeio aleatório num grafo conexo não-direcionado. Para retornar a um vértice v:

E[tempo de retorno a v] = 2|E| / d(v)

Onde |E| é o número de arestas e d(v) é o grau do vértice. Pro nosso cubo:

E[retorno ao resolvido] = 2 × (3.9 × 10²⁰) / 18 ≈ 4.3 × 10¹⁹ movimentos

Ou seja, na média, um random walk leva cerca de 43 quintilhões de movimentos pra voltar ao estado resolvido. Que é, não por coincidência, o mesmo número de estados do cubo. Isso acontece porque o grafo é regular (todo vértice tem grau 18), então o passeio aleatório fica uniformemente distribuído entre todos os estados a longo prazo.

Vamos converter isso em tempo:

O universo tem ~13.8 bilhões de anos. Se você rodasse o random walk a 100 movimentos por segundo desde o Big Bang, provavelmente ele já teria resolvido. Provavelmente. Não tem garantia, porque essa é a esperança matemática, não um limite superior.

Imagem 5 (Excalidraw): Dois caminhos sobrepostos no mesmo grafo abstrato. Caminho 1 (vermelho, fino): linha caótica que dá voltas, cruza sobre si mesma várias vezes, passa por dezenas de nós - rotulado "Random Walk: ~10¹⁹ movimentos". Caminho 2 (verde, grosso): linha direta com 20 segmentos do início à solução - rotulado "Caminho ótimo: 20 movimentos". Anotação: "Mesmo grafo. Mesma origem. Mesmo destino."

Essa é a essência da segunda ironia: a solução está sempre a 20 passos de distância, mas o random walk passa pertinho dela trilhões de vezes sem cair nela.

A armadilha da pseudo-aleatoriedade

OK, mas tudo isso assume que o "aleatório" do nosso script é... aleatório. E aqui entra a parte que importa pra quem programa.

Computadores são máquinas determinísticas. Eles não sabem ser aleatórios. O que chamamos de random() em qualquer linguagem moderna é, na verdade, um PRNG (Pseudo-Random Number Generator): um algoritmo que produz sequências que parecem aleatórias, mas são totalmente previsíveis se você souber o estado interno.

O Math.random() do JavaScript no V8 (Chrome, Node) usa atualmente o xorshift128+, que tem período de 2¹²⁸ - 1, ou seja, ~3.4 × 10³⁸. Isso é muito maior que os 4.3 × 10¹⁹ estados do cubo, então em teoria ele consegue produzir sequências longas o suficiente pra cobrir o espaço de estados.

// O loop do meu projeto, simplificado:
const moves = ["R", "R'", "U", "U'", "F", "F'", 
               "L", "L'", "D", "D'", "B", "B'", 
               "R2", "U2", "F2", "L2", "D2", "B2"];

while (!cube.isSolved()) {
  const move = moves[Math.floor(Math.random() * moves.length)];
  cube.apply(move);
}

Mas calma. Tem três armadilhas escondidas aqui que mudam o jogo:

1. O seed predetermina tudo.

Um PRNG é uma função f(estado) → (próximo número, próximo estado). Se você fixa o seed inicial, a sequência inteira de "movimentos aleatórios" do seu cubo está totalmente predeterminada. Não tem aleatoriedade real. Tem uma sequência fixa que alguém com o seed conseguiria reproduzir movimento por movimento.

Em segurança isso é um problema sério (por isso existem PRNGs criptográficos como crypto.getRandomValues()). Pro cubo é só uma curiosidade filosófica: o macaco infinito do meu projeto não está realmente "tentando", está executando um caminho fixo no grafo.

2. Nem todo PRNG tem período suficiente.

O xorshift128+ é decente. Mas se você fosse implementar isso em C usando o rand() da libc (que ainda é um Linear Congruential Generator), o período típico é de apenas 2³¹ - 1, ou seja, ~2 bilhões. Isso é 20 bilhões de vezes menor que o espaço de estados do cubo.

Resultado: o seu programa em C nunca conseguiria visitar a maior parte dos estados. Ele entraria num ciclo determinístico de no máximo 2 bilhões de configurações, e se a solução não estivesse nesse ciclo, o programa rodaria pra sempre, literalmente.

Imagem 6 (Excalidraw): Dois círculos lado a lado. Círculo 1 (esquerda, pequeno e vermelho): "LCG / rand() · período 2³¹" - mostrando uma trajetória que circula em uma região pequena do espaço de estados, com alguns estados destacados como "nunca alcançados". Círculo 2 (direita, grande e azul): "xorshift128+ · período 2¹²⁸" - cobrindo todo o espaço uniformemente. Anotação central: "Espaço de estados do cubo: 2⁶⁵".

3. Aleatoriedade ≠ uniformidade.

Mesmo com um PRNG de período enorme, você não tem garantia de distribuição uniforme entre os 43 quintilhões de estados. PRNGs como o xorshift são bons, mas falham em testes estatísticos avançados (BigCrush, PractRand). Pro cubo isso significa que alguns estados podem ser visitados mais que outros, o que enviesa o tempo de cobertura na prática.

E tem um detalhe que poucos lembram: o conceito de "random walk" assume independência entre cada movimento. Mas o grupo do cubo tem relações entre os geradores (R · R' = identidade, R² · R² = identidade, etc). Um random walk ingênuo desperdiça uma porcentagem considerável de movimentos com inversões redundantes. Se você implementar um random walk inteligente que evita aplicar R logo depois de R', você reduz o espaço efetivo de movimentos de 18 pra cerca de 15, mas ainda assim continua sem chegar nem perto do que um BFS faz.

O que isso tudo significa

A meta do projeto era visualizar o teorema do macaco infinito. Mas o que ele realmente mostra, na prática, são três coisas:

A primeira é o tamanho absurdo do espaço de estados do cubo. 43 quintilhões parece um número grande, mas só faz sentido quando você compara com a velocidade de um computador moderno e percebe que mesmo iterando bilhões de vezes por segundo você ainda precisa de séculos.

A segunda é a diferença entre algoritmo estruturado e força bruta. O Kociemba resolve qualquer cubo em milissegundos. O random walk resolveria em bilhões de anos. A diferença não é hardware, é estrutura matemática. Quando você conhece o problema, você ataca o grafo com IDA* e pattern databases. Quando você não conhece, você espera o universo morrer.

A terceira, e essa é a que mais me interessa como dev, é que aleatoriedade em computação é uma ficção útil. A gente programa como se Math.random() fosse aleatório de verdade, mas ele é só uma sequência determinística que parece aleatória pra olhos humanos. Em problemas pequenos isso não importa. Em problemas do tamanho do cubo mágico, isso encosta no limite teórico do que computação determinística consegue fazer.

Imagem 7 (Gemini ou Excalidraw): Visualização de escala. À esquerda, um cubo com 20 setas de movimento numeradas (1-20). À direita, um borrão/nuvem caótica de setas representando 10¹⁹ movimentos, com anotação "tantas setas que não cabem na imagem". Texto sobreposto: "20 vs 10.000.000.000.000.000.000".

Considerações finais

O macaco infinito provavelmente nunca vai resolver seu cubo mágico. A matemática diz que ele vai, em média, depois de tempo suficiente pra extinguir várias civilizações. A computação prática diz que ele provavelmente vai entrar em algum ciclo determinístico do PRNG e ficar girando ali pra sempre.

Mas o macaco continua tentando. E tem algo poético nisso: um processo que é matematicamente garantido de funcionar, mas computacionalmente impossível de testar.

Se quiser deixar o seu próprio macaco rodando enquanto faz outra coisa, é só abrir o iframe abaixo (ou acessar https://live.junyo.dev/rubikcube/ direto). Eu deixei rodando aqui no meu monitor de plantão por uns dias enquanto escrevia esse post. O cubo não foi resolvido. Mas eu acho que ele já deve estar perto.

Aliás, se você quiser saber a probabilidade exata de o cubo estar resolvido depois de N movimentos: é aproximadamente N/(4.3 × 10¹⁹). Depois de um milhão de movimentos, a chance é de cerca de 0.0000000000023%. Boa sorte.