SaturBFS: Um Algoritmo de Coloração de Grafos para Resolução do Sudoku - Laurindo, Luís Eduardo Costa; Silva e Silva, Francisco José da (Anais da Escola Regional de Computação do Ceará, Maranhão e Piauí (ERCEMAPI); 2021: Anais da IX Escola Regional de Computação do Ceará, Maranhão e Piauí, 2021)
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.