Solving N Queens problem by implementing Genetic/Memetic Algorithm with Python.
Placing n queens in a n*n table in a way that no two threaten each other.
Single integer n, indicating the size of the chess table.
Using Genetic/Memetic Algorithm, it finds one way of placing n chess queens in the n*n table in a way that no two queens threaten each other.
Here, we'll generate some ways of placing the queens in the table. Of course many of them will threaten each other; So the goal is to minimize this cost function.
Here, every genome (answer) is stored as a permutation of numbers 1 to n: The i-th number represents the number of the column of the queen in i-th row. (Note that, no two queens can be in a same row or the same column.) So this code is pretty similar to the code I've written for TSP, here.
Function crossover inputs 2 permutations, and randomly returns one crossover (child) of those two permutations.
Function cost inputs one permutation (which represents an answer, ) then returns the number of pairs of queens which threaten each other.
Integer m in the code represents the number of the population held in every generation.
List gen stores the answers of the current generation.
mRate represents the "Mutation Rate".
The main loop iterates the generations.
Outputs the corresponding permutation, and an image for better visual understanding.
At first level, it randomly generates some permutations, and let them evolve for a little bit (Not long.) Then it saves this "little evolved" population. Then again, it generates some random permutations, and again let that evolve for a little and so on... It repeats this process several times. So, this prevents the populations to get "narrow".
At second and levels above, it randomly chooses from the previous level (just like first level, but instead of generating new permutations, it chooses from previous level.) And let them evolve a little bit but not much! And so on...
I got this idea from the structure of Segment Tree:
This makes it like hydraulic press! It's slower, but it will penetrate through the hardest of problems!
Here's it solve this problem for n = 1000 (In 12 Minutes):
The solution (permutation) for n = 1000 is present in the notebook.