Navegar

13/09/2017

Xeque-mate de um milhão de dólares

Um dos jogos mais antigos da humanidade, o xadrez desafia os competidores com problemas que, ao primeiro olhar, parecem simples, mas que podem levar mais de um século até serem resolvidos.

A solução de um dos sete problemas do milênio (P versus NP) voltou depois que professores da Universidade de Saint Andrews (Escócia) publicaram artigo relatando que os programadores atuais são incapazes de encontrar todas as soluções para a questão.

Assim, o Instituto Clay de Matemática volta a oferecer US$ 1 milhão (R$ 3,2 milhões) a quem resolver esse ‘simples’ enigma de xadrez, que consiste em colocar 1.000 rainhas em um tabuleiro de 1.000 casas x 1.000 casas sem que se comam umas às outras. Resumindo: não podem existir duas rainhas na mesma fileira, coluna e diagonal.

Instigante, o desafio encheu os olhos de cientistas que há anos tentam criar um algoritmo capaz de gerar todas as soluções para o enigma. O que ninguém contava era que o artigo “Complexity of n-Queens Completion”, da Universidade de Saint Andrews, trouxesse más notícias para os quem têm buscado a solução.

A origem da questão é o chamado problema das oito rainhas, proposto em 1848 pelo enxadrista alemão Max Bezzel. O objetivo era colocar oito rainhas sobre um tabuleiro padrão (8×8) sem que se as peças se ameaçassem entre si. Embora complexo, o problema foi resolvido dois anos depois pelo matemático cego Franz Nauck, cuja resposta conta com 92 soluções: 12 básicas e 80 obtidas por giros e simetrias.

O fato é que, conforme o tabuleiro e o número de rainhas aumentam, cresce também o número de soluções, tornando o enigma P versus NP mais difícil de resolver.  Segundo os pesquisadores escoceses, quando o tabuleiro de xadrez é igual ou maior a 1.000 x 1.000, é impossível encontrar todas as soluções para o problema porque são tantas as possibilidades que os atuais programas demorariam anos para apenas considerar as respostas, gerando um “backtracking”, ou seja, fenômeno onde o código do programa retrocede até o momento em que uma solução é encontrada.

Embora seja um problema matemático, sua resolução traria benefícios para outras áreas. Caso consigam criá-lo, esse superprograma poderia ser adaptado para solucionar o desenho de microchips e até decifrar sistemas de segurança da internet.

Para Peter Nightingale, um dos autores do artigo, a solução do problema das oito rainhas e, consequentemente, do enigma P versus NP está longe de acontecer. “Para todos os propósitos práticos, não pode ser feito”, garante.