Queres ganhar um milhão de dólares? Só tens que resolver este mistério de xadrez!
Pode ganhar 1 milhão de dólares se conseguir resolver um problema matemático extremamente complicado, que envolve um jogo de xadrez, conhecido como “Enigma da Rainha”.
Não é preciso saber as regras do xadrez para participar, mas isso também não vai facilitar as coisas. Na verdade, os cientistas dizem que a solução é tão complexa que pode levar milhares de anos para chegarmos a ela.
A questão original
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 directamente a outra. Se conhece as regras do xadrez, sabe que a rainha é a peça mais poderosa do tabuleiro, pois pode mover-se em oito direcçõ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 direcçõ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 milhões de movimentos potenciais das oito rainhas no tabuleiro. Logo, os matemáticos decidiram complicá-lo.
A variação
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. Neste 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 adicionar um factor incomum: um grupo de rainhas que já ocupam posições definidas no tabuleiro.
O 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 afectam 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 transacções online seguras”. É por isso que o Clay Mathematics Institute está oferecendo um prémio de 1 milhão de dólares para quem resolver o desafio, como um dos seus “Problemas do Milênio”.
Porque vale tanto
A equipa 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?