N Queen problem is a classic constraint satisfaction problem based on chess game.
The idea is how to put N numbers of Queen in N x N chessboard without giving them any chance to kill each other in one turn.
This article is specially dedicated for those with interest in artificial intelligence subject. The main topic is N Queen Problem, a classical problem of constraint satisfaction. However, this problem will always great to be discussed all the time. If you are a beginner in this section, please read the preface on the left side of this page.
I have made many versions of code in some different programming languages. Here is one of them, written in C++, compiled using Turbo C++ 1.0 from Borland. The running time is not really short, but this code has a very good N-Time curve where it is smooth and clean from exceptions and errors. Soon, I will publish my newer and better codes here, too. Please be patient.
You can use, compile, analyze and change any part of the source code below. If you find out how to make this algorithm works better, please send me an e-mail containing the change you have made and some explanations about your new improvements.
// N Queen Problem : versi 8 by Robert Setiadi
// This code is able to generate all pattern combinations
// and display the backtracking counter.
#include<stdio.h>
#include<iostream.h>
#include<conio.h>
#include<dos.h>
#include<graphics.h>
#include<stdlib.h>
int jawab[1001];
char boleh[1001];
int posisi,i,j,n,counter,tampil;
unsigned long int jback;
struct time t1,t2;
unsigned long kemungkinan;
char kmb,pertama,terus;
void generate_sah() {
int i,dx;
for(i=1;i<=n;i++) boleh[i]=1;
for(i=1;i<posisi;i++) {
boleh[jawab[i]]=0;dx=posisi-i;
if(jawab[i]-dx>=1) boleh[jawab[i]-dx]=0;
if(jawab[i]+dx<=n) boleh[jawab[i]+dx]=0;
}
}
void waktu(char tanda) {
struct time t;
if(tanda==3) {
printf("Starting time : %2d:%02d:%02d.%02d\n",
t1.ti_hour, t1.ti_min, t1.ti_sec, t1.ti_hund);
printf("Current time : %2d:%02d:%02d.%02d\n",
t2.ti_hour, t2.ti_min, t2.ti_sec, t2.ti_hund);
}
else gettime(&t);
if(tanda==1) t1=t; if(tanda==2) t2=t;
}
void main() {
clrscr();
cout<<"Artificial Intelligence : Queen Problem - version 8.0"<>n;
} while (n1000);
do {
cout<<"Display all possible combinations (Y/N) ? ";
kmb=getche();
} while (!(kmb=='y' || kmb=='Y' || kmb=='n' || kmb=='N'));
if(kmb=='n' || kmb=='N') pertama=1; else pertama=0;
waktu(1);cout<<endl;
for(i=1;i<=n;i++) jawab[i]=0; // initialization
counter=0;posisi=1;kemungkinan=1;terus=1;jback=0;
do {
cout<<endl;
do {
if(jawab[posisi]>=n) {
if(posisi!=1) jawab[posisi]=0;
posisi--;
counter--;
}
else {
j=jawab[posisi]+1;
generate_sah();
while(!boleh[j] && j<=n) {
j++;
}
if(j<=n) {
jawab[posisi]=j;
counter++;
posisi++;
}
else {
jawab[posisi]=0;
posisi--;
counter--;
jback++;
}
}
if(counter=0) terus=1; else terus=0;
if(counter==-1 && !pertama) terus=0;
} while(terus);
if(counter==n) {
waktu(2);
tampil=0;
if(!pertama) cout<<"Kemungkinan ke "<<kemungkinan<<" :\n";
cout<<setiosflags(ios::left);
for(i=1;i<=n;i++) {
cout<<'Q'<<setw(4)<<i<<"=("<<setw(4)<<i<<','<<setw(4)<<jawab[i]<<") ";
tampil++;if(tampil>=4) { cout<<endl; tampil=0; }
}
if(!pertama) {
cout<<"\nPress any key ... ";
kmb=getch();
cout<<endl;
kemungkinan++;
posisi=1;
counter=0;
for(i=1;i<n;i++) jawab[i]--;
}
}
} while(counter!=-1 && !pertama);
cout<<endl;
if(!pertama) cout<<"Ada "<<(kemungkinan-1)<<" pola.";
cout<<"\nJumlah backtracking = "<<jback<<" \n";waktu(3);
cout<<"copyright(c)1999 by Robert Setiadi - All Rights Reserved\n";
}
The code is fairly simple. It uses one 1-dimension array called “boleh” that is refreshed in every backtracking. The refresh function is called “generate_sah()”. The final solution is stored in array “jawab”. This code is able to generate first or all solutions for N Queen problem where the value of N can be 4 to 1000. I have never try to find any solution of 1000 queens using this program (theoretically possible, but will require too much time).
Leave A Comment