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

Há uma forma de reduzir erros na computação quântica (e já sabemos qual é)

Na computação quântica, assim como no trabalho em equipa, um pouco de diversidade pode ajudar a melhorar o resultado. Esta pode mesmo ser a chave para pôr fim aos erros na computação quântica. Ao contrário dos …

Coimbrões 0-5 FC Porto | Dragões goleiam e seguem em frente na Taça

O FC Porto venceu hoje o Coimbrões, por 5-0, em jogo da terceira eliminatória da Taça de Portugal que os «dragões» resolveram com três golos nos 12 minutos iniciais. Aproveitando a inexperiência e nervosismo da formação …

Produção de filmes em Hollywood é um inimigo silencioso do ambiente

Hollywood é casa para a maioria dos grandes filmes produzidos que estreiam nas salas de cinema espalhadas por todo o mundo. Contudo, consegue ser bastante prejudicial para o meio ambiente e, mais do que nunca, …

O escorbuto era uma doença comum entre piratas, mas pode estar de regresso

O número de casos de escorbuto no Reino Unido mais do que duplicou nos últimos anos. A desnutrição é um dos principais responsáveis pelo regresso desta doença. O escorbuto está em ascensão no Reino Unido e …

Dois veleiros robotizados vão medir alterações climáticas no Atlântico

Dois veleiros de navegação robotizada vão medir, durante os próximos quatro meses, a pegada das mudanças climáticas no oceano Atlântico e irão passar pela Madeira e Cabo Verde. A Plataforma Oceânica das Canárias (PLOCAN) libertou esta …

A educação científica está sob ataque legislativo nos Estados Unidos

São inúmeros os professores de ciências que trabalham diariamente nas escolas públicas dos Estados Unidos para garantir que os alunos estão equipados com o conhecimento teórico e prático necessário para enfrentar o futuro. No entanto, …

João Félix saiu lesionado com gravidade no jogo contra o Valência

João Félix, avançado português do Atlético de Madrid, saiu este sábado lesionado com "forte torção no tornozelo direito", ao minuto 78 do jogo contra o Valência, da nona jornada da Liga espanhola de futebol, disputado …

As traças ficaram mais escuras por causa da Revolução Industrial? Cientistas já sabem a resposta

No virar do século XIX, na Grã-Bretanha, traças de todo o país começaram a ficar gradualmente mais escuras em resposta à forte poluição provocada pela Revolução Industrial. A Revolução Industrial foi um período de grandes transformações …

Mais de mil médicos foram alvo de processos disciplinares. 45 foram condenados, nenhum foi expulso

Mais de 1.070 processos disciplinares a médicos foram abertos no ano passado pelos conselhos disciplinares da Ordem, tendo sido condenados 45, segundo dados este sábado divulgados. Segundo os dados da Ordem dos Médicos, os conselhos disciplinares …

Publicar no Instagram rende mais a Ronaldo do que jogar na Juve

As publicações pagas no Instagram rendem mais a Cristiano Ronaldo do que jogar na Juventus, revela um estudo do Buzz Bingo. O internacional português foi a personalidade mais bem paga neste rede social em 2018. De …