Click here to Skip to main content
12,757,627 members (37,456 online)
Click here to Skip to main content
Add your own
alternative version

Tagged as

Stats

16.8K views
1.1K downloads
4 bookmarked
Posted 6 Jun 2013

N-Queen Problem using Genetic Algorithms

, 7 Jun 2013 CPOL
Rate this:
Please Sign up or sign in to vote.
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;

History

  • Version 1.0.

License

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

Share

About the Author

Hamed Naeemaei
Web Developer ARS NET
Iran (Islamic Republic of) Iran (Islamic Republic of)
No Biography provided

You may also be interested in...

Pro
Pro

Comments and Discussions

 
Questionتوضیح تابع نامبرده Pin
Member 126688659-Aug-16 13:30
memberMember 126688659-Aug-16 13:30 
QuestionN-Queen Problem using Genetic Algorithms Pin
Member 1126293426-Jun-15 13:02
memberMember 1126293426-Jun-15 13:02 
AnswerRe: N-Queen Problem using Genetic Algorithms Pin
Hamed Naeemaei20-Jul-15 8:23
memberHamed Naeemaei20-Jul-15 8:23 
Questionerros in the code Pin
Member 1131594616-Dec-14 13:02
memberMember 1131594616-Dec-14 13:02 
AnswerRe: erros in the code Pin
Hamed Naeemaei17-Dec-14 3:46
memberHamed Naeemaei17-Dec-14 3:46 
AnswerRe: erros in the code Pin
Hamed Naeemaei14-Mar-15 21:33
memberHamed Naeemaei14-Mar-15 21:33 

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.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170217.1 | Last Updated 7 Jun 2013
Article Copyright 2013 by Hamed Naeemaei
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid