8 QUEENS PROBLEM SOLUTION USING GENETIC ALGORITHM

There are optimization problems that couldn't be solved using classical bit-string chromosome approach. The 8 queens problem gives us the simple and clear example of such kind problems. Problem is how to place 8 queens on an ordinary chess board so that none of them can hit any other in one move.


ENCODING


Since classical recombination and mutation operators don't preserve the number of bits we need to make their analogues suitable for this particular case. I think that the most simple 'chromosome' for 8 queens problem is the array holding queens positions (integer numbers from 0 to 63 for 8x8 chess board). For example:


example of queens chromosome

MEASURING FITNESS

Naturally here, fittest 'chromosomes' are those with smaller total number of queens under attack. To evaluate fitness of 'chromosome' we execute this simple algorithm: For each queen in chromosome we calculate number of queens sharing the same row, column and diagonal. Since relation 'being attacked' is symmetric and total number of queens being attacked always will be even we may divide it by 2. And at last we need to negate fitness value, because our algorithm is suited for maximization. For example, above chromosome {2,0,55,48,16,28,62,38} has fitness: -10.

MUTATION

To mutate 'queen' chromosome at nth position (locus) we simply move nth queen to randomly selected unoccupied position. For example, let mutate our sample chromosome at 4th position (counting from 0):

mutation

CROSSOVER

Crossover is more sophisticated procedure. We take two parent chromosomes and put all genes (avoiding duplicates) to one combined chromosome (1st gene comes from 1st parent, 2nd - from 2nd parent, 3rd again from 1st parent and so on). the length of combined chromosomes ranges from 8 to 16 (parents have no common genes) . After combined chromosome is created we copy the first 8 genes from the beginning to first offspring. Other offspring receives the last 8 genes of combined chromosome:
The case where parents has no common genes:


crossover

The case when parents has some common genes:


crossover

 

And situation when combined chromosome offsprings are identical:


crossover


CROSSOVER EXAMPLE


Results of modeling:


optimal object



Base classes for genetic algorithm may be downloaded here.
VB.NET chromosome class implementation for 8 queens problem:

 
Imports System.Collections.Generic
Imports BaseGA5.GeneticAlgorithm


Public Class QueenChromosome : Implements IChromosome

#Region "Local Variables"
    Private Shared _symbols() As String = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P"}
    Private Const _Undefined As Integer = -1
    Private _NQ As Integer = 8
    Private _MaxCol As Integer = 8
    Private _MaxRow As Integer = 8
    Private _N As Integer
    Public _queens As List(Of Integer)
    Public _histogram As List(Of Integer)
    Private Shared _random As Random = New Random((DateTime.Now.Hour * 3600 + DateTime.Now.Minute * 60 + DateTime.Now.Second) * 1000 + DateTime.Now.Millisecond)
