// Below is the code for solving 8 queens problem using backtracking and 2 dimen

Question

//

Below is the code for solving 8 queens problem using backtracking and 2 dimensional arrays. Now i need to do this using a 1 dimensional array. please help.

#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

#include <iostream>
#include <cstdlib>
using namespace std;
int main ()
{
int counter = 1;
int q[8];
int c = 0;
int i = 0;
q[0] = 0;
nc: c++;
if (c == 8) goto print;
q[c] = -1;
nr: q[c]++;
if (q[c] == 8) goto backtrack;
for (i=0; i < c; i++)
{
if (q[i] == q[c] && abs(q[c] - q[i]) == c - i)
goto nr;
}
goto nc;
backtrack: c--;
if (c == -1) return 0;
goto nr;
print:
cout << "Solution number:" << counter << endl;
for (int k = 0; k < 8; k++)
{
cout << q[k];
}
cout << endl;
counter ++;
goto backtrack;
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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