SaturBFS: Um Algoritmo de Coloração de Grafos para Resolução do Sudoku
Resumo
Este estudo propõe um algoritmo de coloração de grafos intitulado Saturated Breadth-First Search (SaturBFS) para determinar soluções válidas do Sudoku. Concebeu-se o algoritmo por meio da combinação dos algoritmos de Busca em Largura (BFS) e DSatur. O objetivo é realizar uma análise comparativa do SaturBFS com os algoritmos BFS não saturado e Busca em Profundidade (DFS) para diferentes níveis (fácil, médio e difícil) e instâncias do Sudoku (4x4, 6x6, 8x8, 9x9, 10x10 e 12x12). Para a avaliação, considerou-se o tempo que os algoritmos levam para determinar uma solução válida e as porcentagens de soluções válidas encontradas. O algoritmo SaturBFS apresentou maior porcentagem de soluções válidas encontradas em um menor tempo.Referências
Bailey, R. A., Cameron, P. J., and Connelly, R. (2008). Sudoku, gerechte designs, resolutions, affine space, spreads, reguli, and hamming codes. The American Mathematical Monthly, 115(5):383–404.
Borges, S., Lima, T., and Marques, V. (2016). Coloração de grafos aplicado na resolução do sudoku.
Chel, H., Mylavarapu, D., and Sharma, D. (2016). A novel multistage genetic algorithm approach for solving sudoku puzzle. In 2016 International Conference on Electrical, Electronics, and Optimization Techniques (ICEEOT), pages 808–813. IEEE.
De Souza, S. S. and Romero, R. (2013). Metaheurísticas simulated annealing e busca tabu aplicadas na resolução do quebra-cabeça sudoku. Proceeding Series of the Brazilian Society of Computational and Applied Mathematics, 1(1).
Delahaye, J.-P. (2006). The science behind sudoku. Scientific American, 294(6):80–87.
Gouveia, T. and Maciel Jr, P. D. (2013). Técnicas de coloração de grafos aplicadas à resolução de quebra-cabeças do tipo sudoku. In Congresso Norte Nordeste de Pesquisa e Inovação, page 1.
Martí, R., Moreno-Vega, J. M., and Duarte, A. (2010). Advanced multi-start methods. In Handbook of metaheuristics, pages 265–281. Springer.
Rabuske, M. (1992). Introdução a Teoria dos Grafos. Série didática. Editora da UFSC.
Sipser, M. (2012). Introduction to the Theory of Computation. Cengage learning.
Takano, K., de Freitas, R., and de Sá, V. (2015). O jogo de lógica sudoku: modelagem In Anais do teórica, np-completude e estratégias algorítmicas exatas e heurísticas. XXXIV Concurso de Trabalhos de Iniciação Científica da SBC, pages 71–80. SBC.
Thirer, N. (2012). About the fpga implementation of a genetic algorithm for solving sudoku puzzles. In 2012 IEEE 27th Convention of Electrical and Electronics Engineers in Israel, pages 1–3. IEEE.
Yato, T. and Seta, T. (2003). Complexity and completeness of finding another solution IEICE transactions on fundamentals of electronics, and its application to puzzles. communications and computer sciences, 86(5):1052–1060.
Borges, S., Lima, T., and Marques, V. (2016). Coloração de grafos aplicado na resolução do sudoku.
Chel, H., Mylavarapu, D., and Sharma, D. (2016). A novel multistage genetic algorithm approach for solving sudoku puzzle. In 2016 International Conference on Electrical, Electronics, and Optimization Techniques (ICEEOT), pages 808–813. IEEE.
De Souza, S. S. and Romero, R. (2013). Metaheurísticas simulated annealing e busca tabu aplicadas na resolução do quebra-cabeça sudoku. Proceeding Series of the Brazilian Society of Computational and Applied Mathematics, 1(1).
Delahaye, J.-P. (2006). The science behind sudoku. Scientific American, 294(6):80–87.
Gouveia, T. and Maciel Jr, P. D. (2013). Técnicas de coloração de grafos aplicadas à resolução de quebra-cabeças do tipo sudoku. In Congresso Norte Nordeste de Pesquisa e Inovação, page 1.
Martí, R., Moreno-Vega, J. M., and Duarte, A. (2010). Advanced multi-start methods. In Handbook of metaheuristics, pages 265–281. Springer.
Rabuske, M. (1992). Introdução a Teoria dos Grafos. Série didática. Editora da UFSC.
Sipser, M. (2012). Introduction to the Theory of Computation. Cengage learning.
Takano, K., de Freitas, R., and de Sá, V. (2015). O jogo de lógica sudoku: modelagem In Anais do teórica, np-completude e estratégias algorítmicas exatas e heurísticas. XXXIV Concurso de Trabalhos de Iniciação Científica da SBC, pages 71–80. SBC.
Thirer, N. (2012). About the fpga implementation of a genetic algorithm for solving sudoku puzzles. In 2012 IEEE 27th Convention of Electrical and Electronics Engineers in Israel, pages 1–3. IEEE.
Yato, T. and Seta, T. (2003). Complexity and completeness of finding another solution IEICE transactions on fundamentals of electronics, and its application to puzzles. communications and computer sciences, 86(5):1052–1060.
Publicado
14/09/2021
Como Citar
LAURINDO, Luís Eduardo Costa; SILVA E SILVA, Francisco José da.
SaturBFS: Um Algoritmo de Coloração de Grafos para Resolução do Sudoku. In: ESCOLA REGIONAL DE COMPUTAÇÃO DO CEARÁ, MARANHÃO E PIAUÍ (ERCEMAPI), 9. , 2021, Quixadá.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2021
.
p. 74-81.
DOI: https://doi.org/10.5753/ercemapi.2021.17910.
