O jogo de lógica Sudoku: modelagem teórica, NP-Completude e estratégias algorítmicas exatas e heurísticas - Takano, Kevin; de Freitas, Rosiane; de Sá, Vinícius (Anais do Concurso de Trabalhos de Iniciação Científica da SBC (CTIC-SBC); 2015: Anais do XXXIV Concurso de Trabalhos de Iniciação Científica da SBC, 2015)
Neste artigo, são abordados os aspectos matemático-computacionais do jogo de lógica Sudoku. O Sudoku clássico consiste em um grid 9x9, parcialmente preenchido, onde se deve encontrar o local certo para serem inseridos números de 1 a 9, de modo que nenhum se repita na mesma linha, na mesma coluna ou no mesmo sub-quadrado em que esteja. O Sudoku é um problema computacional NP-completo, apresentado neste estudo sob diversos aspectos - unique SAT, cobertura exata, pré-coloração estendida e quadrado latino. Foi realizado um estudo e implementação das principais técnicas e algoritmos para resolução exata da literatura, envolvendo enumeração implícita como backtracking com podas, manipulação de bits, dancing links, propagação por restrições e programação inteira. Com base neste estudo, dois métodos são propostos, sendo um método exato baseado em propagação por restrições, com resultados de melhor desempenho do que os similares da literatura, bem como um método metaheurístico GRASP para Sudokus genéricos nxn. Também, algoritmos para o caso polinomial do grid vazio são propostos, que serviram de base para algoritmos de geração automática de instˆancias de nível fácil, médio e difícil. Tal estudo e resultados fazem parte de um projeto de pesquisa do Programa Institucional de Bolsas de Iniciação Científica - PIBIC (UFAM e CAPES).