O jogo de lógica Sudoku: modelagem teórica, NP-Completude e estratégias algorítmicas exatas e heurísticas
Abstract
In this article, the computational mathematics aspects of the Sudoku puzzle, a logic game, are covered. The classic Sudoku consists of a grid 9x9, partially filled, where to find the right place to be inserted numbers from 1 to 9, so that no repeat on the same line in the same column or in the same sub-square where it is. The Sudoku is an NP-complete computational problem, presented in this study in many ways - as unique SAT, exact cover, precoloring extension, and Latin square. It conducted a study and implementation of the main techniques and algorithms for exact resolution from the literature, involving implicit enumeration as backtracking with pruning, bit manipulation, dancing links, constraint propagation, and integer programming. Based on this study, two methods are proposed, an exact method based on constraint propagation, with better performance than similar one from the literature, as well as a GRASP metaheuristic method for generic Sudokus nxn. Also, polynomial algorithms for the case of the empty grid are proposed, which served as the basis for automatic generation algorithms easy level instances, medium and hard. Such study and results are part of a research project of the Institutional Program for Scientific Initiation Scholarships - PIBIC (UFAM and CAPES).
References
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).
