This is a solution for the 8 queens backtracking method. Can anyone please make

Question

This is a solution for the 8 queens backtracking method. Can anyone please make me understand this code.

Thank you.

#include <iostream>

using namespace std;

int main() {

int b[8][8]={0};

int counter=0;

int r;

int c=0;

b[0][0]=1;

NC: c++;

if (c == 8)

goto print;

r=-1;

NR: r++;

if (r==8)

goto backTrack;

//Row BT

for (int i=0; i<c ; i++)

if (b[r][i]==1) goto NR;

//updiagonal BT

for (int i=1; (r-i)>=0 && (c-i)>=0 ; i++)

if (b[r-i][c-i]==1) goto NR;

//Down diagonal BT

for (int i=1; (r+i)<8 && (c-i)>=0 ; i++)

if (b[r+i][c-i]==1) goto NR;

//now we place the queen

b[r][c]=1;

goto NC;

backTrack: c--;

if ( c == -1 )

return 0;

r=0;

while (b[r][c]!=1)

r++;

b[r][c]=0;

goto NR;

print: counter++;

cout << "Solution #"<<counter<<":"<<endl;

for(int i=0 ; i<8 ; i++)

{

for (int j=0 ; j<8 ; j++)

if ( b[i][j] == 1 )

cout << "Q";

else

cout << "-";

cout <<endl;

}

cout <<endl;

goto backTrack;

}

Explanation / Answer

8 queen problem is a classical algorithm problem where the aim is to put 8 queens on a 8x8 chessboard such that they cannot attack each other.

The given problem can be easily solved by brute force but back tracking is an efficient method to solve the same problem.

In backtracking mentioned above we place the queen starting from the leftmost column and while placing the queens we checked for already existing queens on the board for clashes.

In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes then we backtrack and return false.

In Steps:

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.