#End Region


    Public Sub New(ByVal maxCol As Integer, ByVal maxRow As Integer, ByVal NQ As Integer)
        If maxCol > 16 Then
            Throw New Exception(String.Format("Numebr of columns is out of range. Must be < 17"))
        End If
        _MaxCol = maxCol
        _MaxRow = maxRow
        _N = _MaxRow * _MaxCol
        _NQ = NQ
        _queens = CreateList(_NQ, _Undefined)
        _histogram = CreateList(_N, 0)
    End Sub

    Private Function CreateList(ByVal N As Integer, ByVal value As Integer)
        Dim o As New List(Of Integer)(N)
        While N > 0
            o.Add(value)
            N -= 1
        End While
        Return o
    End Function


    Public Sub RandomInit() Implements IChromosome.RandomInit
        Dim N As Integer = _NQ
        While N > 0
            Dim pos As Integer = _random.Next(0, _N)
            If Not _queens.Contains(pos) Then
                _queens(N - 1) = pos
                N -= 1
            End If
        End While
    End Sub


    Private Sub doCopy(ByVal dest As QueenChromosome, ByVal src As QueenChromosome)
        For j As Integer = 0 To _NQ - 1
            dest._queens(j) = src._queens(j)
        Next
    End Sub

    Public Sub Copy(ByVal dest As IChromosome) Implements IChromosome.Copy
        doCopy(dest, Me)
    End Sub

    Public Function ValidPosition(ByVal r As Integer, ByVal c As Integer) As Boolean
        Return (r >= 0 And r < _MaxRow) AndAlso (c >= 0 And c < _MaxCol)
    End Function

    Private Function ChangePosition(ByVal oldPos As Integer) As Integer
        Dim newPos As Integer = 0
        While True
            newPos = _random.Next(0, _N)
            If Not _queens.Contains(newPos) Then
                Return newPos
            End If
        End While
        Return _Undefined
    End Function


    Public Sub MutateAt(ByVal locus As Integer) Implements IChromosome.MutateAt
        _queens(locus) = ChangePosition(_queens(locus))
    End Sub

    Public Function ValidLocus(ByVal locus As Integer) As Boolean Implements IChromosome.ValidLocus
        Return locus >= 0 AndAlso locus < _NQ
    End Function

    Public Sub Validate()
        For j As Integer = 0 To _N - 1
            _histogram(j) = 0
        Next
        For Each pos As Integer In _queens
            If (pos < 0) Or (pos >= _N) Then
                Throw New Exception(String.Format("Invalid queen position {0}.", pos))
            End If
            If _histogram(pos) <> 0 Then
                Throw New Exception(String.Format("Duplicate queen position {0}.", pos))
            End If
        Next
    End Sub

    Private Sub doCrossOver(ByVal dad As QueenChromosome, ByVal mom As QueenChromosome, ByVal offspring1 As QueenChromosome, ByVal offspring2 As QueenChromosome)

        Dim qjoined As New List(Of Integer)

        For j As Integer = 0 To _NQ - 1
            If Not qjoined.Contains(dad._queens(j)) Then
                qjoined.Add(dad._queens(j))
            End If
            If Not qjoined.Contains(mom._queens(j)) Then
                qjoined.Add(mom._queens(j))
            End If
        Next


        Dim N As Integer = qjoined.Count
        If N < _NQ Or N > _NQ * 2 Then
            Throw New Exception(String.Format("Invalid number of queens ({0}) in joined list.", N))
        End If

        For j As Integer = 0 To _NQ - 1
            Dim pos As Integer = qjoined(j)
            offspring1._queens(j) = pos
            pos = qjoined(j + N - _NQ)
            offspring2._queens(j) = pos
        Next

    End Sub


    Public Sub CrossOver(ByVal mom As IChromosome, ByVal offspring1 As IChromosome, ByVal offspring2 As IChromosome) Implements IChromosome.CrossOver
        doCrossOver(Me, mom, offspring1, offspring2)
    End Sub


    Public Sub GetRowCol(ByVal pos As Integer, ByRef row As Integer, ByRef column As Integer)
        row = pos \ _MaxCol
        column = pos Mod _MaxCol
    End Sub

    Public Function GetPosition(ByVal r As Integer, ByVal c As Integer) As Integer
        Return r * _MaxCol + c
    End Function

    Public Function GetRow(ByVal pos As Integer) As Integer
        Return pos \ _MaxCol
    End Function

    Public Function GetCol(ByVal pos As Integer) As Integer
        Return pos Mod _MaxCol
    End Function

    Public Function GetSymbolic(ByVal pos As Integer) As String
        Return String.Format("{0}{1}", _symbols(pos Mod _MaxCol), (pos \ _MaxCol) + 1)
    End Function


    Public Function EvalFitness() As Double
        Dim sum As Double = 0
        For Each pos As Integer In _queens
            'Debug.WriteLine(String.Format("{0} --> {1};{2}", _queens(j), row, col))
            sum += OnSameColumn(pos)
            sum += OnSameRow(pos)
            sum += OnSameDiagonal(pos)
        Next
        'Debug.WriteLine(String.Format("Sum={0}", sum))
        Return sum
    End Function


    Private Function OnSameRow(ByVal pos As Integer) As Integer
        Dim sum As Integer = 0
        Dim row As Integer = GetRow(pos)
        For Each q As Integer In _queens
            sum += IIf((q \ _MaxCol) = row, 1, 0)
        Next
        Return sum - 1
    End Function

    Private Function OnSameColumn(ByVal pos As Integer) As Integer
        Dim sum As Integer = 0
        Dim col As Integer = GetCol(pos)
        For Each q As Integer In _queens
            sum += IIf((q Mod _MaxCol) = col, 1, 0)
        Next
        Return sum - 1
    End Function

    Private Function OnSameDiagonal(ByVal pos As Integer) As Integer
        Dim sum As Integer = 0
        Dim row As Integer = GetRow(pos)
        Dim col As Integer = GetCol(pos)

        For Each q As Integer In _queens
            sum += IIf(Math.Abs(GetRow(q) - row) = Math.Abs(GetCol(q) - col), 1, 0)
        Next
        Return sum - 1
    End Function

