This page presents a Javascript program that solves the N-Queens problem using a very simple Genetic Algorithm.

Genetic Algorithm pseudocode:
1) Create random individuals and compute fitness value.

2) For each generation:
   2.1) Catastrophe? (first 10% of generations are catastrophe-free; catastrophe probability: 5%)
        2.1.1) Remove all individuals.
        2.1.2) Create random individuals and compute fitness value.

    2.2) Keep top 10% individuals (based on fitness) and remove the others.

    2.3) Create new individuals by mutating the remaning (swap Queen positions).

    2.4) For each individual:
         2.4.1) Compute new fitness value based on the number of collisions between Queens.
         2.4.2) Fitness value is zero? (no collisions)
       Solution Found.

Each individual is a group of (x,y) coordinates that represent the position of each Queen on the board. Individual 1324 means that the Queens positions are (1,1) (2,3) (3,2) (4,4).

   1 2 3 4 (x)
 1 Q . . .
 2 . . Q .
 3 . Q . .
 4 . . . Q





Y Axis: score (lower is better), X Axis: Generation Number.


Source Code

All the source code is online here.


blog comments powered by Disqus
Fork me on GitHub