Hace poco decidí revisitar el clásico problema de las N-Reinas, un algoritmo que implementé por primera vez en QBasic a mediados de los 90, cuando todavía estaba en el instituto. Viéndolo con perspectiva, aquella implementación era bastante mejorable, ya que estaba llena de bucles anidados y ni siquiera utilizaba recursividad.
Pocos años después, en la universidad, aprendí el enfoque clásico basado en backtracking recursivo. Ahora, 27 años más tarde, me apetecía volver a enfrentarme al mismo problema para ver hasta dónde podía llevar la optimización.
En lugar de implementar directamente la versión más rápida, decidí construir cuatro versiones diferentes. La primera es un solver de backtracking muy básico, y cada una de las siguientes versiones incorpora nuevas técnicas de optimización, hasta llegar a una implementación aproximadamente 40 veces más rápida que la inicial. Durante el proceso exploré distintas mejoras algorítmicas, optimizaciones de bajo nivel y computación paralela.
He documentado todo el proceso en un vídeo porque creo que puede resultar interesante para quienes disfrutan de los algoritmos clásicos, la optimización de rendimiento o la programación de sistemas al estilo de la vieja escuela. También me gustaría saber cómo abordaríais vosotros la optimización de un solver para el problema de las N-Reinas hoy en día.
Código fuente: https://github.com/albertnadal/n-queens-c-solver
Video: https://www.youtube.com/watch?v=vivmMFGfNbU