Análise comparativa de técnicas de projeto de algoritmos aplicadas aos problemas das N-Rainhas e do passeio do cavalo

Este trabalho apresenta a implementação e a análise comparativa de três abordagens aplicadas aos problemas combinatórios das N-Rainhas e do Passeio do Cavalo: Backtracking, Algoritmos Genéticos e uma Busca Gulosa que inclui um experimento adicional com a heurística de Warnsdorff. Todas as soluções foram desenvolvidas em C++ e avaliadas de forma independente quanto ao tempo de execução, taxa de sucesso e esforço computacional. No Passeio do Cavalo, a versão gulosa simples não obteve sucesso, enquanto a heurística de Warnsdorff, utilizada como experimento complementar, apresentou o melhor desempenho prático, com alta taxa de sucesso e tempo de processamento muito baixo. O Backtracking também encontrou soluções completas, porém com maior custo de busca. O Algoritmo Genético apresentou desempenho intermediário, com taxa de solução inferior à do Backtracking, refletindo a sensibilidade do método à parametrização e ao domínio do problema. No problema N-Rainhas (N = 8), o Backtracking atingiu alta taxa de desempenho com 100% de sucesso, enquanto o Algoritmo Genético obteve resultados elevados, com 100% de sucesso e convergência em poucos milissegundos. Esses resultados reforçam a complementaridade entre paradigmas exatos, heurísticos e metaheurísticos, auxiliando na escolha de técnicas adequadas em contextos de otimização combinatória e no ensino de projeto de algoritmos.