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:

A good program, works well.

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

#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;

}

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

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;

}

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

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++;

}

}

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.

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

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

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

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

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

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/

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 ()

Residential Building - Home entertainment Components

Feel free to visit my web blog: mp3 to video

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)

Vbr231 Assessment - A short Overview From the Vizio

Blu-ray Professional

Also visit my blog post - BenQ EP5920

Post a Comment