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

Abstract

This work presents the implementation and comparative analysis of three approaches applied to the N-Queens and Knight’s Tour combinatorial problems: Backtracking, Genetic Algorithms, and Greedy Search based on Warnsdorff’s heuristic. All solutions were implemented in C++ and independently evaluated in terms of execution time, success rate, and computational effort. In the Knight’s Tour on an 8 × 8 board, Warnsdorff’s heuristic achieved the best practical performance, with a success rate above 95% and average execution time below 1 ms. Backtracking reached 100% success, although with significantly higher search cost. The Genetic Algorithm obtained a success rate of approximately 50%, while the simple greedy version did not produce complete solutions. In the N-Queens problem (N = 8), both Backtracking and the Genetic Algorithm achieved 100% success, with execution times of only a few milliseconds. These results highlight the complementarity among exact, heuristic, and metaheuristic paradigms, supporting the selection of suitable techniques in combinatorial optimization and in educational settings focused on algorithm design.