SaturBFS: Um Algoritmo de Coloração de Grafos para Resolução do Sudoku
Abstract
This study proposes a graph coloring algorithm called Saturated Breadth-First Search (SaturBFS) to determine valid Sudoku solutions. The algorithm was conceived by combining the Breadth-First Search (BFS) and DSatur algorithms. The objective is to perform a comparative analysis of SaturBFS with unsaturated BFS and Depth-First Search (DFS) algorithms for different levels (easy, medium and hard) and Sudoku instances (4x4, 6x6, 8x8, 9x9, 10x10 and 12x12). For the evaluation, the time that the algorithms take to determine a valid solution and the percentages of valid solutions found were considered. The SaturBFS algorithm showed a higher percentage of valid solutions found in a shorter time.References
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.
Published
2021-09-14
How to Cite
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: REGIONAL SCHOOL ON COMPUTING OF CEARÁ, MARANHÃO, AND PIAUÍ (ERCEMAPI), 9. , 2021, Quixadá/CE.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2021
.
p. 74-81.
DOI: https://doi.org/10.5753/ercemapi.2021.17910.
