My friend who is very good at chess bets me (not so good at chess ) to solve a classical puzzle of positioning eight queens on an 8*8 chessboard such that no two queens threaten each other. This means that no two queens may lie on the same row, column or diagonal.

Please help me as I cannot do this on my own.

You have to write a program to print a chessboard positioning 8 queens according to the puzzle.

HINT: Use backtracking technique and then check each case that does it satisfy the requirement.

Solution Code

~~This program is written in C++. Compiled using Borland 5.5 C++ compiler. ~~

/* This is the structure used to save the status of every block of chess if it is affected by the queen or not 
struct b
int p;
int hit;

typedef struct b node;

/* This function traverse every possible status of the chess with 8 queens on it. And then searches for a status that satisfies the given condition. Using nested for and if loops. */ void reset(node a[8][8]) { int i , j , k , l; for(i=0;i<8 ;i++) for(j=0;j<8;j++) a[i][j].hit=0; for(i=0;i<8;i++) for(j=0;j<8;j++) { if(a[i][j].p==1) { for(k=0;k<8;k++) for(l=0;l<8;l++) { if((i-j)==(k-l)) a[k][l].hit=1; if((i+j)==(k+l)) a[k][l].hit=1; if(k==i) a[k][l].hit=1; if(l==j) a[k][l].hit=1; }

} } };

/* This function prints the chessboard once the solution of the puzzle is found This uses two nested for loop to print the chess board using ‘*’ for an empty position and ‘1’ for a queen. */ void print(node a[8][8]) { int i, j; for(i=0;i<8;i++) { for(j=0;j<8;j++) { if(a[i][j].p==1) printf("1 "); else printf("* "); } printf("\n"); } getch(); };

void solve(node a[8][8], int count) { int i,j; if(count==8) { print(a); exit(0); } else { for(i=0;i<8;i++) for(j=0;j<8;j++) { if((a[i][j].p==0)&&(a[i][j].hit==0)) { a[i][j].p=1; reset(a); solve(a,count+1); a[i][j].p=0; reset(a); }

} } };

/* Small main code to call the function that is created */ int main() { int i, j; clrscr(); struct b c[8][8]; for(i=0;i<8;i++) for(j=0;j<8;j++) { c[i][j].p=0; c[i][j].hit=0; } solve(c,0); return 0; }

Sample Output


Non-profit Tax ID # 203478467