# 8 Queens problem

• 10-13-2007
Dashing Boy
8 Queens problem
i have a homework
my homework is to place the remaining 7 queens pieces from the game of chess
on a chessboard so that no queen piece is threatening another queen on the board after user had placed the 1st queen on the position of his choice.

I thought declaring an array like that int queen[8][8] and initially put 0 in entire array thenand put 1 for queen and put 2 to threatining place into this array.

I wrote this code:

Code:

```int a,b,check,queen[8][8],A,B,i,j; for (i=0;a<=7;a++)         {                 for (i=0;b<=7;b++)                 {                         queen[a][b]=0;                 }         } a=3;    //suppose user input these co-ordinates b=5; queen[a][b]=1;         //loops for user placed queen for (i=a+1;i<=7;i++)  //to lock the corresponding lower column         queen[i][b]=2; for (i=a-1;i>=0;i--)        //to lock the corresponding upper column         queen[i][b]=2; for (i=a-1,j=b+1;i>=0,j<=7;i--,j++)  //to lock the corresponding upper right diagonal         queen[i][j]=2; for (i=a-1,j=b-1;i>=0,j>=0;i--,j--)    //to lock the corresponding upper left diagonal         queen[i][j]=2; for (i=a+1,j=b+1;i<=7,j<=7;i++,j++)    //to lock the corresponding lower right diagonal         queen[i][j]=2; for (i=a+1,j=b-1;i<=7,j>=0;i++,j--)    //to lock the corresponding lower left diagonal         queen[i][j]=2; for (i=0;i<=7;i++) {         for (j=0;j<=7;j++)         {                     if (queen[i][j]==0)                     {                                   queen[i][j]=1;                                   // and locked the corresponding column, rows, diagonals for this.                     }         } }```
But the problem is I can't back track to remove the queen if there's no place left for it to place in a particular row.

I tried to to this but it only increased the size of of my program and still no results.

• 10-13-2007
tjpanda
I tried to make sense of your code but I had a hard time, so I went ahead and tried to make it look better, I may misunderstand your intentions in my comments so feel free to harp on me if I did.

Now, what I don't understand is what the problem is?

Code:

```// Commented and cleared for the sake of clarity int a, b;                // The input variables, will store the location of the user-defined queen int check;                // Declared but not used so far int queen[8][8];        // The array that holds the values of where a queen is and can be placed int A, B;                // Declared but not used so far int i, j;                // Counters for (i=0;a<=7;a++)                        // Loop that runs while a = {0, 1, 2, ..., 7}         {                 for (i=0;b<=7;b++)        // Loop that runs while b = {0, 1, 2, ..., 7}                 {                         queen[a][b]=0;        // Initializing the "chest board" array                 }         } a=3;                        //suppose user input these co-ordinates b=5; // If queen[x][y] == 0 then a queen can be placed // If queen[x][y] == 1 then a queen is already placed there // If queen[x][y] == 2 then a queen can not be placed there, due to risk of death by being in line with another queen // Set the user-defined queen queen[a][b]=1; /*****************************************************************/ /*--------NOTE: a corresponds to x and b corresponds to y--------*/ /*****************************************************************/ // The below is for the user-placed queen -------- for (i=a+1;i<=7;i++)                                //to lock the corresponding lower column         queen[i][b]=2; for (i=a-1;i>=0;i--)                                //to lock the corresponding upper column         queen[i][b]=2; for (i=a-1,j=b+1;i>=0,j<=7;i--,j++)                //to lock the corresponding upper right diagonal         queen[i][j]=2; for (i=a-1,j=b-1;i>=0,j>=0;i--,j--)                //to lock the corresponding upper left diagonal         queen[i][j]=2; for (i=a+1,j=b+1;i<=7,j<=7;i++,j++)                //to lock the corresponding lower right diagonal         queen[i][j]=2; for (i=a+1,j=b-1;i<=7,j>=0;i++,j--)                //to lock the corresponding lower left diagonal         queen[i][j]=2; // The above was for the user-placed queen -------- // The below will cycle through and set queens in the free spaces for (i=0;i<=7;i++) {         for (j=0;j<=7;j++)         {                     if (queen[i][j]==0)        // In the case we can set a queen                     {                                 queen[i][j]=1;        // We do                                 // and locked the corresponding column, rows, diagonals for this.                                 // here would be like the above code that we could put in a function                                 // such as "LockQueen(i, j);" that ran the code that was above                                 // in the function for the values i and j being a and b                     }         } }```
EDIT: Here's the LockQueen function I was talking about, at least I'm pretty sure the int &queen[8][8] part will work, if not just define queen as a global before you declare LockQueen():

