give the description to illustrate the program and most importantly Please give

ID: 3726557 • Letter: G

Question

give the description to illustrate the program and most importantly Please give clear and appropriate flowchart and algorithm description.

(Game: Eight Queens) The classic Eight Queens puzzle is to place eight queens
on a chessboard such that no two queens can attack each other (i.e., no two queens
are on the same row, same column, or same diagonal). There are many possible
solutions. Write a program that displays one such solution. A sample output is
shown below:
|Q| | | | | | | |
| | | | |Q| | | |
| | | | | | | |Q|
| | | | | |Q| | |
| | |Q| | | | | |
| | | | | | |Q| |
| |Q| | | | | | |
| | | |Q| | | | |

Explanation / Answer

}

BACKTRACKING CONCEPT:

1.Each recursive call attempts to place a queen in a specific column.

2. For a given call,the state of the board from previous placements is known.

3.Currentstep backtracking. If a placement within the column does not lead to a solution,the queen is removed and moved . "down"thecolu1nn

4. Previousstep backtracking when all rows in a column have been tried,the call terminates and backtracks to the

previouscall.

5.pruning:If a queen cannot be placed into a column i do not even try to place onto column i+1,rather to backtrack i-1 and move the queen that has placed.

Algorithm:

#include<stdio.h> #include<stdlib.h> int t[8] = {-1}; int sol = 1; void printsol() { int i,j; char crossboard[8][8]; for(i=0;i<8;i++) { for(j=0;j<8;j++) { crossboard[i][j]='_'; } } for(i=0;i<8;i++) { crossboard[i][t[i]]='q'; } for(i=0;i<8;i++) { for(j=0;j<8;j++) { printf("%c ",crossboard[i][j]); } printf(" "); } } int empty(int i) { int j=0; while((t[i]!=t[j])&&(abs(t[i]-t[j])!=(i-j))&&j<8)j++; return i==j?1:0; } void queens(int i) { for(t[i] = 0;t[i]<8;t[i]++) { if(empty(i)) { if(i==7){ printsol(); printf(" solution %d ",sol++); } else queens(i+1); } } } int main() { queens(0); return 0;

}