Click here to Skip to main content
15,867,568 members
Articles / Multimedia / GDI

Solving Eight Queens Puzzle with Genetic Algorithm in C#

Rate me:
Please Sign up or sign in to vote.
4.84/5 (28 votes)
25 Jun 2011CPOL5 min read 95.6K   10K   43   28
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 <code>MAX_FIT = 28; holds the maximum fitness.

Functions

C#
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.

C#
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.

C#
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.

C#
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.

C#
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.

C#
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.

C#
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)



Comments and Discussions

 
Questionis the algorithm get all possible correct solution? Pin
abdo512-May-18 23:56
abdo512-May-18 23:56 
QuestionAbout the fitness value Pin
Mujeeba Haj Najeeb7-Apr-17 3:53
Mujeeba Haj Najeeb7-Apr-17 3:53 
AnswerRe: About the fitness value Pin
Ravimal Bandara30-Apr-17 6:43
Ravimal Bandara30-Apr-17 6:43 
GeneralRe: About the fitness value Pin
Mujeeba Haj Najeeb30-Apr-17 10:35
Mujeeba Haj Najeeb30-Apr-17 10:35 
Question8th Queen is capturing other Queen in all slouting Pin
Syed Murad Shah16-Dec-15 3:26
Syed Murad Shah16-Dec-15 3:26 
AnswerRe: 8th Queen is capturing other Queen in all slouting Pin
Ravimal Bandara21-Dec-15 22:08
Ravimal Bandara21-Dec-15 22:08 
Questioncan you help me in this please ?? i think that's easy for you Pin
Member 1213530412-Nov-15 23:17
Member 1213530412-Nov-15 23:17 
QuestionIs there any generation size limitation. Pin
Member 113431151-Jan-15 5:01
Member 113431151-Jan-15 5:01 
AnswerRe: Is there any generation size limitation. Pin
Ravimal Bandara1-Jan-15 17:18
Ravimal Bandara1-Jan-15 17:18 
Questionusing genatic algorithm to built time table schedular in c# Pin
neeraj kumar gandhi17-Mar-14 19:10
neeraj kumar gandhi17-Mar-14 19:10 
AnswerRe: using genatic algorithm to built time table schedular in c# Pin
Ravimal Bandara19-Mar-14 6:12
Ravimal Bandara19-Mar-14 6:12 
GeneralMy vote of 5 Pin
Joezer BH29-Jul-13 21:53
professionalJoezer BH29-Jul-13 21:53 
QuestionRuletteWheel Pin
moein.serpico11-Dec-12 9:47
moein.serpico11-Dec-12 9:47 
AnswerRe: RuletteWheel Pin
Ravimal Bandara3-Jun-13 2:05
Ravimal Bandara3-Jun-13 2:05 
GeneralMy vote of 5 Pin
badboy199210-Dec-12 3:15
badboy199210-Dec-12 3:15 
Questioncan i Pin
idris aliu10-May-12 8:05
idris aliu10-May-12 8:05 
GeneralMy vote of 5 Pin
Manoj Kumar Choubey27-Mar-12 23:51
professionalManoj Kumar Choubey27-Mar-12 23:51 
Questionstructs + arrays Pin
Christian Setzkorn3-Jan-12 5:17
Christian Setzkorn3-Jan-12 5:17 
Question8 queens Pin
gardenona14-Nov-11 21:09
gardenona14-Nov-11 21:09 
GeneralMy vote of 5 Pin
gardenona14-Nov-11 21:02
gardenona14-Nov-11 21:02 
GeneralMy vote of 4 Pin
ham_gr806-Jul-11 20:40
ham_gr806-Jul-11 20:40 
QuestionMy vote of 5 Pin
Filip D'haene30-Jun-11 5:03
Filip D'haene30-Jun-11 5:03 
GeneralMy vote of 5 Pin
s.kleinschmidt28-Jun-11 5:10
s.kleinschmidt28-Jun-11 5:10 
GeneralRe: My vote of 5 Pin
Ravimal Bandara9-Jul-11 6:39
Ravimal Bandara9-Jul-11 6:39 
QuestionNice work but this can be simply coded rationally Pin
George Swan26-Jun-11 12:42
mveGeorge Swan26-Jun-11 12:42 

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

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