Algoritmo evolutivo aplicado à otimização da resolução de Sudoku

Abstract

O presente trabalho propõe um algoritmo híbrido para a resolução de quebra-cabeças Sudoku que combina estratégias lógicas, como: Naked Singles, Hidden Singles, Naked Pairs e X-Wings com um Algoritmo Genético (AG) para otimizar a busca por soluções. A motivação para esse estudo encontra-se na elevada complexidade computacional do Sudoku, que o torna um objetivo de pesquisa relevante para validação de novos algoritmos que, futuramente, podem ser aplicados para resolução de problemas da vida real. A abordagem híbrida sugerida demonstrou ser significativamente mais eficaz do que apenas o AG, alcançando uma taxa de sucesso de 94,56% em um conjunto de 46 Sudokus de diferentes níveis e características nas 12 rodadas de teste realizadas, o que representa um aumento de cerca de 28,8% em comparação com a taxa de 65,76% alcançada apenas pelo AG. A etapa de pré-processamento, em que as técnicas de resolução são aplicadas, resolveu de forma autônoma 73,91% dos puzzles testados e, nos casos mais complexos, reduziu consideravelmente o espaço de busca e acelerou a convergência do AG. Nesse contexto, o trabalho concluiu que a integração de métodos determinísticos com meta-heurísticas representa uma estratégia robusta para problemas de otimização combinatória. Desse modo, as principais contribuições deste projeto incluem o modelo híbrido proposto, a análise empírica de seu desempenho e a disponibilização do código-fonte.