Inteligência matemática

Cubo de Rubik, quebra-cabeça 3D criado pelo húngaro Erdõs Rubik em 1974, pode ser resolvido com até 20 movimentos

É possível resolver o “Cubo de Rubik” – quebra-cabeça 3D, criado em 1974 pelo húngaro Ernõ Rubik – em até 20 movimentos, a partir de qualquer arranjo inicial. O feito foi realizado pela combinação do poder dos computadores usados pelo Google com alguns insights matemáticos, o que permitiu checar todas as 43 quintilhões de possíveis posições que o cubo possa assumir.

“O grande avanço foi descobrir um meio de resolver tantas posições, todas de uma vez, a uma grande velocidade”. Tomas Rokicki, programador de Palo Alto, Califórnia, passou os últimos 15 anos, procurando pelo número mínimo de movimentos necessários para resolver qualquer configuração do Cubo de Rubik.

Para alcançar esse objetivo, Rokicki e colaboradores usaram técnicas de um ramo da matemática chamado teoria de grupos: dividiram todas as possíveis configurações iniciais em 2,2 bilhões de conjuntos, cada um contendo 19,5 bilhões de configurações (2,2 bilhões x 19,5 bilhões = 42,9 quintilhões).

O critério da divisão foi a maneira como essas configurações corespondiam a um grupo de 10 movimentos possíveis. Esse agrupamento permitiu que a equipe reduzisse o número de conjuntos para 56 milhões de simetrias. Por exemplo, virar o cubo de cima para baixo não torna o problema mais difícil; então, essas posições equivalentes podem ser ignoradas. Mas isso ainda deixa um vasto número de configurações iniciais para ser checadas, o que não seria viável sem um algoritmo para dar velocidade ao processo. Algorritmo é um conjunto de regras para solução de determinado problema).

Uma maneira de entender o algoritmo é supor que a tarefa fosse visitar um amigo em uma cidade desconhecida e que você teria recebido instruções para virar à esquerda ou à direita, mas que as instruções não tinham incluído a posição inicial. Se você seguir as instruções, a partir de uma posição inicial qualquer, é improvável que chegue a seu destino. Mas, pareando os movimentos direita-esquerda à posição inicial correta, você chegara ao destino.

Métodos anteriores resolviam cerca de 4.000 cubos por segundo, tentando um conjunto de posições iniciais e determinando se a posição resultante o aproximava da solução. Se não o fizesse, o algoritmo se desfazia desses movimentos e começava de novo. O insight de Rokicki foi notar que esses becos sem saída são, na realidade, soluções para um cubo com uma posição inicial diferente. Isso o levou a um algoritmo que conseguia tentar um bilhão de simetrias de cubos, por segundo. As pesquisas chegaram à resolução de um conjunto de 19,5 bilhões de configurações em 20 segundos. Entretanto, mesmo nessa velocidade, levaria 35 anos para completar toda a tarefa em um computador pessoal.

Aí, entrou em cena o engenheiro John Dethridge (Google, em Mountain View, Califórnia) com os supercomputadores da empresa e o problema resolveu-se em poucas semanas. Havia a teoria, mas não o hardware. Sabia-se que algumas configurações iniciais requeriam apenas 20 movimentos para serem resolvidas, e alguns matemáticos suspeitavam que nenhuma configuração exigiria mais do que isso.

“Pesquisa desse tipo mostra como matemática pura pode ser usada para transformar problemas computacionais difíceis em problemas mais tratáveis (...) O Cubo de Rubik é um caso interessante para os métodos de teoria de grupos computacional.” (Mark Kambites, matemático da Universidade de Manchester).

 

Veja algumas dicas interessantes para resolver o cubo, nesta pequeno curso.

Ou Vc. pode acessar este site que ensina todos os passos de Como Resolver o Cubo de Rubik – tradução da página How to Solve The Rubik's Cube, criada por Mark Jeays: duas soluções completas para resolver o cubo a partir de qualquer posição válida. Para iniciantes.