N-Queens Problem in C++: Backtracking vs. Brute Force Algorithms

How can N queens be distributed on an N*N board without attacking each other? This program shows all the possible solutions. A solution with the backtraking algorithm and another algorithm using optimized brute force.

HISTORY

• Version 2 – 23-IV-2024
  • The code is updated to the new C++ 17 standard
  • Std::setfill and std::setw are used instead of the old gotoxy, to make the code more portable. In such a way that conio.h is dispensed with
  • Pauses are no longer inserted after showing each solution
  • Function parameters are ordered to constants, to indicate that the variables passed as reference parameters will not be modified
  • Now the solutions found are saved in a vector, to show them later. In this way it will be possible to measure the time it takes for the algorithm just to find the solutions.
  • Addons.h is included to measure the time it takes for the algorithm to find the solutions, and then display this time on the screen.
  • A pause is placed before showing the solutions or the option to exit the program is given
  • The credits and version history are updated
  • The credits and history are partially translated from Spanish to English
  • A more optimized solution is added using the backtraking algorithm, in order to compare the time vs the optimized brute force algorithm. The times, number of solutions and solution report of each algorithm are shown separately, so that they can be compared face to face.
  • RESULTS:
    • For 8 queens the following results were obtained:
    • With the 1999 average performance CPU it took 52 seconds with the “optimized brute force” algorithm.
    • With an average performance CPU of 2024 it takes 0.03 seconds and 0.0003 seconds, with the “backtraking” and “optimized brute force” algorithms respectively.
    • For 11 queens and with an average performance CPU of 2024: it took 0.03 seconds and 79 seconds, with the with the “backtraking” and “optimized brute force” algorithms respectively.
    • For 15 queens and with an average performance CPU of 2024: It took 45.52 seconds, with the “backtraking” algorithm.
• Version 1.9 – 26-VI-1999
  • First version for Borland C++ 3.1 and Turbo C 3.0
  • The new algorithm that I use consists of using permutations, that is to say it is known that to each queen corresponds a row of the board of N*N, so that to find all the solutions, it will be enough to permute the rows and in each permutation to verify if there is no attack, if the previous thing is fulfilled the current position of the queens is a solution.
  • The function Nreinas is in charge of permuting the queens, using recursion and using 2 “accelerators”, which select the permutations with non-repeated elements, thus accelerating the process wonderfully. Unlike the previous version that took 15 minutes for 8 queens, now it does it in 52 seconds (without pauses).