Eis um bom desafio para os desenvolvedores familiarizados com a criação de algoritmos. Nesta quinta-feira, 31, a Universidade de St. Andrews, na Escócia, e o Clay Mathematics Institute, nos Estados Unidos, se uniram para anunciar uma competição com um prêmio de US$ 1 milhão. Para ganhar, basta criar uma solução para resolver um problema envolvendo o jogo de xadrez.
Obviamente, se o prêmio está nesse nível, é porque a solução não é simples. No entanto, é bem fácil entender o problema. Imagine um tabuleiro de xadrez convencional de 8×8. Você tem oito rainhas. Como você as distribuiria no tabuleiro de forma que fosse impossível, pelas regras de movimentação do jogo, que uma peça pudesse atacar a outra? Esse é o “problema das oito rainhas”, idealizado em 1850.
Esse problema matemático já possui solução, quando falamos em um tabuleiro convencional de 8×8. No entanto, quando o conceito é expandido para tabuleiros muito maiores (pense em algo na casa de 1.000×1.000, com 1.000 peças e assim por diante), a solução fica exponencialmente mais complexa. Por este motivo, os pesquisadores acreditam que um software de computador levaria pelo menos um milênio para conseguir resolver a questão. E é aí que entram os competidores.
O professor Ian Gent, um dos autores do desafio, explicou ao site Digital Trends qual é a participação dos competidores na brincadeira. Existem duas formas de ganhar o milhão de dólares: a primeira é provar por que nenhum algoritmo é capaz de resolver o problema das n-rainhas em um curto período de tempo, e a segunda é criar o algoritmo que seja capaz de solucionar a questão.
Segundo ele, encontrar um método eficiente de resolver o problema é “provavelmente a coisa mais difícil de se fazer em ciência da computação”, e o motivo por trás dessa dificuldade é que o método mais simples é a utilização de força bruta para solucionar a questão por tentativa e erro, o que envolve analisar a viabilidade de cada uma das alternativas. Quando o tabuleiro conta com um número imenso de casas, como no exemplo de 1.000×1.000, testar cada uma das alternativas se torna um exercício que depende de quantidades colossais de tempo. O algoritmo tem como missão encontrar uma forma mais inteligente de fazer tais cálculos.
Quais são os requisitos para participar do concurso? Não existe nenhum, além de ser um gênio com sorte. Gent dá três dicas para quem topar o desafio: tenha um doutorado em complexidade computacional, seja brilhante e tenha sorte.
O desafio vai além de um mero problema teórico sem qualquer aplicação prática. Caso solucionado, os pesquisadores acreditam que um algoritmo capaz de resolver o problema das rainhas também poderia solucionar outros problemas considerados impossíveis envolvendo criptografia, com inúmeras aplicações práticas; uma delas seria, por exemplo, tornar a navegação na internet mais segura e difícil de ser interceptada.
Tags: