O sudoku: unha aplicación da investigación de operacións

Abstract

O presente traballo céntrase no estudo matemático e computacional da resolución dun sudoku, partindo da súa conexión cos cadros latinos. Analízase a súa existencia e enumeración, sentando as bases dun marco teórico sólido para comprender a estrutura subxacente do sudoku. A continuación, descríbese o xogo nun contexto histórico e formal, estudando as súas regras e propiedades, o número total de taboleiros posibles, e, ademais, o problema do número mínimo de pistas necesarias para garantir unha solución única. Tamén se describen as técnicas de resolución manual máis empregadas, tanto básicas como avanzadas. A parte principal do traballo explora distintas metodoloxías de resolución mediante programación matemática, como a programación lineal, algoritmos de retroceso, métodos evolutivos (como o algoritmo xenético) e o recocido simulado, así como modelos baseados en grafos. Ademais esténdese a análise a algunhas variantes do sudoku. Finalmente, preséntase unha avaliación comparativa da eficiencia computacional de todas as metodoloxías propostas, baseada en implementacións na linguaxe R.

This work focuses on the mathematical and computational study of Sudoku solving, starting from its connection with Latin squares. Its existence and enumeration are analyzed, laying the groundwork for a solid theoretical framework to understand the underlying structure of Sudoku. The game is then described in a historical and formal context, examining its rules and properties, the total number of possible boards, as well as the problem of the minimum number of clues required to guarantee a unique solution. The most commonly used manual solving techniques, both basic and advanced, are also described. The main part of this work explores several solution methodologies using mathematical programming, including linear programming, backtracking algorithms, evolutionary methods (such as genetic algorithms), and simulated annealing, along with graph-based models. Furthermore, the analysis is extended to some Sudoku variants. Finally, a comparative evaluation of the computational efficiency of all proposed methodologies is presented, based on implementations in the R programming language.