HEURÍSTICAS EVOLUTIVAS E OTIMIZAÇÃO MATEMÁTICA: SOLUCIONANDO SUDOKU COM ALGORITMOS GENÉTICOS EM PYTHON

Autores

  • Felipe de Jesus Miranda ifg@ifg.edu.br
    Instituto Federal de Educação, Ciência e Tecnologia de Goiás, Câmpus Senador Canedo
  • Edson Lauandre Nunes Ferreira ifg@ifg.edu.br
    Instituto Federal de Educação, Ciência e Tecnologia de Goiás, Câmpus Senador Canedo
  • Diogo Gonçalves Dias ifg@ifg.edu.br
    Instituto Federal de Educação, Ciência e Tecnologia de Goiás, Câmpus Senador Canedo
  • Alfredo de Oliveira Assis ifg@ifg.edu.br
    Instituto Federal de Educação, Ciência e Tecnologia de Goiás, Câmpus Senador Canedo

Palavras-chave:

Algoritmos Genéticos, Sudoku, Otimização Combinatória, Heurísticas Evolutivas, Python

Resumo

O presente trabalho tem como objetivo investigar e implementar um algoritmo genético voltado à busca de soluções para diferentes instâncias do jogo Sudoku, utilizando a linguagem Python no ambiente Google Colab, bem como analisar o seu comportamento frente a variados níveis de complexidade. O Sudoku configura-se como um problema de satisfação de restrições (PSR) que, além de sua dimensão recreativa, apresenta relevante valor acadêmico para a fundamentação de métodos computacionais de busca e otimização. A metodologia fundamentou-se nos conceitos estruturantes dos algoritmos genéticos, tais como população, função de fitness, seleção, cruzamento, mutação e evolução geracional. A modelagem computacional do problema contemplou a representação adequada das soluções, a preservação estrita das células fixas (valores iniciais) e a formulação de uma função de fitness encarregada de quantificar e avaliar os conflitos existentes nas linhas, colunas e subgrades. Foram conduzidos experimentos com instâncias classificadas nos níveis fácil, médio e difícil, perfazendo um total de 30 execuções experimentais, distribuídas igualmente entre as categorias analisadas. Como operadores evolutivos, empregaram-se a seleção por torneio, a recombinação uniforme e a mutação adaptada, viabilizando o monitoramento do progresso das soluções ao longo das gerações. Os resultados demonstraram que o algoritmo obteve convergência satisfatória e 100% de êxito na resolução das instâncias de nível fácil. Contudo, nas instâncias médias e difíceis, observaram-se episódios de estagnação associados à convergência prematura em ótimos locais, bem como um incremento expressivo no tempo de processamento computacional. Durante o processo de desenvolvimento, foram aplicados ajustes pontuais na preservação das células fixas, na estratégia de mutação e no ajuste fino de hiperparâmetros, visando mitigar as limitações identificadas. Conclui-se que a sistematização e a aplicação do algoritmo genético ao problema abordado propiciaram a compreensão prática de suas potencialidades e restrições operacionais. Como perspectivas de continuidade, destacam-se o aprimoramento do mecanismo de verificação de conflitos, o teste de novas estratégias e heurísticas evolutivas, além da investigação do potencial de transferência do conhecimento construído para outros problemas de otimização combinatória, tais como o alocamento e a organização de quadros de horários (timetabling).

Downloads

Não há dados estatísticos.

Downloads

Publicado

2026-11-18

Métricas


Visualizações do artigo: 9     PDF downloads: 1

Como Citar

MIRANDA, Felipe de Jesus; FERREIRA, Edson Lauandre Nunes; DIAS, Diogo Gonçalves; ASSIS, Alfredo de Oliveira. HEURÍSTICAS EVOLUTIVAS E OTIMIZAÇÃO MATEMÁTICA: SOLUCIONANDO SUDOKU COM ALGORITMOS GENÉTICOS EM PYTHON. Anais do Seminário de Iniciação Científica e Tecnológica do IFG, [S. l.], v. 19, n. 1, 2026. Disponível em: https://periodicos.ifg.edu.br/sicti/article/view/3602. Acesso em: 20 nov. 2026.