End Class

 

Genetic algorithm specialization:

 
Imports System.Collections.Generic
Imports BaseGA5.GeneticAlgorithm


Public Class QueenGA : Inherits BaseGeneticAlgorithm(Of QueenChromosome)

    Private _crossoverP As Double = Double.NaN
    Private _mutateP As Double = Double.NaN
    Private _maxiter As Integer = 100
    Private _sideSize As Integer = 8
    Private _NQ As Integer = 8

    Public Event BestObject(ByVal sender As Object, ByVal obj As QueenChromosome)


    Public Sub New(ByVal SideSize As Integer, ByVal NQ As Integer, ByVal maxiter As Integer, ByVal crossoverP As Double, ByVal mutateP As Double)
        _sideSize = SideSize
        _NQ = NQ
        _maxiter = maxiter
        _crossoverP = crossoverP
        _mutateP = mutateP
    End Sub

    Public Function PickBestObject(ByVal population As IEnumerable(Of QueenChromosome)) As QueenChromosome
        Dim maxf As Double = Double.MinValue
        Dim o As QueenChromosome = Nothing
        For Each obj As QueenChromosome In population
            Dim value As Double = GetFitness(obj)
            If value > maxf Then
                maxf = value
                o = obj
            End If
        Next
        Return o
    End Function

    Protected Overrides Function CanStop(ByVal iteration As Integer, ByVal population As System.Collections.Generic.List(Of QueenChromosome)) As Boolean
        Debug.WriteLine(String.Format("Iteration={0}", iteration))
        Dim o As QueenChromosome = PickBestObject(population)
        If o IsNot Nothing Then
            Dim ftn As Integer = o.EvalFitness()
            Debug.WriteLine(String.Format("Sum={0}", ftn))
            RaiseEvent BestObject(Me, o)
            Return (iteration >= _maxiter) Or (ftn = 0)
        End If
        Return True
    End Function

    Public Overrides Function CreateChromosome() As QueenChromosome
        Return New QueenChromosome(_sideSize, _sideSize, _NQ)
    End Function

    Public Overrides Function EvalFitness(ByVal obj As QueenChromosome) As Double
        Return obj.EvalFitness()
    End Function

    Protected Overrides Function PerformCrossover() As Boolean
        Return _random.NextDouble <= _crossoverP
    End Function

    Protected Overrides Function PerformMutate() As Boolean
        Return _random.NextDouble() <= _mutateP
    End Function

End Class
   

Download source code.

Download video clip illustrating algorithm in progress.

LINKS:
N Queens Problem
Eight Queens Puzzle
The N-Queens Problem
Graphical Solution to eight queen problem
The Queen's Problem
All Solutions To The Problem of Eight Queens