Code:

```void LockQueen(int x, int y, int &queen[8][8]) {         int i; j;         for (i=x+1;i<=7;i++)                                //to lock the corresponding lower column                 queen[i][y]=2;         for (i=x-1;i>=0;i--)                                //to lock the corresponding upper column                 queen[i][y]=2;         for (i=x-1,j=y+1;i>=0,j<=7;i--,j++)                //to lock the corresponding upper right diagonal                 queen[i][j]=2;         for (i=x-1,j=y-1;i>=0,j>=0;i--,j--)                //to lock the corresponding upper left diagonal                 queen[i][j]=2;         for (i=x+1,j=y+1;i<=7,j<=7;i++,j++)                //to lock the corresponding lower right diagonal                 queen[i][j]=2;         for (i=x+1,j=y-1;i<=7,j>=0;i++,j--)                //to lock the corresponding lower left diagonal                 queen[i][j]=2; }```
• 10-13-2007
Dashing Boy
Yeah, that's what I intended to do. Sorry for not being clear. Actually, the program which I wrote is so messed up now that even I'm having a hard time understanding it.

Now coming to the problem. The problem is, suppose the function LockQueen worked up to rows 0-2 then it skipped the row 3, the user has inputed by incrementing a variable of the outer loop. But in row 4 there's no suitable place for a queen, so it should go back to row 2 and moves the queen to the next suitable location. THAT's my problem. How could I do that???

Any help would be greatly appreciated.

P.S. Please ignore any grammatical errors as English isn't my first language, but I hope I'm lot more clearer this time.
• 10-13-2007
CornedBee
You could make more use of the many values an int can take, e.g.:
0: No queen, nobody threatening.
-1: Queen.
-2: There used to be a queen there, but it was moved.
> 0: this many pieces are threatening this field.

