Sudoku. Número mínimo de pistas já não é mistério

Três investigadores da Universidade de Dublin criaram um algoritmo para resolver um mistério que desde os anos 1980 assolava a comunidade sudoku: qual o número mínimo de pistas (números revelados à partida) para que só exista uma solução para cada puzzle, uma das regras do quebra-cabeças japonês. A resposta é 17, como já se suspeitava, revelam num artigo publicado online a 1 de Janeiro. Mas a prova matemática não foi fácil: depois de desenharem um programa especial para resolver o problema, os trabalhos de computação levaram um ano, de Janeiro de 2011 a Dezembro.

Ao longo de 40 páginas, os investigadores explicam com o problema do número mínimo de pistas do sudoku tem movimentado matemáticos em todo o mundo. Para o resolver de vez, provar que se é possível ou não um puzzle de 16 pistas, os investigadores construíram um catálogo com mais de 5 mil milhões de soluções de sudokus, uma amostra razoável para as 6, 670, 903, 752, 021, 072, 936, 960 existentes, explicam à revista do Instituto de Tecnologia de Massachusets, “Technology Review”, dado que muitas são equivalentes. Depois, usaram o algoritmo para pesquisar em cada uma das grelhas por cenários em que 16 pistas levariam a uma única solução, o que mais uma vez aumentou exponencialmente as análises necessárias (10 elevado a 16 por grelha). Os autores adiantam que o programa que desenvolveram, de análise rápida, poderá ser útil em áreas como análise de expressão genética ou teste de softwares.