Hi all,
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 using a 2D array.
Initially I thought of declaring an array like that int queen[8][8] and initially put 0 in entire array and put 1 for queen and put 2 to threatining place into this array.
But since, I was havin' some problem backtracking the queen. I asked for an advice and following that advice I wrote the code given below. This code works much betta then what I was initially trying to do. But is still not producing the required results.
The system, as suggested to me is:
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.
Here's the 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=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 out put I'm getting is:
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 1Please help me out to solve this.