Saturday, July 7, 2007

What is the 8 queens problem? Write a C program to solve it.

The 8 queens problem is a classic problem using the chess board. This problem is to place 8 queens on the chess board so that they do not attack each other horizontally, vertically or diagonally. It turns out that there are 12 essentially distinct solutions to this problem.


Suppose we have an array t[8] which keeps track of which column is occupied in which row of the chess board. That is, if t[0]==5, then it means that the queen has been placed in the fifth column of the first row. We need to couple the backtracking algorithm with a procedure that checks whether the tuple is completable or not, i.e. to check that the next placed queen 'i' is not menaced by any of the already placed 'j' (j < i):


Two queens are in the same column if t[i]=t[j]
Two queens are in the same major diagonal if (t[i]-t[j])=(i-j)
two queens are in the same minor diagonal if (t[j]-t[i])=(i-j)




Here is some working C code to solve this problem using backtracking


#include
static int t[10]={-1};
void queens(int i);
int empty(int i);

void print_solution();

int main()
{
queens(1);
print_solution();
return(0);
}

void queens(int i)
{
for(t[i]=1;t[i]<=8;t[i]++)
{
if(empty(i))
{
if(i==8)
{
print_solution();
/* If this exit is commented, it will show ALL possible combinations */
exit(0);
}
else
{
// Recurse!
queens(i+1);
}

}// if

}// for
}



int empty(int i)
{
int j;
j=1;

while(t[i]!=t[j] && abs(t[i]-t[j])!=(i-j) &&j<8)j++;

return((i==j)?1:0);
}



void print_solution()
{
int i;
for(i=1;i<=8;i++)printf("\nt[%d] = [%d]",i,t[i]);
}




And here is one of the possible solutions



t[1] = [1] // This means the first square of the first row.
t[2] = [5] // This means the fifth square of the second row.
t[3] = [8] ..
t[4] = [6] ..
t[5] = [3] ..
t[6] = [7] ..
t[7] = [2] ..
t[8] = [4] // This means the fourth square of the last row.

18 comments:

Anonymous said...

A good program, works well.

Anonymous said...

write a C program to print first seven positive integers and their factorial?

Anonymous said...

#include
#include
int f(int);
void main()
{
int i;
printf(“number\tfactorial”);
for(i=1;i<8;i++)
printf(“%d\t%d”,i,f(i));
Getch();
}
int f(int n)
{
int fact=1;
for(i=1;i<n;i++)
fact*=i;
return fact;
}

Anonymous said...

Excellent code!!!!!thanks bro!!!

Anonymous said...

If I'm not mistaken, the loop in factorial program is wrong.

int f(int n)
{
int fact=1;
for(i=1;i<=n;i++)
fact*=i;
return fact;
}

Anonymous said...

Thankyou for the post. Program is short and easy to understand. It helped me a lot.

Anonymous said...

void main()
{
int i = 1, n = 1, fact = 1;
while (n <=7)
{
while (i <= n)
{
fact = fact *i;
i++;
}

printf("fact of %d is%d",n,fact);
n++;
}

}

Anonymous said...

Hi,in above 8 queen problem prg .....u have used "abs" but not define there in prg...plz check it and reply me...it's not running giving error.

diljit said...

@anonymous USE #include header file to use the abs math function

akashdeep sharma said...

the code you submitted is showing all possible solution but in last it gives one more extra solution as
t[1] = 9
t[2] = 9
t[3] = 9
t[4] = 9
t[5] = 9
t[6] = 9
t[7] = 9
t[8] = 9

Anonymous said...

Having read this I thought it was rather informative.

I appreciate you spending some time and effort to put this informative article together.
I once again find myself spending a lot of time both reading and posting comments.
But so what, it was still worthwhile!

My web site: Highly recommended Resource site

Anonymous said...

If you are tired of all the trendy toys out there, this is a classic you can't go wrong with. Large sailing ships are always popular Lego sets if sales on the secondary market are anything to go by. The LEGO Minotaurus comes with a rule booklet, instruction manual to build the board, one building LEGO dice, one building board, 12 LEGO micro figures and 224 LEGO pieces.

Here is my webpage spongebob lego

Anonymous said...

Unquestionably believe that which you said. Your favorite reason appeared to be on the net
the easiest thing to be aware of. I say
to you, I definitely get annoyed while people think about worries that they plainly don't know about. You managed to hit the nail upon the top and defined out the whole thing without having side effect , people can take a signal. Will likely be back to get more. Thanks

Here is my page - leave

Anonymous said...

These watches are designed to be loud and attractive.
But people are more interested in discussing the three newly-released Maurice Lacroix
Pontos D. Keep in mind, that there are certain watch makers,
who demand top dollar, for their watches.

Feel free to visit my site :: http://onthank.info/

Anonymous said...

You do not want any hard surfaced to come in contact with the soft delicate skin of your little one.

This allows your babies to sleep close to each other without clobbering or rolling over each other.
Though this article might be of great help in your
decision to buy a baby bassinet, try to find out
more on baby bassinets by reading reviews and other articles on
the internet.

Here is my weblog; round crib ()

Anonymous said...

Residential Building - Home entertainment Components

Feel free to visit my web blog: mp3 to video

Anonymous said...

Thanks for the good writeup. It in reality used to be a entertainment account it.
Glance complicated to far introduced agreeable from
you! By the way, how can we keep in touch?

Here is my web page :: golfnow (http://hamseoul.kr/wiki/index.php/%EC%82%AC%EC%9A%A9%EC%9E%90:HolleyEmm)

Anonymous said...

Vbr231 Assessment - A short Overview From the Vizio
Blu-ray Professional

Also visit my blog post - BenQ EP5920