Open AccessSaturBFS: Um Algoritmo de Coloração de Grafos para Resolução do Sudoku
Author(s) -
Luís Eduardo Costa Laurindo,
Francisco José da Silva e Silva
Publication year - 2021
Language(s) - Portuguese
Resource type - Conference proceedings
DOI - 10.5753/ercemapi.2021.17910
Subject(s) - physics , humanities , combinatorics , mathematics , philosophy
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.