Qualquer um pode ganhar um milhão de dólares solucionando este mistério matemático de xadrez

Por , em 5.09.2017

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.

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

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.

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.

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

É 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” (veja outros no link abaixo).

Por que vale tanto

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? [ScienceAlert]

1 Star2 Stars3 Stars4 Stars5 Stars (13 votos, média: 4,54 de 5)

3 comentários

Deixe seu comentário!