Matemáticos provam que o cubo mágico pode ser resolvido em 20 movimentos - Engenharia é

[Rafaela 2.029]

Matemáticos provam que qualquer combinação no cubo-mágico pode ser resolvida em apenas 20 movimentos

Quem nunca brincou com um cubo mágico e tentou resolver a simetria dele, colocando todas as cores nos devidos lugares? O engraçado é que a maioria das pessoas, já mexeram em um cubo mágico quando crianças ou adultos, tentando resolver os encaixes coloridos do cubo mágico.

Diversos estudos foram e vem sendo feitos em cima do cubo mágico, na maioria das vezes por matemáticos. O objetivo é um só, conseguir solucionar o cubo mágico no menor número de movimentos possíveis.

Tudo bem que existem alguns gênios que conseguem solucionar o cubo mágico em apenas poucos segundos — e até com os olhos fechados! —, contudo, a verdade é que a maioria de nós precisa quebrar a cabeça para deixar todos os lados com as mesmas cores e, geralmente, usando mais de 40 movimentos para isso. Afinal, são 43.252.003.274.489.856.000 de combinações possíveis!

Com a ajuda de supercomputadores do Google, matemáticos provam que qualquer combinação no cubo-mágico pode ser resolvida em apenas 20 movimentos.

Processando todas as 43.252.003.274.489.856.000 de configurações possíveis, Morley Davidson, da Kent State University, John Dethridge, engenheiro do Google, Herbert Kociemba, professor de matemática da Alemanha, e Tomas Rokicki, programador da Califórnia, descobriram o número máximo para solucioná-las.

Esse chamado “número de Deus” já havia sido proposto, porém nenhum grupo havia conseguido provar que todas as possibilidades do objeto poderiam ser resolvidas com duas dezenas ou menos de movimentos. Na verdade, apenas cerca de 300 milhões de possibilidades precisam de 20 movimentos. A maioria requer entre 15 e 19. (veja na tabela)

O Google não revela os detalhes de suas super máquinas utilizadas, mas os pesquisadores fazem uma comparação em seu site: com um bom PC (como o Intel Nehalem, de quatro núcleos com freqüência de 2,8 GHz), seriam necessário 1,1 bilhão de segundos, ou cerca de 35 anos, para fazer esses cálculos.

Otimização

A “solução otimizada” tem uma definição bem óbvia: é aquela que não requer mais movimentos do que o necessário. Parece óbvio, mas não é simples realizar, ou calcular, o mínimo de movimentos possíveis. Ao invés de resolver de forma otimizada todos os problemas, os pesquisadores programaram seus algoritmos para buscar soluções que precisavam de 20 ou menos movimentos.

Dessa forma, pela primeira vez, um grupo conseguiu provar que todas as combinações do cubo mágico pode ser resolvidas em, no máximo, 20 etapas. Agora, os quatro colegas aguardam que uma equipe independente confirme seus resultados.

Todo esse estudo pode ser acompanhado através do site Cube 20. onde você ainda pode tentar solucionar um cubo. Deixe-nos saber nos comentários o que achou.

Fonte: http://www.engenhariae.com.br/curiosidades/matematicos-provam-que-qualquer-combinacao-no-cubo-magico-pode-ser-resolvida-em-apenas-20-movimentos/

Editado Outubro 28, 2013 por Rafaela

[Felipe Rigon 881]

De quando é essa notícia...?

Na última vez que li sobre o Algoritmo de Deus, o número máximo de movimentos necessários para solucionar qualquer estado do cubo já havia sido reduzido para 19!

Ou minha memória está a me pregar uma peça?!

[Rafaela 2.029]

De quando é essa notícia...?

Na última vez que li sobre o Algoritmo de Deus, o número máximo de movimentos necessários para solucionar qualquer estado do cubo já havia sido reduzido para 19!

Ou minha memória está a me pregar uma peça?!

Pelos comentários da notícia, ela saiu pelo dia 25 de outubro de 2013 mesmo.

Acho que a sua memória está a pregar uma peça. ushahusauh

Não lembro de ter visto notícia relacionada a essa redução.

[Felipe Rigon 881]

A notícia é antiga: http://info.abril.com.br/noticias/ciencia/20-passos-resolvem-qualquer-cubo-magico-13082010-17.shl?p=2

Eu lembro de ter lido sobre isso há muito tempo!

Minha memória não costuma me pregar peças, mas dessa vez foi, de fato: a notícia era que o número é definitivamente 20, embora a maioria dos estados pode ser solucionado com até 19 movimentos.

O número de Deus é assunto recorrente no fórum: http://forum.cubomagicobrasil.com/topic/103-artigo-cubo-de-rubik/

(Olha, posts meus de cinco anos atrás!)

Edit: Agora que notei, você tirou sarro do jeito que escrevi "está a pregar uma peça"? hahahahaha

Editado Outubro 28, 2013 por Felipe Rigon

[Rafaela 2.029]

A notícia é antiga: http://info.abril.com.br/noticias/ciencia/20-passos-resolvem-qualquer-cubo-magico-13082010-17.shl?p=2

Eu lembro de ter lido sobre isso há muito tempo!

Minha memória não costuma me pregar peças, mas dessa vez foi, de fato: a notícia era que o número é definitivamente 20, embora a maioria dos estados pode ser solucionado com até 19 movimentos.

O número de Deus é assunto recorrente no fórum: http://forum.cubomagicobrasil.com/topic/103-artigo-cubo-de-rubik/

(Olha, posts meus de cinco anos atrás!)

Edit: Agora que notei, você tirou sarro do jeito que escrevi "está a pregar uma peça"? hahahahaha

Sobre a notícia antiga, eles só usaram a otimização e a tabela, eu acho,

