Você pode ganhar um prêmio de US$ 1 milhão (cerca de R$ 3,15 milhões, no câmbio atual) se conseguir resolver a variação de um problema matemático extremamente complicado envolvendo um jogo de xadrez, conhecido como “Enigma da Rainha” ou “Problema das Oito Rainhas”.
Não é preciso entender as regras do xadrez para participar, mas isso também não vai facilitar as coisas nenhum pouco. Na verdade, os cientistas dizem que a solução é tão complexa que pode levar milhares de anos para chegarmos nela.
O Problema das Oito Rainhas foi originalmente criado em 1848. O desafio é colocar oito rainhas em um tabuleiro de xadrez 8 x 8, de modo que nenhuma ameace diretamente a outra.
Se você conhece as regras do xadrez, sabe que a rainha é a peça mais poderosa do tabuleiro, pois pode mover-se em oito direções – para cima, para baixo, para ambos os lados e diagonalmente para todos os lados. Além disso, também pode se mover a uma distância ilimitada em qualquer uma dessas direções.
Essa liberdade de movimento é a razão pela qual o enigma é tão interessante, embora não tão difícil assim de se resolver. Na verdade, existem 92 formas diferentes de solucioná-lo, de cerca de 4,5 bilhões de movimentos potenciais das oito rainhas no tabuleiro.
Logo, os matemáticos decidiram complicá-lo.
Em vez de se limitar a um tabuleiro de tamanho padrão 8 x 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 em um tabuleiro 20 x 20, ou 100 rainhas em um tabuleiro 100 x 100, e assim por diante – e nenhuma delas pode ser posicionada na mesma linha, coluna ou diagonal que suas semelhantes.
Esta variante do quebra-cabeça, chamado de “Enigma n-Rainhas”, fica realmente complicado quando chegamos a números grandes, como n = 1.000. Até computadores muito poderosos têm dificuldade de resolvê-lo, dado o número de possibilidades envolvidas.
O nível do desafio torna-se ainda maior se você adicionar um fator incomum: um grupo de rainhas que já ocupam posições definidas no tabuleiro.
Prêmio
O prêmio diz respeito a resolução do Enigma das n-Rainhas, com algumas peças já colocadas no tabuleiro. O problema pode ser fácil de entender em sua mente, mas descobrir maneiras de resolvê-lo de forma eficiente é um grande obstáculo de enorme complexidade computacional.
“Se criássemos um programa de computador que pudesse resolver o problema rápido, poderíamos adaptá-lo para resolver muitos outros problemas que nos afetam diariamente”, disse o cientista da computação Ian Gent, da Universidade de St. Andrews, no Reino Unido.
“Isso inclui desafios triviais, como descobrir o maior grupo de seus amigos do Facebook que não se conhecem, ou muito mais importantes, como descobrir os códigos que mantêm todas as nossas transações online seguras”, acrescentou.
É por isso que o Clay Mathematics Institute está oferecendo um prêmio de US$ 1 milhão para quem resolver o desafio, como um de seus “Problemas do Milênio”.
A equipe de Gent estabeleceu que o enigma é um exemplo do chamado problema “P versus NP”, em um 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 da mesma classe.
De acordo com Gent, o prêmio pode ser ganho se alguém provar que nenhum algoritmo pode resolver o enigma em um tempo razoável, ou se alguém desenvolver um algoritmo que possa resolvê-lo em um tempo razoável.
“Na prática, ninguém chegou perto de escrever um programa que possa resolver o problema rapidamente. Então, o que nossa pesquisa mostra é que – para todos os propósitos práticos – isso não pode ser feito”, argumenta Gent.
Será que alguém vai mostrar que ele está errado?
// HypeScience
