Publicação: Algoritmo Genético aplicado ao jogo de tabuleiro Sudoku
Carregando...
Tipo do documento
Data
Direito de acesso
Programa
Área do conhecimento
CNPQ::CIENCIAS EXATAS E DA TERRA
Título da Revista
ISSN da Revista
Título de Volume
Autores
Orientador
Coorientador
Resumo
Este trabalho aborda o desenvolvimento e a avaliação de um Algoritmo Genético (AG)
para a resolução do quebra-cabeça Sudoku, um problema de otimização combinatória
NP-completo. O objetivo principal foi investigar como diferentes parâmetros e opera-
dores genéticos impactam a eficácia e a eficiência do algoritmo na busca por soluções
válidas. Para isso, implementou-se um AG em Python com indivíduos representados
por matrizes 9x9, função de fitness baseada na minimização de conflitos e opera-
dores de recombinação, mutação e elitismo. A metodologia envolveu uma série de
experimentos controlados para calibrar iterativamente os parâmetros do algoritmo. Os
resultados definiram uma configuração otimizada com população de 600 indivíduos,
mutação de 1%, elitismo de 5% e torneio de tamanho 3. A análise demonstrou que a
escolha dos operadores foi o fator mais determinante para o desempenho, com a com-
binação da Recombinação Uniforme e da Mutação por Gene apresentando a aborda-
gem mais eficaz para atingir a solução ótima com maior regularidade. Por fim, conclui-
se que a eficiência do AG é limitada pela sua natureza aleatória, tornando sua aplica-
ção mais pertinente a cenários complexos onde etapas lógicas de pré-processamento
não são, por si sós, suficientes para a resolução.
Abstract
This study addresses the development and evaluation of a Genetic Algorithm (GA) for
solving the Sudoku puzzle, an NP-complete combinatorial optimization problem. The
main objective was to investigate how different parameters and genetic operators im-
pact the effectiveness and efficiency of the algorithm in searching for valid solutions.
To this end, a GA was implemented in Python with individuals represented by 9x9 ma-
trices, a fitness function based on conflict minimization and recombination, mutation
and elitism operators. The methodology involved a series of controlled experiments to
iteratively calibrate the algorithm parameters. The results defined an optimized confi-
guration with a population of 600 individuals, 1% mutation, 5% elitism and tournament
size 3. The analysis demonstrated that the choice of operators was the most determi-
ning factor for performance, with the combination of Uniform Recombination and Gene
Mutation presenting the most effective approach to achieving the optimal solution with
greater regularity. Finally, it is concluded that the efficiency of GA is limited by its ran-
dom nature, making its application more pertinent to complex scenarios where logical
pre-processing steps are not, by themselves, sufficient for resolution.
Palavras-chave
Algoritmo Genético, Genetic Algorithm, Sudoku, Fitness, Otimização de parâmetros, Parameter optimization
Citação
BERNARDES, Andressa Oliveira. Algoritmo Genético aplicado ao jogo de tabuleiro Sudoku. 2025. 58 f. Trabalho de Conclusão de Curso (Graduação em Sistemas de Informação) - Universidade Federal de Uberlândia, Uberlândia, 2025.
DOI
Avaliação
Revisão
Suplementado Por
Referenciado Por
Licença Creative Commons
Exceto quando indicado de outra forma, a licença deste item é descrita como Acesso Aberto