Cientistas estão a oferecer um prémio de um milhão de dólares a quem conseguir resolver uma variação de um problema matemático extremamente complicado conhecido como “Enigma da Rainha” ou “Problema das Oito Rainhas”.
A beleza do desafio está no facto de não ser preciso saber jogar xadrez para participar. No entanto, é certo que isso também não vai facilitar – nem um pouquinho – as coisas. Na verdade, os cientistas dizem que a solução é tão matematicamente complexa que descobri-la pode demorar milhares de anos.
O “Enigma da Rainha” (ou “Problema das Oito Rainhas”) foi originalmente criado em 1848. O desafio é colocar oito rainhas num tabuleiro de xadrez de 8×8, de modo que nenhuma rainha ameace directamente a outra.
A rainha é a peça mais poderosa do tabuleiro, podendo mover-se em todas as direcções – para cima e para baixo, para ambos os lados e diagonalmente para todos os lados. Além disso, em qualquer destas direcções pode mover-se a qualquer distância no tabuleiro.
Esta liberdade de movimento é a razão pela qual o enigma é tão interessante, embora não seja assim tão assim difícil de resolver. Na verdade, há 92 formas diferentes de o solucionar, “escondidas” nos cerca de 4,5 mil milhões de movimentos potenciais das oito rainhas no tabuleiro.
Razão pela qual os matemáticos decidiram complicá-lo.
A variação
Em vez de se limitar a um tabuleiro de tamanho padrão 8×8, com 64 quadrados no total, o enigma expande as dimensões do problema para incluir praticamente qualquer número de rainhas.
Nesse caso, é preciso ajustar 20 rainhas num tabuleiro 20×20, ou 100 rainhas num tabuleiro 100×100, e assim sucessivamente – sendo que nenhuma das rainhas pode ser posicionada na mesma linha, coluna ou diagonal que as suas semelhantes.
Mas esta variante do problema matemático, chamado de “Enigma n-Rainhas”, torna-se realmente complicado quando se chega a números grandes, como n = 1.000. Até os mais poderosos computadores têm dificuldade em resolvê-lo, dado o número de possibilidades envolvidas.
O nível do desafio torna-se ainda maior se se adicionar um factor incomum: um grupo de rainhas que já ocupam posições definidas no tabuleiro.
O prémio
O problema pode ser fácil de entender, mas descobrir formas de o resolver de forma eficiente é um grande obstáculo, de enorme complexidade computacional.
“Se criássemos um programa de computador que pudesse resolver rapidamente o problema, poderíamos adaptá-lo para resolver muitos outros problemas que nos afectam diariamente”, afirma o cientista de computação Ian Gent, da Universidade de St. Andrews, no Reino Unido.
“Isso inclui desafios triviais, como descobrir o maior grupo dos seus amigos do Facebook que não se conhecem, ou muito mais importantes, como descobrir os códigos que mantêm todas as nossas transacções online seguras”, explica.
Por essa razão, o Clay Mathematics Institute está a oferecer um prémio de um milhão de dólares a quem resolver o desafio, como parte do Millennium Prize Problems.
A equipa de Gent estabeleceu que o enigma é um exemplo do chamado problema “P versus NP”, num artigo publicado no Journal of Artificial Intelligence Research. Isso significa que qualquer algoritmo que possa resolver o enigma pode também ser usado para resolver qualquer outro problema do mesmo tipo.
O prémio será ganho por quem provar que nenhum algoritmo pode resolver o enigma num tempo razoável, ou por quem desenvolver um algoritmo que possa resolvê-lo.
“Na prática, ninguém chegou perto de escrever um programa que possa resolver o problema rapidamente. Então, o que a nossa pesquisa mostra é que – para todos os efeitos práticos – isso não pode ser feito”, argumenta.
Será que alguém está disposto a mostrar-lhe que está errado?
[sc name=”assina” by=”ZAP” url=”https://hypescience.com/voce-pode-ganhar-um-milhao-de-dolares-solucionando-este-misterio-matematico-de-xadrez/” source=”HypeScience” ]
Dêem-me 5 minutos… (…) ou 5 milénios!
Eu estou
Mas primeiro quero 50% e só depois dou a solução
Essa é fácil:
Z=(n+((x-y/(n*3))^2)/pi)*cosn/x^pi
Em que
Z = entrada horizontal do tabuleiro
X = entrada vertical do tabuleiro
n = número de rainhas
y = Z*X/(Z+X)
Assunto resolvido. Venha o próximo.
Como assim podera explicar
Mas será sempre a mesma pessoa que escreve sobre ciência e temas «fora da caixa»? Que diabo, traduzir não é assim tão difícil, o que parece ser mais difícil é escrever correctamente em português. Para além de falhas permanentes de concordância entre sujeito e predicado e estruturas gramaticais sem sentido, existe um conjunto tão grande de «issos» e «istos» utilizados no texto que até cansa. Os anglo-saxónicos utilizam this e that a torto e a direito, e os brasileiros idem, mas em português soa mesmo mal. Vamos lá a melhorar «isso» :).
Pimba! Até estou surpreendido como o seu comentário ainda não desapareceu. É o que o ZAP costuma fazer quando é “ofendido”… Mas… Se fosse só as traduções o problema do ZAP…
Obrigado pelo «apoio». É que quase que parece que já ninguém se preocupa com a correcção da escrita. Aceito que a pressão para escrever textos seja realmente muita mas isso não deve ser desculpa para tudo, nomeadamente para a menor precisão em termos científicos. Posso estar a esperar de mais mas pode ser que as críticas construtivas ajudem :).
Caro Jorge,
O texto continha efectivamente algumas opções de estilo que optámos por alterar. Obrigado pelo seu reparo.
Não encontrámos no entanto nenhuma imprecisão em termos científicos. Pode por favor especificar?
Muito boa noite. Começo por louvar por um lado o esforço efectuado em termos a clareza e estrutura gramatical do texto, o qual ficou realmente bem mais claro e fácil de ler. Em segundo lugar, registo igualmente o meu agrado por responderem ao meu comentário, algo que infelizmente é hoje em dia cada vez mais raro e, quando ocorre, quase nunca tem lugar de um modo construtivo, antes assumindo um carácter de sobranceria ou aproximando-se mesmo da má educação. Os meus parabéns desde já.
No que se refere às incorrecções científicas tenho que reconhecer que, ao que me lembro, já que com a nova escrita o texto mudou (para melhor), que na situação vigente se tratava de uma incongruência que deixava algumas dúvidas sobre a quem ficava atribuída a tarefa de descobrir a solução para o enigma. Este não era, no entanto, o caso mais negativo em termos científicos, outros artigos publicados no Zap atingem uma percentagem maior de incorrecções. Fica aqui desde já a promessa de que no futuro ficarei mais atento e irei então tomar nota de imediato daquilo que considere menos correcto e comunicar-vos-ei as minhas opiniões, que não têm necessariamente de estar todas correctas. Mais uma vez, sinceros agradecimentos por este profícuo diálogo.
Caro senhor Pimba,
O comentário do do leitor Jorge Gonçalves não nos ofende. Enriquece-nos.
O seu, pelo contrário, é um disparate despropositado e descabido.
E ofende-nos. Como é, aliás, habitual nos seus comentários.
Se tem críticas construtiva a fazer ao conteúdo, faça.
Mas se apenas lhe apraz criticar a qualidade, carácter, honestidade, ou intenção dos nossos jornalistas ou do ZAP, apenas lhe podemos sugerir que deixe de nos visitar.
Porque o tempo que estamos a gastar a tentar explicar-lhe a diferença entre as duas coisas era mais útil se fosse usado a fazer artigos mais perfeitos.
Temos que alimentar constantemente as nossas bagagens intelectuais
Já agora, acrescento que a Raínha pode mover-se em 4 – QUATRO – direcções, não oito: horizontal, vertical e nas 2 diagonais. “para a direita e para a esquerda” NÃO são duas direcções, são DOIS SENTIDOS da mesma direcção.
Na linguagem comum, usam-se intercambiavelmente – e erradamente – sentido e direcção; mas numa divulgação científica, seria bom manter o mais possível a correcção técnica dos termos.
Confesso que também tenho peco deste defeito de linguagem quando se trata do dia-a-dia, mas, ao contrário, sou extrememente atento quando se trata de discussão técnica e/ou profissional.
Caro Ahahah,
Efectivamente, todos nós temos o mau hábito de dizer que vamos “em direcção a Lisboa”, e não “no sentido de”. Não podemos é escrever como falamos.
Repare no entanto que o nosso texto não diz que a rainha se move em 8 direcções, diz que se move “em todas as direcções”:
“(…) para cima e para baixo, para ambos os lados e diagonalmente para todos os lados (…)”
Mas efectivamente, talvez tivesse sido mais correcto descrever as direcções como “vertical”, “horizontal” e “nas duas diagonais”.
Isso é caso sério!!!
O problema que foi provado ser computacionalmente difícil se P for diferente de NP não foi o problema das n-rainhas, mas o problema de estender uma solução parcial do problema da n-rainhas para uma solução completa. Segundo os autores, o problema das n-rainhas comprovadamente tem solução para todo n>3, portanto é trivial decidir se o problema tem ou não tem uma solução. Os autores mostraram que dado um valor de n e uma solução parcial para o problema das n-rainhas, o problema de determinar se essa solução parcial pode ser estendida para uma solução com n damas é NP-completo. Solucionar esse último problema em tempo polinomial ou provar que tal solução não existe é o que resolveria a importante questão P versus NP. Vejam a nota do próprio Clay Mathematics Institute aqui: http://claymath.org/events/news/8-queens-puzzle