Dei uma olhada no tópico, mas não tem mais novas notícias sobre o assunto, nem sobre mais uma redução. F. Rigon, tu tens mais informações sobre isso?

Não tirei sarro. ^-^

[Hypercuber 18]

wow só 20 movimentos? caramba

[Murillo Otero 962]

Agora eu quero ver alguém decorar e executar todos os 43 quintilhões de possibilidades... hahahaha

[Felipe Rigon 881]

Sobre a notícia antiga, eles só usaram a otimização e a tabela, eu acho,

Dei uma olhada no tópico, mas não tem mais novas notícias sobre o assunto, nem sobre mais uma redução. F. Rigon, tu tens mais informações sobre isso?

Não tirei sarro. ^-^

Ora, mas se usaram a tabela da pesquisa antiga, a notícia é antiga, não?! hahahaha

É, o tópico é dos primórdios do fórum; não pesquiso sobre o Número de Deus desde aquela época!

E obrigado por não tirar sarro de minha pessoa.

hahahahaha

[Rafaela 2.029]

Ora, mas se usaram a tabela da pesquisa antiga, a notícia é antiga, não?! hahahaha

É, o tópico é dos primórdios do fórum; não pesquiso sobre o Número de Deus desde aquela época!

E obrigado por não tirar sarro de minha pessoa.

hahahahaha

uhsauhashuas

Volte a pesquisar sobre

[Felipe Rigon 881]

uhsauhashuas

Volte a pesquisar sobre

De acordo com a primeira página do google, o número de Deus é realmente 20. Ali tem algo sobre ser "definitivamente 20". Depois pesquiso mais a fundo. hahaha

E outra: posso não saber qual é o número de Deus, mas sei que a resposta da questão fundamental da vida, o universo e tudo o mais, é, de fato, 42.

[Rafaela 2.029]

De acordo com a primeira página do google, o número de Deus é realmente 20. Ali tem algo sobre ser "definitivamente 20". Depois pesquiso mais a fundo. hahaha

E outra: posso não saber qual é o número de Deus, mas sei que a resposta da questão fundamental da vida, o universo e tudo o mais, é, de fato, 42.

husauhasuhashua

Viciado no Guia do Mochileiro das Galáxias e.e

[Felipe Rigon 881]

husauhasuhashua

Viciado no Guia do Mochileiro das Galáxias e.e

Às evidências sugerem que você também aprecia as desventuras de Arthur Dent.

Talvez. Ou não.

Mas não é preciso um post meu para perceber meu gosto! hahahahaha

[Newbie 1.201]

Testei aqui e o resultado para 15 movimentos é, na verdade, 91.365.146.187.124.311 e não 91.365.146.187.124.313; alguém aí confirma ?

[Cinoto 678]

Parece que você tá certo Newbie, pra mim deu a mesma coisa, vamos escrever pra eles?

[Murillo Otero 962]

Poxa eu testei aqui e deu 91.365.146.187.124.315...

[Rafaela 2.029]

"Descoberta Impressionante sobre o Cubo Mágico:

[26 movimentos em QTM] - http://www.cube20.org/qtm

Em 2010, um grupo de programadores e pesquisadores, utilizando um supercomputador da Google, descobriu que para qualquer embaralhamento de um cubo mágico, seria necessário no máximo 20 movimentos (o chamado God's Number, ou Algoritmo de Deus) para ser resolvido, incluindo giros duplos. Foi uma descoberta histórica na época, pois o cubo possui 43.252.003.274.489.856.000 combinações e seria impossível provar esta descoberta sem um supercomputador.

Uma das ~500 milhões de combinações que geram 20 movimentos é o Superflip, cujo algoritmo é:

R L U2 F U' D F2 R2 B2 L U2 F' B' U R2 D F2 U R2 U

Mas a pesquisa não acabou por aí. Recentemente, no dia 3 de Agosto, foi anunciado que descobriram também o número máximo de movimentos de 90 graus (quarter-turn metric, ou quartos de volta) para se resolver o cubo 3x3x3, que é de 26 movimentos.

Mas o mais fascinante é saber que, ao invés de milhões de casos, provavelmente existem apenas 3 scrambles simétricos que necessitam de 26 movimentos com quartos de volta para se resolverem, dentre todas as 43 quintilhões de permutações!

São novamente os chamados Superflips, mas com 4 centros opostos:

[x] U U F U U R' L F F U F' B' R L U U R U D' R L' D R' L' D D

[y] U U F U U R' L F F U F' B' R L U U R U D' R L' D R' L' D D

[z] U U F U U R' L F F U F' B' R L U U R U D' R L' D R' L' D D

Acho que não vão encontrar outros possíveis, então essa "beleza matemática" e perfeita do cubo mágico será preservada!"

- Por Fábio Bini

[Daniel Lehwing 800]

E outra: posso não saber qual é o número de Deus, mas sei que a resposta da questão fundamental da vida, o universo e tudo o mais, é, de fato, 42.

Pessoal, prestem atenção nesta pessoa... ele sabe do que diz!!

DON'T PANIC

Editado Junho 6, 2015 por Daniel Lehwing

[Felipe Rigon 881]

Pessoal, prestem atenção nesta pessoa... ele sabe do que diz!!

DON'T PANIC

Eu sei aonde está minha toalha. Hahahaha

[Allyson Dias 359]

Eu acho que a maioria dos casos necessitam de 18, e não 19. Vi uma vez uma contagem de quantas combinações tinha por número de movimentos para resolver, mas não lembro onde vi.

[Rafaela 2.029]

Eu acho que a maioria dos casos necessitam de 18, e não 19. Vi uma vez uma contagem de quantas combinações tinha por número de movimentos para resolver, mas não lembro onde vi.

Esse site tem bastante informação sobre o Número de Deus:

http://www.cube20.org/