Click here to Skip to main content
Click here to Skip to main content
Go to top

Solving Eight Queens Puzzle with Genetic Algorithm in C#

, 25 Jun 2011
Rate this:
Please Sign up or sign in to vote.
A C# code for solving eight queens puzzle using genetic algorithm

Introduction

There are several ways to solve NP-hard problems. Genetic algorithm is one easy approach to solve such kind of problems. This article is about solving 8 queens puzzle with genetic algorithm using C#.

mainView.JPG

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.

In order to use genetic algorithm, it is a must to define the crossover operator, mutation operator, chromosome and genes.

Problem Representation

Gene: A gene is a number from 0 to 7 that means the row number that a queen is located. The position of the gene in a chromosome implies the column number of the queen. It is mandatory to locate one queen per column and row because there are same number of queens and columns/rows in the board.

Chromosome: A chromosome is a set of 8 genes. It is assumed to be that no duplicate genes in a chromosome.

Example:

0|1|4|2|3|6|7|5 8 queens are located in following cells.

(0,0), (1,1), (2,4), (3,2), (4,3), (5,6), (6,7), (7,5)

Mutation: Mutation is done with swapping the gene that is to be mutated with a randomly selected gene (except the gene that is currently subjected to the mutation) from the same chromosome.

Crossover: Genes are drawn from the two parent chromosomes with the probability of 0.5. A gene is drawn from one parent and it is appended to the offspring chromosome. The corresponding gene is deleted in the other parent. This step is repeated until both parent chromosomes are empty and the offspring contains all genes involved.

Fitness Function: A collision is two queens who are able to attack each other. This means they are in the same diagonal, the same row or the same column. Since the chromosome has no duplicate genes and it guarantees that 2 queens are not in a single column it is only needed to calculate the diagonal collisions. Therefore maximum number of collisions that can occur is 28. The fitness function is a higher-is-better function, so calculate it by subtracting the amount of collisions that occur in the current state from 28. A solution would have 0 collisions and thus a fitness of 28.

Using the Code

Classes and Structures

  • class GeneticAlgo: The class that is responsible for all the operations of genetic algorithm.
  • class FitnessComparator: A comparator class to sort chromosomes with fitness value in order to show the final population in the table.
  • struct Chromosome: The structure that represents a chromosome which include genes, fitness and its cumulative of average fitness.
  • class MainFrame: The class that responsible for handling user interface and create initial population in order to pass to the genetic algorithm.
  • class Board: The class that is responsible for graphical view and operations of the chess board.

Variables

  • private const int MAX_FIT = 28; holds the maximum fitness.

Functions

private List<chromosome> GetInitialPopulation(int population)
{
	List<chromosome> initPop = new List<chromosome>();
	GeneticAlgo RandomGen = new GeneticAlgo();
	for (int i = 0; i < population; i++)
	{
		List<int> genes = new List<int>(new int[] {0, 1, 2, 3, 4, 5, 6, 7});
		Chromosome chromosome = new Chromosome();
		chromosome.genes = new int[8];
		for (int j = 0; j < 8; j++)
		{
			int geneIndex = (int)(RandomGen.GetRandomVal
				(0,genes.Count-1)+0.5);//randomly select a gene
			chromosome.genes[j] = genes[geneIndex];
			genes.RemoveAt(geneIndex);//remove selected gene
		}

		initPop.Add(chromosome);
	}
	return initPop;
} 

This function takes the size of population as the parameter and returns a list of chromosomes that contain randomly generated genes. The values of genes are randomly selected from a list that contains 0 to 7. While selecting the values from the list, the selected values are removed to avoid the duplication of genes in a chromosome. The size of the list is equal to the size of population. After creating the initial population using this function, the returned list of chromosomes sends to the function DoMating.

public void DoMating(ref List<Chromosome> initPopulation, 
	int generations, double probCrossver, double probMutation)
{
	int totalFitness = 0;
	CalcFitness(ref initPopulation, ref totalFitness);            

	for (int generation = 0; generation < generations; generation++)
	{                
		PrepareRuletteWheel(ref initPopulation,totalFitness);
		Crossover(ref initPopulation, probCrossver);
		Mutate(ref initPopulation, probMutation);
		CalcFitness(ref initPopulation, ref totalFitness);                
		if (initPopulation[initPopulation.Count - 1].fitness == 28)
			break;
		if (progress != null)
		{
			progress(generation + 1);
		}
	}
	initPopulation.Sort(new FitnessComparator());
}  

