Cientistas oferecem um milhão de dólares a quem solucionar mistério matemático de xadrez

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?

PARTILHAR

15 COMENTÁRIOS

  1. 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.

  2. 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.

  3. 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”.

  4. 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

RESPONDER

"Árvores dinossauro". Bombeiros australianos conseguiram salvar floresta pré-histórica

Os bombeiros australianos conseguiram salvar dos incêndios uma floresta com árvores pré-históricas localizada no sudeste do país, anunciou o Governo. Em causa estão árvores da espécie Wollemia nobilis, vulgarmente conhecidas como Pinheiro de Wollemi, que se …

Príncipe Harry e Meghan renunciam aos títulos da realeza

O Palácio de Buckingham anunciou, este sábado, um acordo em que o príncipe Harry e a sua mulher renunciaram aos respetivos títulos, abandonando os deveres enquanto membros seniores da família real do Reino Unido e …

Polaris Slingshot chega ao mercado com um sistema de transmissão inovador

A nova versão do Polaris Slingshot vem equipado com um sistema de transmissão que mescla a condução do manual com o conforto do automático. Para quem não conhece o Polaris Slingshot, apresentado pela primeira vez em …

Turistas estão a invadir Hallstatt, a aldeia austríaca que terá inspirado "Frozen"

Considerado Património Mundial pela UNESCO desde 1997, Hallstatt, na Áustria, possui apenas 778 moradores e tem uma sequência de casas em estilo alpino. Em 2010, antes do lançamento do primeiro filme da Disney, "Frozen", a cidade …

Teerão vai enviar caixa negra do avião abatido para a Ucrânia

O Irão vai enviar para a Ucrânia as gravações da caixa negra do avião ucraniano que abateu acidentalmente, na semana passada, para que sejam sujeitas a análises adicionais. Hassan Rezaeifer, chefe de investigações de acidentes do …

António Folha já não é treinador do Portimonense

O treinador apresentou a demissão do comando técnico do Portimonense, este sábado, depois de perder na deslocação ao lanterna-vermelha Desportivo das Aves, por 3-0. "Antes de me fazerem qualquer pergunta sobre o jogo, queria transmitir que …

Há pombos cowboys em Las Vegas (e voluntários estão a tentar salvá-los)

Por alguma razão, alguém decidiu colar chapéus vermelhos minúsculos de cowboy em pombos de Las Vegas, nos Estados Unidos. Agora, a equipa do Lofty Hopes Pigeon Rescue está a tentar salvá-los. Há uma missão para resgatar …

Youtube encaminha milhões de utilizadores para desinformação climática

Os algoritmos do YouTube estão a encaminhar milhões de utilizadores de vídeos de empresas para a desinformação sobre as alterações climáticas, através de serviços de publicidade online, de acordo com uma investigação da comunidade virtual …

Paulo Gomes é o novo presidente do Vitória de Setúbal

O ex-vice-presidente, líder da lista D, foi eleito presidente do Vitória de Setúbal para o mandato 2020-2023, com um total de 875 votos. Paulo Gomes, de 50 anos, foi o mais votado das cinco listas candidatas, …

O mercado online de leite materno está a crescer (mas pode ser mau para os bebés)

https://vimeo.com/385229063 Para os pais que querem que o seu filho beba leite materno, mas que não conseguem produzi-lo, a possibilidade de o poder comprar na Internet pode parecer uma boa solução. No entanto, este mercado não …