O cubo mágico resolvido em 20 movimentos ou menos

Gostaria de avisar que essa notícia será um choque terrível para pessoas que, assim como eu, nunca conseguiram resolver um cubo mágico na vida.

Através de um algoritmo de solução de cubo mágico desenvolvido por um grupo de quatro pesquisadores (dois matemáticos, um engenheiro e um programador) qualquer posição do cubo mágico pode ser resolvida em, no máximo, 20 movimentos. No máximo!

Ou seja, não existe nenhuma posição, por mais embaralhada que esteja, que não possa ser resolvida com até 20 movimentos.

Vou repetir! 20 míseros movimentos são o suficiente para resolver QUALQUER embaralhada do cubo mágico! Pronto, podemos sentar e chorar…

Segundo Morley Davidson, John Dethridge, Herbert Kociemba e Tomas Rokicki (os responsáveis por esse feito), existem 43.252.003.274.489.856.000 posições diferentes do cubo mágico, contando com as posições simétricas. (Acho que nem o Tio Patinhas consegue calcular um número desse quilate)

Esses pesquisadores executaram esse algoritmo em uma grande quantidade de computadores do Google (nem eles sabem quantos computadores o Google usou para isso) e resolveram todas as combinações únicas em algumas semanas. No link que eu deixei lá embaixo, eles explicam quantos testes eles precisaram fazer para chegar a essa conclusão.

Ainda segundo eles, se fossem usar uma máquina Intel Quad-Core 2.8GHz (um bom computador) eles levariam o equivalente a 35 anos de processamento ininterrupto (1.1 bilhão de segundos). 😮

A tabela abaixo, mostra que a maioria das posições do cubo mágico só pode ser resolvida por, no mínimo, 18 movimentos. As posições que requerem 20 movimentos para serem resolvidas, são raras, apesar de serem +/- 300 milhões.

Distância Posições
0 1
1 18
2 243
3 3.24
4 43.239
5 574.908
6 7.618.438
7 100.803.036
8 1.332.343.288
9 17.596.479.795
10 232.248.063.316
11 3.063.288.809.012
12 40.374.425.656.248
13 531.653.418.284.628
14 6.989.320.578.825.350
15 91.365.146.187.124.300
16 ~ 1.100.000.000.000.000.000
17 ~ 12.000.000.000.000.000.000
18 ~ 29.000.000.000.000.000.000
19 ~ 1.500.000.000.000.000.000
20 ~ 300.000.000

Mais informações aqui.

Um comentário idiota: Isso mostra que é mais fácil resolver as 43.252.003.274.489.856.000 posições do cubo mágico do que saber quantos computadores o Google usa para resolver o problema…

Comments on this entry are closed.

  • Realmente impressionante. Quando vi isso pela primeira vez fiquei triste por saber que eu nunca consegui arrumar em menos de 40 movimento ;~ (e consegui com 43 uma única vez na vida, aka foi pura sorte =P)

    Apenas uma correção: na realidade, eles não criaram um algoritmo que *resolve* o cubo em no máximo 20 movimentos. Eles tentaram por força bruta todas as possibilidades, limitaram o numero máximo de movimentos e descobriram que é possível resolver *em até* 20 movimentos todas as permutações do cubo. Pode ser que esses 300kk diminuam, já que ainda podemos encontrar um número menor de movimentos para resolver tais casos. Eles não exploraram todos os caminhos, mas sim os que chegassem a uma solução em até 20 movimentos.

    Mas com esse último resultado, eu duvido que o número de Deus deva diminuir mais que isso. Só me pergunto quantas posições diferentes podem ser resolvidas com no mínimo 19 e 20 movimentos.

  • Ricardo, eles melhoraram o algoritmo sim, o resultado anterior, que era de 22 movimentos, também foi forçado por supercomputadores, da mesma forma. E o que você duvida, realmente procede, porque em 1995 foi provado que uma das combinações do cubo necessita de no mínimo 20 movimentos (a combinação onde os meios estão todos invertidos).

    E para nós, reles mortais, o jeito é aprender o método básico mesmo. Quem tiver interesse em aprender a resolver o cubo, é só acessar: http://www.cubomagicobrasil.com

    Não vou dizer que é super fácil, mas com um pouco de paciência qualquer um pode aprender a resolver.

  • Agora fiquei realmente feliz.

    Acabo de descobrir que NÃO sou um alienígena e que outras pessoas também jamais conseguiram resolver o cubo.

  • rafael mitidiero

    ai mo lokao nunca tentei fase pelo metodo de menor movimento ja monto o cubo pelo metodo basico e to começando o avançado hehe minha amedia ta em 50s se montase em 20 movimento caia pra menos de 10

  • Marco Aurélio Dantas

    Uma vez eu consegui em 22 movimentos. Podem olhar no Fórum Cubo Mágico Brasil o usuário com o nome “Lelo”, que sou eu. Na assinatura tem os meus recordes, o recorde está escrito: “Fewest Moves: 22 moves”