This function takes a list of chromosomes as the initial population, number of generations that we are willing to propagate in the algorithm, the crossover probability and the mutation probability as its parameters. The responsible of this function is to handle the propagation to the required generation by invoking the functions CalcFitness, PrepareRuletteWheel, Crossover and Mutate.

public void CalcFitness(ref List<Chromosome> chromosome, ref int totalFitness)
{
	int collisions = 0;
	totalFitness = 0;
	for (int k = 0; k < chromosome.Count; k++)
	{
		for (int i = 0; i < chromosome[k].genes.Length - 1; i++)
		{
			int x = i;
			int y = chromosome[k].genes[i];
			for (int j = i + 1; j < chromosome[k].genes.Length; j++)
			{
				if (Math.Abs(j - x) == Math.Abs
					(chromosome[k].genes[j] - y))
					collisions++;                        
			}
		}
		
		Chromosome temp = chromosome[k];
		temp.fitness = MAX_FIT - collisions;
		chromosome[k] = temp;
		totalFitness += chromosome[k].fitness;
		collisions = 0;
	}
}

This function calculates the fitness of each chromosome and assigns the fitness value to the property fitness of each chromosome. The fitness is calculated by counting the number of collisions and deduct it from the maximum number of collisions because in this code the fitness is a higher-is-better function. While calculating the fitness for each chromosome, this function also calculates the total fitness of the population because we need it in the next step to calculate the fitness ratio of each chromosome.

private void PrepareRuletteWheel(ref List<Chromosome> parents,int total)
{
	int currentTotalFitness=0;
	for (int i = 0; i < parents.Count; i++)
	{
		currentTotalFitness += parents[i].fitness;
		Chromosome temp = parents[i];
		temp.cumAvgFitness = currentTotalFitness / (double)total;
		parents[i] = temp;
	}
}

A rulette wheel that is based on the fitness of chromosome is used for selecting parents to mate in order to generate a new generation. This function is responsible for preparing the rullette wheel and it takes a list of chromosomes as the current population and the total fitness of the population. The function calculates the ratio of fitness of each chromosome to the total fitness and then calculates the cumulative of it to assign to the property cumAvgFitness of a chromosome.

public void Crossover(ref List<Chromosome> parents, double probability)
{
	List<Chromosome> offspring = new List<Chromosome>();

	for (int i = 0; i < parents.Count; i++)
	{                
		if (Assay(probability)) //if the chance is to crossover
		{
			Chromosome parentX = AssayRuletteWheel(parents);
			Chromosome parentY = AssayRuletteWheel(parents);

			List<int> child = new List<int>();
			for (int j = 0; j < 8; j++)
			{
				if (Assay(0.5)) //select from parentX
				{
					for (int k = 0; k < parentX.genes.Length; k++) 
					{
						if (!child.Contains
						(parentX.genes[k]))//instead of 
							//deleting the similar genes
							//from parents select the 
							//next non-contained number
						{
							child.Add(parentX.genes[k]);
							break;
						}
					}
				}
				else //select from parentY
				{
					for (int k = 0; k < parentY.genes.Length; k++)
					{
						if (!child.Contains
						(parentY.genes[k]))//instead of 
						//deleting the similar genes from 
						//parents select the next 
						//non-contained number
						{
							child.Add(parentY.genes[k]);
							break;
						}
					}
				}
			}
			Chromosome offSpr = new Chromosome();
			offSpr.genes = child.ToArray();
			offspring.Add(offSpr);

		}
		else //else the chance is to clone
		{
			Chromosome parentX = AssayRuletteWheel(parents);
			offspring.Add(parentX);
		}
	}

	while (offspring.Count > parents.Count)
	{
		offspring.RemoveAt((int)GetRandomVal(0, offspring.Count - 1));
	}

	parents = offspring;
}

This function is responsible for crossing over and cloning operations. The function takes a list of chromosomes as the current population and the crossover probability as its parameters. The function Assay(int probability) returns true with the given probability, therefore it is used with the crossover probability to determine whether the operation is a crossing over or a cloning.

if (Assay(probability)) //if the chance is to crossover
{
	Chromosome parentX = AssayRuletteWheel(parents);
	Chromosome parentY = AssayRuletteWheel(parents);

	List<int> child = new List<int>();
	for (int j = 0; j < 8; j++)
	{
		if (Assay(0.5)) //select from parentX
		{
			for (int k = 0; k < parentX.genes.Length; k++) 
			{
				if (!child.Contains(parentX.genes[k]))//instead of 
					//deleting the similar genes from parents 
					//select the next non-contained number
				{
					child.Add(parentX.genes[k]);
					break;
				}
			}
		}
		else //select from parentY
		{
			for (int k = 0; k < parentY.genes.Length; k++)
			{
				if (!child.Contains(parentY.genes[k]))//instead of 
					//deleting the similar genes from parents 
					//select the next non-contained number
				{
					child.Add(parentY.genes[k]);
					break;
				}
			}
		}
	}
	Chromosome offSpr = new Chromosome();
	offSpr.genes = child.ToArray();
	offspring.Add(offSpr);
}

