O jogo de lógica Sudoku: modelagem teórica, NP-Completude e estratégias algorítmicas exatas e heurísticas
Resumo
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).
Referências
Colbourn, C. (1984). The complexity of completing partial latin square. Elsevier Science Plubishers.
Cook, P. (2006). Solving every sudoku puzzles with python. http://www2.warwick.ac.uk/fac/sci/moac/people/students/peter_cock/python/sudoku. Acessado em 26 de abril de 2015.
Hoeve, W.-J. (2001). The all different constraint: A survey. In 6th Annual Workshop of the ERCIM Working Group on Constraints.
Lewis, R. (2007). Metaheuristcs can solve sudoku puzzles. Jornal of Heuristics.
McNair, R. (2005). Number of (completed) sudokus (or sudokus) of size n2 x n2. http://oeis.org/A107739. Acessado em 26 de abril de 2015.
Norvig, P. (2006). Solving every sudoku puzzle. http://norvig.com/sudoku.html. Acessado em 26 de abril de 2015.
Skiena, S. S. (2008). Algorithm Design Manual. Springer Publishing.
Sloane, N. J. A. (2004a). Number of latin squares of order n; or labeled quasigroups. http://oeis.org/A002860. Acessado em 26 de abril de 2015.
Sloane, N. J. A. (2004b). Number of reduced latin squares of order n; also number of labeled loops (quasigroups with an identity element) with a fixed identity element. http://oeis.org/A000315. Acessado em 26 de abril de 2015.
Sloane, N. J. A. (2005). Number of inequivalent (completed) n2 x n2 sudokus (or sudokus). http://oeis.org/A109741. Acessado em 26 de abril de 2015.
Yato and Seta (2002). Complexity and completeness of finding another solution and its application to puzzles. In Procceedings of The National Meeting of the Information Society of Japan (IPSJ).