Then on placing a queen, you increment every field the queen can reach and that is >= 0. On removing a queen, you decrement every field the queen can reach and that is > 0. (If you encounter a field == 0 on removing, you've got a bug.)
• 10-13-2007
Dashing Boy
That's exactly what I initially did.

0: or no queen
1: queen
2: locked path/threatening

When there's no place go back to the previous iteration and removes the queen with aal its fields and placed 4 where it was initially and then starts the whole process again. Now the problem is, if I place 0 again it would place the queen on the same location again and if I place or 2 it runs into a situation where I can't find a solution.

• 10-13-2007
tjpanda
This may not be the best solution but try adding a second 2darry such as:

Code:

`int badLocation[8][8];                // A mask for "bad spots"`
Then every time you run across a problem like you mentioned you can put a 1 on that location in badLocation and then in your code check to see if the location your about to set a queen in has a 1 in that position on badLocation, if it does then simply don't place it there and move on to the next slot.
• 10-13-2007
CornedBee
No, it's not the same. Read my post again. My system is more complex.
• 10-14-2007
Dashing Boy

tjpanda, I tried what you said but still....the problem is how to remove that particular 1 again if there's no slot for placing a queen after investigating all the previous rows.

And CornedBee, sorry! I didn't get you. Would you please elaborate it a little more by writing a piece of code for that???
• 10-14-2007
CornedBee
Something like this:
Code:

```bool addQueen(int x, int y) {   if(theField[x][y] != 0) {     return false; // Field is threatened or already taken or was already taken once.   }   for(int i = 0; i < 8; ++i) {     if(theField[i][y] == -1) {       return false; // Would threaten on row.     }     if(theField[x][i] == -1) {       return false; // Would threaten on column.     }   }   // Same test for diagonal. Too lazy to implement the coordinate finding.   // OK, we know we can place the queen.   theField[x][y] = -1;   for(int i = 0; i < 8; ++i) {     if(theField[i][y] >= 0) {       ++theField[i][y]; // One more piece is threatening this field.     }     if(theField[x][i] >= 0) {       ++theField[x][i]; // One more piece is threatening this field.     }   }   // Again, same thing for diagonal moves.   return true; } bool removeQueen(int x, int y) {   if(theField[x][y] != -1) {     // There's no queen here.     return false;   }   theField[x][y] = -2; // There has been a queen here, so don't try placing one again.   for(int i = 0; i < 8; ++i) {     if(theField[i][y] > 0) {       --theField[i][y]; // One less piece is threatening this field.     }     if(theField[x][i] > 0) {       --theField[x][i]; // One less piece is threatening this field.     }   }   // Again, same thing for diagonal moves.   return true; }```
The nice thing about this is that you don't mark a field unthreatened by removing a queen when in fact a different queen is still threatening it. Which, I guess, was your main problem.
• 10-14-2007
Dashing Boy

Code:

```#include "stdafx.h" #include <iostream> using namespace std; int queen[8][8]; bool addQueen(int x, int y) {         int j;         if(queen[x][y] != 0)         {                 return false; // Field is threatened or already taken or was already taken once.         }         for(int i = 0; i < 8; ++i)         {                 if(queen[i][y] == -1)                 {                         return false; // Would threaten on row.                 }                 if(queen[x][i] == -1)                 {                         return false; // Would threaten on column.                 }         }   // OK, we know we can place the queen.         queen[x][y] = -1;         for(int i = 0; i < 8; ++i)         {                 if(queen[i][y] >= 0)                 {                         ++queen[i][y]; // One more piece is threatening this field.                 }                 if(queen[x][i] >= 0)                 {                         ++queen[x][i]; // One more piece is threatening this field.                 }         }         for (int i=x-1,j=y+1;i>=0,j<=7;i--,j++)            {                 if (queen[i][j]>=0)                         ++queen[i][j];         }     for (int i=x-1,j=y-1;i>=0,j>=0;i--,j--)                        {                 if (queen[i][j]>=0)                         ++queen[i][j];         }     for (int i=x+1,j=y+1;i<=7,j<=7;i++,j++)                        {                 if (queen[i][j]>=0)                         ++queen[i][j];         }     for (int i=x+1,j=y-1;i<=7,j>=0;i++,j--)                        {                 if (queen[i][j]>=0)                         ++queen[i][j];         }           return true; } bool removeQueen(int x, int y) {         int j;         if(queen[x][y] != -1)         {     // There's no queen here.                 return false;         }         queen[x][y] = -2; // There has been a queen here, so don't try placing one again.         for(int i = 0; i < 8; ++i)         {                 if(queen[i][y] > 0)                 {                         --queen[i][y]; // One less piece is threatening this field.                 }                 if(queen[x][i] > 0)                 {                         --queen[x][i]; // One less piece is threatening this field.                 }         }                 for (int i=x-1,j=y+1;i>=0,j<=7;i--,j++)            {                 if (queen[i][j]>0)                         --queen[i][j];         }     for (int i=x-1,j=y-1;i>=0,j>=0;i--,j--)                        {                 if (queen[i][j]>0)                         --queen[i][j];         }     for (int i=x+1,j=y+1;i<=7,j<=7;i++,j++)                        {                 if (queen[i][j]>0)                         --queen[i][j];         }     for (int i=x+1,j=y-1;i<=7,j>=0;i++,j--)                        {                 if (queen[i][j]>0)                         --queen[i][j];         }   return true; } int _tmain(int argc, _TCHAR* argv[]) {         int a, b, i, j; // ab to store the user co-ordinates ans i,j as counters         bool ans;     //int queen[8][8];     for (i = 0; i <= 7; i++)                        // Loop that runs while a = {0, 1, 2, ..., 7}                 {                         for (j = 0; j <= 7; j++)        // Loop that runs while b = {0, 1, 2, ..., 7}                         {                                 queen[i][j] = 0;        // Initializing the "chest board" array             }         }     cout<<"Enter Row: ";     cin>>a;     cout<<"Enter Column: ";     cin>>b;     queen[a][b] = -1;     for(i = 0; i < 8; ++i)         {                 ++queen[i][b]; // One more piece is threatening this field.         ++queen[a][i]; // One more piece is threatening this field.     }     for (i=a-1,j=b+1;i>=0,j<=7;i--,j++)                //to lock the corresponding upper right diagonal                 ++queen[i][j];     for (i=a-1,j=b-1;i>=0,j>=0;i--,j--)                //to lock the corresponding upper left diagonal             ++queen[i][j];     for (i=a+1,j=b+1;i<=7,j<=7;i++,j++)                //to lock the corresponding lower right diagonal             ++queen[i][j];     for (i=a+1,j=b-1;i<=7,j>=0;i++,j--)                //to lock the corresponding lower left diagonal             ++queen[i][j];         for (i=0;i<8;++i)         {                 for (j=0;j<8;++j)                 {                         if (i==a)                                 ++i;                         ans = addQueen(i,j);                         if (!ans)                                 removeQueen(i,j);                 }         }         for (i=0;i<8;i++)         {                 for (j=0;j<8;j++)                 {                         cout<<"\t"<<queen[i][j];                 }                 cout<<"\n";         }         return 0; }```
And the output I got is:

Enter Row: 3
Enter Column: 5

-1 3 3 2 2 4 2 2
3 3 -1 2 3 2 3 3
3 4 3 3 3 2 3 -1
4 3 4 2 3 1 3 3
2 -1 3 2 4 4 4 2
2 1 2 2 3 3 2 2
2 2 3 3 -1 3 3 4
2 3 3 2 3 3 -1 3

Enter Row: 0
Enter Column: 0
1 3 3 3 3 1 2 2
3 3 -1 4 2 2 2 1
3 4 4 3 -1 2 1 1
3 -1 3 4 4 2 1 1
3 2 4 -1 3 2 2 1
1 2 2 2 2 1 1 1
2 2 1 1 2 1 1 1
2 1 1 1 1 1 1 1

Enter Row: 5
Enter Column: 5
3 -1 4 3 2 3 1 2
4 4 3 -1 3 2 1 2
-1 3 4 4 2 3 1 2
2 4 -1 3 2 3 2 3
3 3 3 3 2 3 3 -1
3 2 2 3 2 1 3 3
1 1 1 1 2 3 1 2
1 1 1 2 1 2 1 2

Any ideas what went wrong or did I misunderstood anything...???
• 10-14-2007
CornedBee
Why did you replicate logic from addQueen() in main()?
• 10-14-2007
Dashing Boy
To block the path of the user placed queen. Still there's no appropriate solution if I remove that part. .
• 10-14-2007
matsp
Quote:

Originally Posted by Dashing Boy
To block the path of the user placed queen. Still there's no appropriate solution if I remove that part. .

But surely the function "placeQueen" shouldn't care if it's a user-placed queen or not?

--
Mats
• 10-14-2007
Dashing Boy
Ooooops........I guess that was the mistake. But still it is not producing the required result after removing that part of code. Here's the result:

Enter Row: 3
Enter Column: 5
-1 3 3 3 2 2 3 1
3 3 -1 3 3 2 2 2
3 4 3 4 -1 1 3 1
3 2 3 3 2 -1 1 0
2 -1 4 3 4 2 3 1
3 3 3 -1 3 2 3 2
2 1 2 2 2 1 2 2
2 3 2 2 3 2 -1 2

Enter Row: 0
Enter Column: 0
-1 2 3 1 1 2 1 0
2 -1 3 3 3 3 1 2
3 3 3 -1 4 2 2 2
1 3 4 4 3 -1 2 1
1 3 -1 3 4 4 2 1
2 3 2 4 -1 3 2 2
1 1 2 2 2 2 1 1
0 2 2 1 1 2 1 1

I even tried after both removing and adding the following part of code but can't find any significant improvement.

Code:

``` if(i==a)          //to skip the row of user placed queen {       i++; }```
• 10-15-2007
Dashing Boy
Sorry for disturbing your guys again.

But that's what I did. I made an array of type 'position' to keep track of the queens I placed, like that:

Code:

```struct position {       int x,y; }; position queen[8];```
And that's the way I used it:

Code:

```#include "stdafx.h" #include <iostream> using namespace std; int board[8][8],a,b; struct position {         int x,y; }; position queen[8]; bool addQueen(int x, int y) {         int j;         if(board[x][y] != 0)         {                 return false; // Field is threatened or already taken or was already taken once.         }         for(int i = 0; i < 8; ++i)         {                 if(board[i][y] == -1)                 {                         return false; // Would threaten on row.                 }                 if(board[x][i] == -1)                 {                         return false; // Would threaten on column.                 }         }   // OK, we know we can place the queen.         board[x][y] = -1;         for(int i = 0; i < 8; ++i)         {                 if(board[i][y] >= 0)                 {                         ++board[i][y]; // One more piece is threatening this field.                 }                 if(board[x][i] >= 0)                 {                         ++board[x][i]; // One more piece is threatening this field.                 }         }         for (int i=x-1,j=y+1;i>=0,j<=7;i--,j++)            {                 if (board[i][j]>=0)                         ++board[i][j];         }     for (int i=x-1,j=y-1;i>=0,j>=0;i--,j--)                        {                 if (board[i][j]>=0)                         ++board[i][j];         }     for (int i=x+1,j=y+1;i<=7,j<=7;i++,j++)                        {                 if (board[i][j]>=0)                         ++board[i][j];         }     for (int i=x+1,j=y-1;i<=7,j>=0;i++,j--)                        {                 if (board[i][j]>=0)                         ++board[i][j];         }           return true; } bool removeQueen(int x, int y) {         int j;         if(board[x][y] != -1)         {     // There's no queen here.                 return false;         }         board[x][y] = 0; // There has been a queen here, so don't try placing one again.         for(int i = 0; i < 8; ++i)         {                 if(board[i][y] > 0)                 {                         --board[i][y]; // One less piece is threatening this field.                 }                 if(board[x][i] > 0)                 {                         --board[x][i]; // One less piece is threatening this field.                 }         }                 for (int i=x-1,j=y+1;i>=0,j<=7;i--,j++)            {                 if (board[i][j]>0)                         --board[i][j];         }     for (int i=x-1,j=y-1;i>=0,j>=0;i--,j--)                        {                 if (board[i][j]>0)                         --board[i][j];         }     for (int i=x+1,j=y+1;i<=7,j<=7;i++,j++)                        {                 if (board[i][j]>0)                         --board[i][j];         }     for (int i=x+1,j=y-1;i<=7,j>=0;i++,j--)                        {                 if (board[i][j]>0)                         --board[i][j];         }   return true; } bool moveQueen (int x, int y) {         if (x==a)                 return false;         removeQueen(x,y);         for (int i=y+1;i<=7;i++)         {                 if (board[x][i]==0)                 {                         board[x][i]=-1;                         return true;                 }         }         return false; } int _tmain(int argc, _TCHAR* argv[]) {         int i, j;         bool ansAdd, ansRem, ansMov;     //int queen[8][8];     for (i = 0; i <= 7; i++)                        // Loop that runs while a = {0, 1, 2, ..., 7}                 {                         for (j = 0; j <= 7; j++)        // Loop that runs while b = {0, 1, 2, ..., 7}                         {                                 board[i][j] = 0;        // Initializing the "chest board" array             }         }         cout<<"Enter Row: ";         cin>>a;         cout<<"Enter Column: ";         cin>>b;     board[a][b] = -1;     for (i=0;i<8;++i)         {                 for (j=0;j<8;++j)                 {                         if (i==a)                //if i = user input row                                 ++i;                         if (i==8)                                 break;                         ansAdd = addQueen(i,j);                         if (ansAdd)                         {                                 queen[i].x=i;            //to keep track of the placed queens                                 queen[i].y=j;                                 break;                         }                         if (!ansAdd && j==7)        // if there's no place for a queen to be placed                         {                                 ansMov = moveQueen (queen[i].x,queen[i].y);    move queen to the next available slot                                 if (!ansMov)                                         i-=2;                                                         }                                         }         }         for (i=0;i<8;i++)         {                 for (j=0;j<8;j++)                 {                         cout<<"\t"<<board[i][j];                 }                 cout<<"\n";         }         return 0; }```
And the result is:

Enter Row: 0
Enter Column: 0
0 1 2 -1 0 1 0 -1
1 -1 3 3 3 3 1 2
2 3 2 -1 4 2 2 2
0 3 4 3 3 -1 2 1
0 3 -1 3 3 4 2 1
1 3 2 4 -1 2 2 2
0 1 2 2 2 2 0 1
0 2 2 1 1 2 1 0

Enter Row: 3
Enter Column: 5
1 2 1 2 -1 1 0 1
2 2 -1 2 2 1 2 2
2 2 1 3 0 -1 1 0
3 2 2 1 2 -1 0 0
2 -1 3 3 2 2 1 1
3 2 4 -1 1 1 2 1
1 2 2 2 1 0 0 1
-1 3 2 2 2 2 1 1

Would you please tell me what stupid mistake I'm making this time???