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 (Proceedings of the SBC Undergraduate Research Contest (CTIC-SBC), 2015)
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).