Uma Abordagem para o Knight’s Tour Problem utilizando Depth First Search - Yui, Bruno Kenzo; Bertho, Gabriel Andreazi; Barcelos, Karen Ketlyn Ferreira; Yamauchi, Rodrigo Takizawa; Guardia, Helio Crestana (Anais da Escola Regional de Alto Desempenho de São Paulo (ERAD-SP), 2025)
Knight’s Tour é um problema clássico da teoria dos grafos e da otimização combinatória, no qual um cavalo deve percorrer um tabuleiro de xadrez e visitar cada casa exatamente uma vez. Este artigo apresenta uma abordagem para o problema baseada em Depth First Search (DFS) e outra usando método de Monte Carlo para explorar possíveis passeios do cavalo, e analisa suas complexidades computacionais e eficiências. Além disso, discutimos otimizações heurísticas, como a Regra de Warnsdorff, para melhorar o desempenho da busca. Os resultados demonstram a viabilidade do uso de DFS para resolver esse problema NP-difícil.