Metaheurísticas simulated annealing e busca tabu aplicadas na resolução do quebra-cabeça sudoku

Abstract

O quebra-cabeça Sudoku é considerado um problema NP-difícil, e por este fato desperta a atenção de pesquisadores. É um jogo muito popular, jogado por milhões de pessoas, sendo de difícil resolução dependendo das condições inicias do quebra-cabeça. Neste artigo apresentam-se duas metodologias para resolver o quebra-cabeça Sudoku: as metaheurísticas Simulated Annealing e Busca Tabu. Os algoritmos foram desenvolvidos na linguagem C++ Builder 6.0, utilizando interface gráfica. Para evidenciar a eficácia destas metodologias foram realizados vários testes, sendo possível comprovar que as metodologias encontram a solução ótima para diferentes níveis de dificuldade: fácil, médio, difícil (sudoku com dimensão 3x3) e super-sudoku (sudoku com dimensão 4x4) para o quebra-cabeça sudoku.