The N_Queens problem is a classic problem that lends itself to local search algorithms. In this problem, N queens are placed on an N × N chessboard, one queen per column. We assume that each queen can only move vertically (Up or Down) within her residence column. You can find more information about the problem in this Wikipedia article. An example solution for an 8 x 8 chessboard is shown:
The N_Queens.py file contains python solution codes for several algorithms that try to solve the problem. These algorithms are explained below.
To represent the place of all queens, a one-dimensional array with N columns is created. In this array, columns are indexed from 0 to N-1, and each column contains a single number that describes the row location of the residing queen in that column.
To evaluate each state of the board, first, the maximal number of queen pairs in conflict is calculated as follows:
Maximum conflicts = 1 + 2 + ... + N-1 = (N-1 × N) / 2
Since the algorithms are doing ascending search, the evaluation score of each board is thus:
Evaluation Score = Maximum conflicts - Total current conflict pairs
At last, the program ends when the maximum evaluation score (which is just the number of Maximum conflicts) is reached. Since the algorithms might get stuck in the local optimum, if the global optimum is not found, the program ends after 1000 iterations. Afterward, the resulting board, evaluation score, and a graph demonstrating the evaluation score during iterations are shown.
In a random algorithm, the queen of each column is placed in a random row on each iteration. The success rate of this algorithm is relatively low, especially if N is large.
In this algorithm, the queen of each column is placed in a random row on each iteration. In this for loop, if the relocated queen decreases the evaluation score, the row number of the queen in that particular column is restored to the previous row number. We might move a queen into another row with the evaluation score remaining the same. This way, we can change the board without decreasing the score and possibly make way for other changes that can further increase the evaluation score. If the algorithm is stuck at the local optimum, this subtle move could be a determining factor in avoiding the local optimum. In a graphical view, this move is like jumping from the top of the local hill to the hillside of another hill at the same height (Evaluation Score)!
This algorithm is an upgrade to the Optimised Random Search algorithm. If the evaluation score of the new board is higher or equal to the original board, the changes are implemented on the original board. However, if the evaluation score is decreased, the changes are applied to the original board with some probability. Since the algorithm here tries to find the global maximum, this probability is calculated as follows:
Here, e is the Euler's number, ∆S is the change in evaluation score (Negative since the evaluation score has decreased), and T is Temperature. Temperature is just a fancy word for a variable that decreases after each iteration. Thus, this number is high in primary iterations, and the probability of accepting decreasing new boards is high. On the contrary, as T decreases, the probability of accepting decreasing new boards decreases, as if the algorithm stops sudden changes and focuses on reaching the local ahead. Note that, in general, worse new boards which drastically reduce the evaluation score are less likely to be accepted.
P.S. Note that the new evaluation score must be higher or equal to the original board in order to accept new changes. In some algorithms, this condition is only noted as higher; however, the author believes accepting equal recent evaluation scores will result in a higher probability of escaping the local optimum.
This algorithm is, in a sense, heuristic, as we perform the best move on each iteration. That is, we calculate the evaluation score of all possible new boards in which the location of a single queen has changed. Then, the new board of maximum evaluation scores is chosen, and the changes are applied to the original board. If there exists more than one new board having a maximum evaluation score, the first one found is used due to using python's built-in max function.
This algorithm is not efficient and has a high order time complexity. Furthermore, it is pretty vulnerable to local optimums. In general, on each iteration, we make the best move (Climb one step up the hill), and we stop when there is no better move than our current move (Stop at the optimum). This way, we can easily find an optimum; however, we cannot avoid local optimums.
This algorithm is an add-on to Hill Climbing to decrease the chance of getting stuck in local optimums. On each iteration, with a constant probability of 23%, instead of following hill climbing, 2 random queens are chosen and are moved to random rows. This subtle change enables the algorithm to "shake" itself once in a while and hopefully avoid some local optimums.
The reason behind 23% probability and 2 random queens is discussed in the Discussion file.
This algorithm is an add-on to Hill Climbing to decrease the chance of getting stuck in local optimums. By somehow combining the idea of hill climbing with simulated annealing, on each iteration, with a changing probability, instead of following hill climbing, 2 random queens are chosen and are moved to random rows. This subtle change enables the algorithm to "shake" itself once in a while and hopefully avoid some local optimums. This changing probability is calculated as follows:
P.S. In this algorithm, temperature only decreases when the algorithms have done hill climbing (instead of random chance). This will increase the probability of success by avoiding the local optimum.
In another attempt, the algorithm is changed to avoid local optimums. This algorithm has memory. It stores the evaluation score of the previous board and the current board. If these two scores are equal, it means the algorithm is stuck in the local optimum, and thus instead of following hill climbing, 4 random queens are chosen and are moved to random rows. This modification enables the algorithm to move randomly to another state when stuck in the local optimum
The reason behind 4 random queens is discussed in the Discussion file.
Another interesting algorithm to solve the N_Queens problem is the Genetic Algorithm. To keep this article short, this algorithm is not included in the python file. The code and explanation of this algorithm can be found here.
Two parameters needed some experimentation to come up with. One is the probability of acting random (P), and the other is the number of queens changed in a random action (Q). Based on the following results, 23% and 2 were the most valuable numbers. Interestingly, as the number of queens (N) increased, the number of queens which should change in a random iteration (Q) stayed the same. The author believes that as N increases, there is a need for more queens to change, but at the same time, each queen affects a higher number of relationships with other queens, and thus, there would not be any need to increase Q. In other words, each queen is more valuable and satisfies our need for a more dramatic change to the board.
A board of size 8 (N = 8) was chosen to test and find the optimum numbers. With a maximum iteration of 1000 (The program ends after 1000 tries if not successful), the mean result for 10 independent runs was recorded. In the begging, instead of experimentation with some constant number of queens, a certain percentage (%) of queens were chosen to be relocated randomly on each random iteration. The product of % and N is truncated to reach Q by the program. Prob is the probability of acting randomly (P).
Surprisingly, when N = 8, even high values of % could give acceptable results; however, high P values drastically decreased the success rate. To reach more accurate results, the same experiment was repeated with N = 16.
These new results demonstrated that in addition to a small %, P should also be small. The best results were obtained when P was around 0.1 to mid-way 0.2 - 0.3, and thus, the experiment was repeated with P ranging from 0.02 to 0.24.
Based on the results, the optimum range for % was around 0.2 - 0.3. Thus, the experiment was repeated with P ranging from 0.06 - 0.28 and % ranging from 0.125 - 0.45. Note that the product of % and N is truncated to reach an integer number of queens to be relocated randomly. Percentages pointing toward the same number are colored the same. Each result is the mean of 20 runs. The max number of iterations also decreased to 700.
Based on the above results, a percentage resulting in changing 2 queens is optimum when N = 16. However, the optimum P could not be decided due to noise from success rates obtained from large %. Thus, part of the results where 2 queens changed was sliced, and means were calculated specifically for this slice.
Finally, the optimum % was chosen to be 23% for N = 16. Although these numbers are optimums for N = 16, further experiments in the following algorithm showed almost no change is needed for further improvement in other N.
In this algorithm, since acting random is restricted to when the program is stuck in local optimum, only parameter % (Percentage of queens that are randomly relocated in a random iteration) needs to be optimized. Like the previous optimization, it was deducted that % changes according to N so that their product (N * %), which is the number of queens being randomly relocated (Q), is somehow constant. That is, even for various N, a constant number of queens should be relocated. The author believes that as N increases, there is a need for more queens to change, but at the same time, each queen affects a higher number of relationships with other queens, and thus, there would not be any need to increase Q. In other words, each queen is more valuable and satisfies our need for a more dramatic change to the board.
A board of size 8 (N = 8) was chosen to test and find the optimum numbers. With maximum iteration numbers ranging from 50 to 1000 (The program ends after these number of tries if not successful), the mean result for 20 independent runs was recorded. In the begging, instead of experimentation with some constant number of queens, a certain percentage (%) of queens were chosen to be relocated randomly on each random iteration. The product of % and N is truncated to reach Q by the program.
Note: The following format is used to represent the experiment setup: N Repeats MaximumIterations
Since the algorithm is highly successful, N = 8 could not give us intuition about how to optimize %.
In the next experiment, N was increased to 16, and this time, Maximum Iterations ranged from 250 to 1000.
Based on the results, it was concluded that the optimum % lay somewhere between 0.2 - 0.4. Most probably, a % = 0.3 which resulted in Q = 4 seemed like the best option. Q of 3 or 6 resulted in lower success rates.
Afterward, N was increased to 24, and the experiment was repeated.
The results of this experiment were quite surprising. The optimum % was 0.2, which pointed toward Q = 4! A proof that despite an 8 queen increase in numbers, the optimum algorithms still changed Q = 4 queens on random iterations.
Thus, it was concluded that % is not important; instead, Q is the determining factor. These results are in conjunction with the experiments in the "Hill Climbing + Constant Random Probability" section. Finally, to test this idea, a set of 4 experiments with N = 4, 8, 16, and 24 were conducted. To decrease the noise, the repetition of the experiments was substantially increased. It is also noteworthy that MaxIterations was decided based on the N. The following results were obtained:
N = 4, Repeats = 1000, MaxIterations(15, 18, 20)
N = 8, Repeats = 500, MaxIterations(65, 70, 75)
N = 16, Repeats = 500, MaxIterations(250, 300, 350, 400)
N = 24, Repeats = 50, MaxIterations(300, 400, 450, 500)
Based on the above results, it was confirmed that, indeed, Q is the determining factor regardless of how large N is. Also, There was not quite much difference between Q = 3 and Q = 4. However, Q = 4 stood for a higher success rate each time. It is also noteworthy that the difference between the success rate when Q = 3 and Q = 4 got smaller as N increased, pointing towards a possible hypothesis that Q = 3 might become the better option in huge N. Unfortunately, this hypothesis remains untested as of today.
To thoroughly compare the success rates of these two algorithms, 5 experiments were conducted, that is, N = 4, 8, 16, 24, 32. The number of Repeats and MaxIterations were both set to 1000. The result took quite a long to come out, as the time complexity of both these algorithms is quite high. Interestingly, the second algorithm solved the problem quicker and ended in lower Iterations.
First Algorithm (Hill Climbing + Constant Random Probability) ran with P = 23% and Q = 2. The mean success rate of over 1000 repeats is shown.
The second Algorithm (Optimised Hill Climbing) ran with Q = 4. The mean success rate of over 1000 repeats is shown.
Unfortunately, the results of the first algorithm in N = 32 took too long and eventually did not come out. However, the dominant victory of the second algorithm is apparent from lower N. The graph below represents the above numbers:
In the end, the second algorithm (Optimised Hill Climbing) showed quite high success rates even in large N. A success rate of more than 97% when N = 32 is quite mind-blowing. The only problem, however, is the low efficiency of the algorithm. As a final note, the author believes since the first algorithm plays randomly in 23% of iterations, a lower Q (Q = 2) optimized it compared with the second algorithm that, only acted randomly when stuck at local optimums and needed a higher Q (Q = 4) to be optimized. In other words, if P increases, Q is decreased, so they can somehow neutralize each other's effect for the algorithm to remain optimized.