Thread: 8 Queens problem

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;
}

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.)

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.

No, it's not the same. Read my post again. My system is more complex.

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.

First of all thanks for your help. By following your advice I wrote this code:

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...???

Why did you replicate logic from addQueen() in main()?

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