Hackety Hacking Problem Chess puzzle
Jump to navigation
Jump to search
Problem Statement
CHESS PUZZLE
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.
HINT : You have to write a program to print a chessboard positioning 8 queens according to the puzzle. Use backtracking technique and then check each case that does it satisfy the requirement.
Sample Output
1 * * * * * * * * * * * 1 * * * * * * * * * * 1 * * * * * 1 * * * * 1 * * * * * * * * * * * 1 * * 1 * * * * * * * * * 1 * * * *
Curriculum Connections
This problem gives student help in understanding few thins mentioned below:
- Making use of an important tool to develop Advanced programs - Backtracking technique
- Making use of structures
Solution
This program is written in C++. Compiled using Borland 5.5 C++ compiler. #include<stdio.h> #include<conio.h> #include<process.h> /* 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; }