This part of code is from the above function and is responsible for crossover the two parents parentX and parentY. In order to create the offspring, genes are selecting from two parents with a probability of 0.5 while avoiding the gene duplication in the chromosome.

In the cloning operation, one parent is directly brought to the next generation.

public void Mutate(ref List<Chromosome> parents, double probability)
{
	List<Chromosome> offsprings = new List<Chromosome>();
	for (int i = 0; i < parents.Count; i++)
	{
		Chromosome offspring = parents[i];
		for (int mutatePosition = 0; mutatePosition < 8; mutatePosition++)
		{
			if (Assay(probability)) //if the chance is to mutate
			{
				int newGeneIndex = (int)(GetRandomVal(0,6)+0.5);
				if (newGeneIndex>=mutatePosition)
				{
					newGeneIndex += 1;
				}
				int swapTemp = offspring.genes[mutatePosition];
				offspring.genes[mutatePosition] = 
						offspring.genes[newGeneIndex];
				offspring.genes[newGeneIndex] = swapTemp;                       
			}
		}                                             		
		offsprings.Add(offspring);                
	}
	parents = offsprings;
}

This function applies the mutation operator with the given probability. It assays the chance of mutation while traversing the genes of chromosomes in the current population. If the mutation has to be applied to a gene, then it's value swaps with a randomly selected gene except the gene that is subjected to mutate from the same chromosome.

When a solution is achieved, the array of genes in the chromosome that contains the solution can be set to the property that are named as Genes in the class Board.

How to Use

The program allows you to specify the population size, number of generations, crossover probability and the mutation probability. The algorithm can be executed using the start button. If the population size and the number of generations are too large, please use the progress bar to indicate the current generation. But it can dramatically slow down the algorithm.

All the chromosomes of the final generation are shown in the table and the graphical chess board shows the best result.

The source code is available to download.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Ravimal Bandara
Student University of Moratuwa
Sri Lanka Sri Lanka
Postgraduate research student specializing in video content analysis. Interested in Image processing, HCI and Digital music production. Computer and technology enthusiast. I love coding and sharing my knowledge.
Follow on   Twitter

Comments and Discussions

 
Questionusing genatic algorithm to built time table schedular in c# PinmemberMember 769934917-Mar-14 19:10 
AnswerRe: using genatic algorithm to built time table schedular in c# PinprofessionalRavimal Bandara19-Mar-14 6:12 
GeneralMy vote of 5 PinmemberMaimonides29-Jul-13 21:53 
QuestionRuletteWheel Pinmembermoein.serpico11-Dec-12 9:47 
AnswerRe: RuletteWheel PinmemberRavimal Bandara3-Jun-13 2:05 
GeneralMy vote of 5 Pinmemberbadboy199210-Dec-12 3:15 
Questioncan i Pinmemberidris aliu10-May-12 8:05 
GeneralMy vote of 5 Pinmembermanoj kumar choubey27-Mar-12 23:51 
Questionstructs + arrays PinmemberChristian Setzkorn3-Jan-12 5:17 
Question8 queens Pinmembergardenona14-Nov-11 21:09 
GeneralMy vote of 5 Pinmembergardenona14-Nov-11 21:02 
GeneralMy vote of 4 Pinmemberham_gr806-Jul-11 20:40 
QuestionMy vote of 5 PinmemberFilip D'haene30-Jun-11 5:03 
GeneralMy vote of 5 Pinmembers.kleinschmidt28-Jun-11 5:10 
GeneralRe: My vote of 5 PinmemberRavimal Bandara9-Jul-11 6:39 
QuestionNice work but this can be simply coded rationally PinmemberGeorge Swan26-Jun-11 12:42 
AnswerRe: Nice work but this can be simply coded rationally PinmemberRavimal Bandara27-Jun-11 3:26 
GeneralRe: Nice work but this can be simply coded rationally PinmemberGeorge Swan27-Jun-11 4:22 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web04 | 2.8.140916.1 | Last Updated 25 Jun 2011
Article Copyright 2011 by Ravimal Bandara
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid