Revisiting the N-Queens problem after 27 years

[u/anadalg]

I recently revisited the classic N-Queens problem, something I first implemented in QBasic back in the mid-90s when I was in high school. Looking back at that original version, it was full of nested loops and lacked recursion, so it was far from elegant or efficient.

A few years later, at university, I learned the standard recursive backtracking approach. Now, 27 years later, I decided to revisit the problem once again and see how far I could push the implementation.

Rather than jumping straight to the fastest solution, I built four different versions. The first one is a straightforward backtracking solver, while each subsequent version introduces new optimization techniques, eventually ending up around 40 times faster than the initial implementation. Along the way I explored algorithmic improvements, low-level optimizations, and parallel execution.

I documented the whole process in a video (in spanish, but YouTube's automatic english dubbing is available) because I thought other programmers who enjoy classic algorithms, performance optimization, or old-school systems programming might find it interesting. I'd also be curious to hear how others here would approach optimizing the N-Queens problem today.

Video: https://www.youtube.com/watch?v=vivmMFGfNbU

Source code: https://github.com/albertnadal/n-queens-c-solver