Algoritmo Genético aplicado ao jogo de tabuleiro Sudoku

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.