8 Queens, problem with searching 2D array

Hello, I'm trying to solve the 8 queens problem, but I need some help searching the 2D array. I understand how the algorithm works, but the problem I always have is applying that algorithm to code. I've posted what I have so far. I have to do it this way, so don't tell me to combine functions or anything like that. Searching arrays like this really confuses me for some reason, so any help is great. Thanks!

Code:

---

#include <iostream>

using namespace std;

int board[8][8];

void resetBoard();
void displayBoard();
void addQueen(int row, int column);
void removeQueen(int row,int column);
void solve(int n, int column, int row);

bool isPathViable(int row, int column);
bool isPathSuccess();

int main()
{
        resetBoard();
       
        for(int i=1; i <= 8; ++i)
                //solve(...);
       
        return 0;
}

void resetBoard()
{
        for(int i=0; i < 8; ++i)
                for(int j=0; j < 8; ++j)
                        board[i][j]=0;
}

void displayBoard()
{
        for(int i=0; i < 8; ++i)
        {
                for(int j=0; j < 8; ++j)
                        cout << board[i][j] << " ";
               
                cout << "\n";
        }
}

void addQueen(int row,int column)
{
        board[row][column]=1;
}

void removeQueen(int row,int column)
{
        board[row][column]=0;
}

void solve(int n,int row, int column)
{
        addQueen(row,column);

        if(isPathSuccess())
                displayBoard();

        else if(isPathViable(row,column))
                for(int i=1; i <= n; ++i)
                        solve(n,i,column+1);



}


bool isPathViable(int row, int column)
{
        for(int i=0; i < column; ++i)
                if(board[row][i]==1)
                        return false;

        //Really confused on how to search this and check if a queen is safe

                else
                        return true;
}

bool isPathSuccess()
{
        int queens=0;

        for(int i=0; i < 8;i++)
                for(int j=0;j < 8;j++)
                        if(board[i][j]=1)
                                ++queens;

        if(queens==8)
                return true;

        else
                return false;
}

---

Can anyone help with this?

Quote:

---

Originally Posted by Sentral

Can anyone help with this?

---

Help with what?

Quote:

---

Originally Posted by tabstop

Help with what?

---

I've explained it. I don't know how to check if a queen is safe or not. How do I go about searching the board to find if a queen is in danger?

The queen is safe if there is no other queen in the same row, column, or diagonal. Looping over a row or column should be trivial. As far as diagonals go, if you want to save thinking, you can just search in each of the four diagonal directions NE, NW, SE, and SW looking for queens. So ask yourself: if you are at, say, [3][4] and want to move one square to the northeast, where you will be? What about two squares? Can you see a pattern?

Ok here is what I got to check if a path is viable, but I have a problem. I search through using for loops, and check if the element is equal to 1. If it is I return false because that path is not safe. However, this doesn't seem to work. The function returns numbers such as 253, or 252 which doesn't make sense. Anyone know why?

Code:

---

bool isPathViable(int row, int column)
{
        for(int i=0;i <= row; i++)        //Checks row
                if(board[row][i]==1)
                        return false;

        for(;row => 0,column => 0;--row,--column)        //Checks left and up diagonal
                if(board[row][column]==1)
                                return false;

        for(;row => 0,column => 0;++row,--column)        //Checks left and down diagonal
                if(board[row][column]==1)
                                return false;

       
}

---

Did you see that warning that says something like "not all paths return a value"? Did you notice how you don't ever bother to return true if the path is viable? Did you ever wonder what happened when you forgot to return a value and then tried to use it?

Thank you, I believe I got it now.

Code:

---

bool isPathViable(int row, int column)
{
        bool success;
       
        for( ;column >= 0; --column)        //Checks row
        {
                if(board[row][column]==1)
                        success=false;
       
                else if(board[row][column]==0)
                        success=true;
        }
       
        for( ; row >= 0, column >= 0;--row, --column)        //Checks left and up diagonal
        {
                if(board[row][column]==1)
                        success=false;

               
                else if(board[row][column]==0)
                        success=true;
        }
       
        for( ;row >= 0,column >= 0;++row,--column)        //Checks left and down diagonal
        {
                if(board[row][column]==1)
                        success=false;

               
                else if(board[row][column]==0)
                        success=true;
        }

        return success;
               
}

---

You still have two diagonals left to check, I think -- not to mention the fact that the third for-loop checks the diagonal, not of the square you want to look at, but of the square you finished the previous for loop at.

And notice that if you find an enemy, success must remain false no matter what else happens -- no setting it back to true!

Quote:

---

You still have two diagonals left to check, I think

---

I think I did that in the last two for loops. The first checks North West direction, and the second checks South West.

Quote:

---

not to mention the fact that the third for-loop checks the diagonal, not of the square you want to look at, but of the square you finished the previous for loop at.

---

What do you mean by this?

Quote:

---

And notice that if you find an enemy, success must remain false no matter what else happens -- no setting it back to true!

---

So you're saying don't use a bool variable? Just return true or false? I've tried that but it didn't work because the first return it comes in contact with terminates the function. How can I get around this?


Oh, and if I'm in first column and check if it's viable it returns false. How can this be?

Quote:

---

Originally Posted by Sentral

What do you mean by this?
And notice that if you find an enemy, success must remain false no matter what else happens -- no setting it back to true![/

---

Maybe because you function is searching for avaliablity. So if you search one path and recieve a false,
you then re-use your boolean variable for the next loop. Possibly re-initalising it to true..?

return an INT sybolising which direction you have been compromised in...?

Quote:

---

Originally Posted by Else

Maybe because you function is searching for avaliablity. So if you search one path and recieve a false,
you then re-use your boolean variable for the next loop. Possibly re-initalising it to true..?

---

Why would I reuse it? If it's false that means there is a queen that is threatening, so why would I go on to check other directions?

Quote:

---

Originally Posted by Sentral

Why would I reuse it? If it's false that means there is a queen that is threatening, so why would I go on to check other directions?

---

I don't know why you would want to. You do anyway, but I don't know why you would want to, and yes your variable does then get reset to true. The instant you get false, you want to return, because (a) checking more won't help so why bother and (b) this way you don't inadvertently destroy your result. Your first try was perfect in that regard, if only you hadn't forgotten to type "return true;" at the end of it.

Your row and column variables are changed by the second for-loop, until they walk off the board. So at the start of the third for-loop, that's where you start moving southwest, from that ending square.

You've got left+up and left+down, which means you have completely ignored right+down and right+up. You shouldn't.

Quote:

---

I don't know why you would want to. You do anyway, but I don't know why you would want to, and yes your variable does then get reset to true. The instant you get false, you want to return, because (a) checking more won't help so why bother and (b) this way you don't inadvertently destroy your result. Your first try was perfect in that regard, if only you hadn't forgotten to type "return true;" at the end of it.

---

Ok, so you are saying get rid of the "else's" and just return true at the end of the funtion, but still keep the "return false" in the if's?

Quote:

---

Your row and column variables are changed by the second for-loop, until they walk off the board. So at the start of the third for-loop, that's where you start moving southwest, from that ending square.

---

Oh wow I didn't even notice that! So I would have to initialize the for-loop with some variable and then assign my row and column into those it won't modify them?

Quote:

---

You've got left+up and left+down, which means you have completely ignored right+down and right+up. You shouldn't.

---

I believe this algorithm doesn't require that. You only have to check to the left because the placing of the queens goes from left to right. However, judging by my progress with this I could be wrong :D


EDIT- Hmmmmm... I still get falses returned even if the queen is in a safe spot. This is frustrating! :o