Explorando operadores de um Algoritmo Genético aplicado ao jogo Sudoku
Resumo
Este trabalho apresenta o desenvolvimento e a avaliação de um Algoritmo Genético (AG) para resolver o jogo Sudoku clássico, um problema de otimização combinatória classificado como NP, a fim de melhorar os resultados obtidos nos estudos de [Bernardes 2025]. O AG foi implementado em Python, com indivíduos representados por matrizes 9x9 e com uma função de fitness baseada na minimização de conflitos. A modelagem do Sudoku como problema de permutação e a metodologia utilizada foram os fatores decisivos para o sucesso do algoritmo, superando a principal referência (de 20% para 90% na instância analisada).
Referências
Bellman, R. (1957). Dynamic Programming. Princeton University Press. [link].
Bernardes, A. O. (2025). Algoritmo genético aplicado ao jogo de tabuleiro sudoku. Trabalho de conclusão de curso de bacharelado, Universidade Federal de Uberlândia, Uberlândia, MG. [link].
Bäck, T., Fogel, D. B., and Michalewicz, Z. (2000). Evolutionary Computation 1: Basic Algorithms and Operators. Institute of Physics Publishing, Bristol, UK. [link].
Dantzig, G. B. (1957). Discrete-variable extremum problems. Operations Research, 5(2):266–288. DOI: 10.1287/opre.5.2.266.
Darwin, C. (1859). On the Origin of Species by Means of Natural Selection, or the Preservation of Favoured Races in the Struggle for Life. John Murray, London, England, United Kingdom. [link].
Eiben, A. E. and Smith, J. E. (2015). Introduction to evolutionary computing. Springer, Berlim e Heidelberg, Alemanha, 2 edition. [link].
Flood, M. M. (1956). The traveling-salesman problem. Operations Research, 4(1):61–75. DOI: 10.1287/opre.4.1.61.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco. [link].
Garns, H. (1979). Number place. Publicado na revista Dell Pencil Puzzles and Word Games. Considerado o precursor do Sudoku moderno.
Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison Wesley, Massachusetts, USA. [link].
Holland, J. H. (1975). Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control and artificial intelligence. MIT Press, Cambridge, MA, USA. DOI: 10.7551/mitpress/1090.001.0001.
Neves, F. A. A. S. C. (2020). Análise da eficiência de um algoritmo genético aplicado ao sudoku. Trabalho de conclusão de curso de bacharelado, Universidade Tecnológica Federal do Paraná, Cornélio Procópio, PR. [link].
Wang, C., Sun, B., Du, K.-J., Li, J.-Y., Zhan, Z.-H., Jeon, S.-W., Wang, H., and Zhang, J. (2023). A novel evolutionary algorithm with column and sub-block local search for sudoku puzzles. IEEE Transactions on Games, PP:1–11. DOI: 10.1109/TG.2023.3236490.
Yato, T. and Seta, T. (2003). Complexity and completeness of finding another solution and its application to puzzles. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E86-A(5):1052–1060.
Bernardes, A. O. (2025). Algoritmo genético aplicado ao jogo de tabuleiro sudoku. Trabalho de conclusão de curso de bacharelado, Universidade Federal de Uberlândia, Uberlândia, MG. [link].
Bäck, T., Fogel, D. B., and Michalewicz, Z. (2000). Evolutionary Computation 1: Basic Algorithms and Operators. Institute of Physics Publishing, Bristol, UK. [link].
Dantzig, G. B. (1957). Discrete-variable extremum problems. Operations Research, 5(2):266–288. DOI: 10.1287/opre.5.2.266.
Darwin, C. (1859). On the Origin of Species by Means of Natural Selection, or the Preservation of Favoured Races in the Struggle for Life. John Murray, London, England, United Kingdom. [link].
Eiben, A. E. and Smith, J. E. (2015). Introduction to evolutionary computing. Springer, Berlim e Heidelberg, Alemanha, 2 edition. [link].
Flood, M. M. (1956). The traveling-salesman problem. Operations Research, 4(1):61–75. DOI: 10.1287/opre.4.1.61.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco. [link].
Garns, H. (1979). Number place. Publicado na revista Dell Pencil Puzzles and Word Games. Considerado o precursor do Sudoku moderno.
Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison Wesley, Massachusetts, USA. [link].
Holland, J. H. (1975). Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control and artificial intelligence. MIT Press, Cambridge, MA, USA. DOI: 10.7551/mitpress/1090.001.0001.
Neves, F. A. A. S. C. (2020). Análise da eficiência de um algoritmo genético aplicado ao sudoku. Trabalho de conclusão de curso de bacharelado, Universidade Tecnológica Federal do Paraná, Cornélio Procópio, PR. [link].
Wang, C., Sun, B., Du, K.-J., Li, J.-Y., Zhan, Z.-H., Jeon, S.-W., Wang, H., and Zhang, J. (2023). A novel evolutionary algorithm with column and sub-block local search for sudoku puzzles. IEEE Transactions on Games, PP:1–11. DOI: 10.1109/TG.2023.3236490.
Yato, T. and Seta, T. (2003). Complexity and completeness of finding another solution and its application to puzzles. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E86-A(5):1052–1060.
Publicado
15/06/2026
Como Citar
BRASIL, Christiane Regina Soares; BERNARDES, Andressa Oliveira.
Explorando operadores de um Algoritmo Genético aplicado ao jogo Sudoku. In: ESCOLA REGIONAL DE INFORMÁTICA DO TRIÂNGULO MINEIRO (ERI-TM), 1. , 2026, Uberlândia/MG.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 77-81.
DOI: https://doi.org/10.5753/eritm.2026.27247.
