11,637,415 members (64,440 online)
Tip/Trick

# N-Queen Problem using Genetic Algorithms

, 7 Jun 2013 CPOL 11.6K 805 4
 Rate this:
In this article, we describe a solution for solving the 8-queen problem.

## Introduction

In this article, we describe a solution for solving the 8-queen problem. My solution is based on Genetic algorithms that is not a good method for solving this type of a problem.

In my code, first initiate the primary population (as chromosomes). For example: a={3 1 4 2} means queen is in row 1 and column 3, next queen is in row 2 and column 1, and etc.

Then select the best chromosomes from the population. In the next step generate some children from the population (crossover) and some of this children mutate. And between children and parents select the best chromosome.

This cycle repeats for n times (for example, n= 100).

## Using the code

1. Before you run the program you should understand the variants that they use for population size, table size, and fitness (for genetic algorithms).
```fixedsize=100;
tablesize=8;
fitness=0; ```
2. First, generate the primary population that shows as a decimal array: for example, (4-queens) : a={3 1 4 2} means queen is in row 1 and column 3, next queen is in row 2 and column 1, and etc.
```for i=1:fixedsize
cromo(i,1:tablesize)=randperm(tablesize);
cromo(i,tablesize+1)=-1;
end;
for i=1:fixedsize
for j=1:tablesize
for k=j+1:tablesize
if (cromo(i,j)==cromo(i,k)) || (abs(cromo(i,j)-abs(cromo(i,k))) == abs(j-k))
fitness=fitness+1;
end;
end;
end;
cromo(i,tablesize+1)=fitness;
fitness=0;
end;```
3. Select the best parents to generate the children:
`cromo=sortrows(cromo,9);`
4. Generate the children and mutate them. Repeat this step for n times (example, n=1500).
``` for cnt=1:1500
if(cromo(1:fixedsize,9)==0)
level=cnt;
checkboard(cromo(1,1:tablesize),tablesize,tablesize);
break;
end;
%pm=(1/240)+(0.11375/2^cnt);
pc=1/cnt ;
slct=cromo(1:fixedsize,:);
n=0;
for i=1:2:fixedsize/2
u=rand(1);
if(u<=pc)
n=n+2;
child(n-1:n,1:tablesize)=crossover(slct(i:i+9,:),tablesize);
end;
end;
%n=n+1;
%if(n>0)
child(:,tablesize+1)=-1;

cromo((fixedsize+1)-length(child):end,:)=[];
cromo=[cromo;child];
for i=(fixedsize+1)-length(child):fixedsize
cromo(i,1:tablesize)=mutation(cromo(i,1:tablesize),tablesize);
end;
%end;
fitness=0;
for i=1:fixedsize
for j=1:tablesize
for k=j+1:tablesize
if (cromo(i,j)==cromo(i,k)) ||
(abs(cromo(i,j)-abs(cromo(i,k))) == abs(j-k))
fitness=fitness+1;
end;
end;
end;
cromo(i,tablesize+1)=fitness;
fitness=0;
end;
cromo=sortrows(cromo,9);
end;```

• Version 1.0.

## Share

 Web Developer ARS NET Iran (Islamic Republic Of)
No Biography provided

## You may also be interested in...

 First Prev Next
 N-Queen Problem using Genetic Algorithms Member 1126293426-Jun-15 12:02 Member 11262934 26-Jun-15 12:02
 Re: N-Queen Problem using Genetic Algorithms Hamed Naeemaei20-Jul-15 7:23 Hamed Naeemaei 20-Jul-15 7:23
 erros in the code Member 1131594616-Dec-14 12:02 Member 11315946 16-Dec-14 12:02
 Re: erros in the code Hamed Naeemaei17-Dec-14 2:46 Hamed Naeemaei 17-Dec-14 2:46
 Re: erros in the code Hamed Naeemaei14-Mar-15 20:33 Hamed Naeemaei 14-Mar-15 20:33
 Last Visit: 31-Dec-99 18:00     Last Update: 30-Jul-15 12:09 Refresh 1