I played my first PC CD-ROM game The 7th Guest when I was 11 years old. Other than the "insane" graphics it had at the time the game also has many interesting puzzles. And one of them is the Eight Queens puzzle.
The goal of the Eight Queue puzzle is to place eight queens on the board in a way that no queen can attack any of the others.
It took me very long time to solve the puzzle in the game. I remembered that after I proudly announced my achievement to my dad, he replied me with an evil grin that someone has already written a computer program that is capable of finding multiple solutions to the puzzle in seconds. And at that very moment, I knew exactly what I will be doing when I grow up...
Biology is one of my favourite topics in college and Genetic Algorithm is based on one of the most widely accepted theory in biology - the Theory of Evolution.
The general idea of the theory is very simple. In the process of natural selection, organisms that are more fit to their environment are more likely to survive therefore pass on their genes to future generations. As a result the overall gene pool of the population will get more and more fit to their environment over time. You can read more about the theory on Wikipedia if you are interested.
The genetic algorithm implemented in this specific case "breeds" 2D arrays. Each item in the 2D array represents a 2D coordinate of the Queen on the chess board. You can think of the array as DNA. Each coordinate in the array is a gene and the entire collection of the array is the population.
The fitness of each array (DNA) is calculated by counting the total number of coordinates (genes) in the array that meet the condition of the Eight Queen rule. i.e. they cannot attack each other. Higher fitness will give the DNA more chance of breeding with others (this is an extremely simplified biology model, so yes, DNA can breed by themselves!).
Multiple iterations of breeding will be performed. At the end of each iteration a new generation of DNA will be born. Over time the fitness of the population should increase and eventually we should get a DNA with fitness of eight and that DNA is our solution to the Eight Queens puzzle.
You can try to solve the puzzle yourself. Click on an empty grid to place a queen. Click on a existing queen to remove it.
Click on the Solve with GA button to let the computer do the work.
You can play around with the population size and the mutation rate to see their impact on the performance. Please note that I'm not responsible for your power bill if you used a ridiculously large population size :)
Not much technical details to say about this simple GA demo. It is written in pure client side JavaScript, HTML and CSS. No 3rd party framework or tool is used. The project was done back in 2017 and it only took a couple of days to complete.
Also I want to thank The Coding Train for the great video tutorial on Genetic Algorithm. You should definitely check out his YouTube channel if you are passionate about coding.
As always, I'd love your feedback. Send me an email or leave me a message on LinkedIn or Blogger.