8 Queens
8 Queens is
one of the most common problems in Artificial Intelligence.
Let's define: If a person has wanted to place eight queens on a chess board in
such a way that no one will see each other, what would be the algorithm?
The Algorithm
C source Code
You can grab the compiled version here.
#include<stdio.h>
#include<conio.h>
#include<process.h>
#include<dos.h>
#include<iostream.h>
/*
Used Variables
a :Matrix
x, y : row, colomn
n : Size of matrix
k : takes only 0 or 2
Purpose: This function is called after the queen is placed to x,y position
and after the preceding placed queen is erased.
if k = 0 decrease process or k = 2 for inrease process
*/
void up_or_down(int x,int y,int n,int a[8][8],int k)
{
int i1,j1,x1,x2,y1,y2;
x++;
x1 = x2 = x;
y1 = y2 = y;
for (i1=x1;i1<n;i1++) // Placed or erased queen's rows are
a[i1][y]+=(k-1); // increased or decreased
while (y1>0) // Lower-Left corner is up or dowm
{
y1--;
a[x1][y1]+=(k-1);
x1++;
}
while (y2<(n-1)) // Lower-right corner is up or dowm
{
y2++;
a[x2][y2]+=(k-1);
x2++;
}
}
/*
Used variables
a : Matrix
*ystr1 : Pointer of the row(i)
*ystr2 : Pointer of the colomn(j)
n : Matrix size
position : Holds the position of placed queens in the matrix, [2][15]
*ystr3 : Holds the last placed queen's used number of colomns
*ystr4 : Controls whether the n queens are placed correctly or not
Purpose :
For given position in an 8x8 matrix this function chooses the correct
place of the queen.If there is not a suitable place then colomn number
is incresed by one and at this point function runs in recursive mode.
Value of the position must be zero(0) to place the queen.
*/
void right_pos( int *ystr1,
int *ystr2,
int n,
int a[8][8],
int position[2][15],
int *ystr3,
int *ystr4)
{
int k=0,t1,t2;
while ( (a[*ystr1][*ystr2]) != 0 && (*ystr2) < n )
(*ystr2)++;
if (*ystr2==n)
{
(*ystr3)--;
t1=position[0][*ystr3];
t2=position[1][*ystr3];
a[t1][t2]=0;
position[0][*ystr3]=0;
position[1][*ystr3]=0;
(*ystr1)--;
k=0;
up_or_down(t1,t2,n,a,k); // Erased queen's lower-row and lower-corver
// is up or down
(*ystr4)--;
*ystr2=(t2+1);
right_pos(ystr1,ystr2,n,a,position,ystr3,ystr4); //recursive
}
}
int main(void)
{
clrscr();
void up_or_down(int ,int ,int ,int [8][8],int ); //declaration
void right_pos(int *,int *,int ,int [8][8],int [2][15],int *,int *);//declaration
static int i,j,yer,h,k,n=8,z=0;
int a[8][8],position[2][15];
char cev = 0;
while( cev != 27 )
{
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
a[i][j]=0;
}
}
for (i=0;i<2;i++)
{
for (j=0;j<15;j++)
{
position[i][j]=0;
}
}
j = z;
i = yer = h = 0;
while (yer<n)
{ // find the places where the queen will be placed
right_pos(&i,&j,n,a,position,&h,&yer);
a[i][j] = 100;
position[0][h] = i;
position[1][h] = j;
h++;
k=2;
up_or_down(i,j,n,a,k);
i++;
j=0;
yer++;
}
clrscr();
textcolor(3);
cprintf(" 8 QUEEN'S PALACEMENT TABLE \n");
for (i=0;i<n;i++)
{
gotoxy(13,3+i);
for (j=0;j<n;j++)
{
if (a[i][j]==100)
{
textcolor(2);
cprintf(" X");
}
else
{
textcolor(15);
cprintf("%4d",a[i][j]);
}
}
printf("\n");
}
textcolor(12);
gotoxy(28,12);
cprintf("TABLE %d",z+1);
textcolor(15);
gotoxy(5,15);
cprintf("Press any key to continue(ESC EXIT)...");
cev = getch();
z++;
if (z==8)
{
return 0;
}
}
return 0;
}
Sample Execution
8 QUEEN'S PLACEMENT TABLE
X 0 0 0 0 0 0 0
1 1 0 0 X
0 0 0
1 0
1 1 1 1 0
X
1 0
1 1 1 X 2 1
1 1 X 0
3 2 1 2
2 1 1 2 2 2 X 2
2 X 2
1 2 2 2 2
2 2 3 X
2 2 1 2
TABLE 1
0 X 0 0 0 0 0 0
1 1 1 X 0 0 0 0
0 1 1 2 1 X
0
0
0 2
0 1 2 2 1
X
1 1 X 2
0 2 2 2
X 2 2 2 0
2 1 2
2 3
1 1 2
1 X 2
2 1
2 2 X 3
1 2
TABLE 2
0 0 X 0 0 0 0 0
X 1 1 1 0 0 0 0
2 1 1 0 1
0 X 0
1 0
2 0 X 2
1
1
1 0
1 2 2 1
2 X
1 X 2
1 2 0
3 2
2 2 3 X
1 2 1 2
2 2 2 2 3 X
2 1
TABLE 3
0 0 0 X 0 0 0 0
X 0 1 1 1 0 0 0
1 2
0 1 X 1
0
0
2 0
1 2 1 1 1 X
1 X 1
2 1 0
2
2
2 2 1 1 2 1 X
2
2 1 X
2 2 2 1 2
1 2
1 3 3 X 2 1
TABLE 4
0 0 0 0 X 0 0 0
X 0 0 1 1 1 0 0
1 1 1 X 1
0 1 0
1 1 2
1 2 X 0 1
2 1
0 2 2 2 1
X
2 X 0
2 2 1
2
2
2 1
2 1 1 3 X
2
1 2 X 2 2 2 2 2
TABLE 5
0 0 0 0 0 X 0
0
X 0 0 0 1 1 1 0
1 1 0
1 X 1 0 1
1 X 2
1 1 2
0
0
2 2 2 1 1 1 1
X
2 2 X 1
2 1 1 2
2 2 1 1 2 3 X
1
2 1 1 X
3 3 2
2
TABLE 6
0 0 0 0 0 0 X 0
X 0 0 0 0 1 1 1
1 1 X 0
1 0 1 0
1 1 2 2 0 0 1
X
2 0
2 1 1 X 2 1
1 1 1 X 2
3 2 1
2 X 2 2 2 2 2 2
2 2 3
2 X 2 2 2
TABLE 7
0 0 0 0 0 0 0
X
0 X 0 0 0 0 1 1
1 1 1 X 0
1 0 1
X 1 1 2 2 0 0 1
1 3
0 2 1 1 X
1
2 1
2 1 X 2 2 2
1 2 X
3 2 1
2
2
2 2 2 3
2 X 2 2
TABLE 8