8 Queens, problem with searching 2D array

Ok, here is the code that I'm still having trouble with. It returns false, even when the queen is in a safe spot, and if it's in the first column with no other queens. I'm only checking to the left, because the recursive algorithm places queens from left to right. This seems so simple, yet it doesn't want to work. Any help is appreciated, I've been going crazy trying to figure out what's wrong.

Code:

---

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

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

        return true;
               
}

---

Did you put the queen on the board already? If so, the very first thing you do is check the square you just filled.

Here is full code. However, I get weird results when I check for a queen.

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 row, int column);

int main()
{
        int n=8;

        resetBoard();
       
       
        /*for(int i=0; i < n; ++i)
                solve(n,0,i);*/

        addQueen(3,2);
        addQueen(3,3);
        displayBoard();
        cout << isPathViable(3,3);

        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(row,column))
                displayBoard();

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

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

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

        return true;
               
}

bool isPathSuccess(int row, int column)
{
        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 && isPathViable(row,column))
                return true;

        else
                return false;
}

---

So the answer to the question is "yes". You put the queen down on a square, and then you check whether the square is covered. By definition, it will be covered, by the queen you just put down. You have to check before placing the queen, not after.

Quote:

---

Originally Posted by tabstop

So the answer to the question is "yes". You put the queen down on a square, and then you check whether the square is covered. By definition, it will be covered, by the queen you just put down. You have to check before placing the queen, not after.

---

Oh I see, that was pretty stupid.

I'm now having trouble with the actual function that solves it, when I display the board to see what is going on, almost all the board is covered in ones.

Code:

---

int main()
{
        int n=8;

        resetBoard();
       



        for(int i=0; i < n; ++i)
                solve(n,i,0);

        displayBoard();


        return 0;
}

---

Code:

---

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

        if(isPathSuccess(row,column))
                displayBoard();

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

---

if(board[i][j]=1)

is assignemnt not comparison

Quote:

---

Originally Posted by vart

if(board[i][j]=1)

is assignemnt not comparison

---

Thanks I missed that somehow. It corrected the board flooding with 1's, but now no queens are placed, even though I am placing them in my solve function.


I've found that if I comment out the removeQueen function, all the 1's are straight down the first column, but there are no queens in the other columns. For some reason it's not incrementing to the next column, but shouldn't the "column+1" that I have deal with that?

Quote:

---

Originally Posted by Sentral

Thanks I missed that somehow. It corrected the board flooding with 1's, but now no queens are placed, even though I am placing them in my solve function.

---

I have this vague feeling that removeQueen might remove the queens from the board.

Quote:

---

Originally Posted by tabstop

I have this vague feeling that removeQueen might remove the queens from the board.

---

Yes, you're right, but only at the specified "row,column" position and only if it ever reaches that point. Once the for loop in the solve function terminates, it would then call removeQueen, which would take that away from the board because that spot won't work.

Quote:

---

Originally Posted by Sentral

Yes, you're right, but only at the specified "row,column" position and only if it ever reaches that point. Once the for loop in the solve function terminates, it would then call removeQueen, which would take that away from the board because that spot won't work.

---

Note that "only if it ever reaches that point" is the same as "always", since there is no control path through the function that does not execute that line.

bool isPathViable(int row, int column)

is called AFTER the Queen is placed in the (row,column)

if(board[row][i]==1) for i == column will be ALWAYS true

so

Code:

---

void solve(int n,int row, int column)
{
    if(isPathViable(row,column))
  {
        addQueen(row,column);
        if(column == 8)
            displayBoard();
        else
            for(int i=0; i < n; ++i)
                solve(n,i,column+1);
        removeQueen(row,column);
  }
}

---

so,ething like that maybe?

Quote:

---

Originally Posted by tabstop

Note that "only if it ever reaches that point" is the same as "always", since there is no control path through the function that does not execute that line.

---

I thought since I made a recursive call, it would go the beginning of the function, and not execute the remove function. So why would I need a control path?

I'd check that this expression in the for() statements

row >= 0, column >= 0

really does what you hope it does. You'd probably want some sort of logical operator there instead of the comma.

Come to think of it, the variables used inside the for loop might need some tweaking as well. The way it's written you're only checking one square for each for loop, but you're doing it a bunch of times.

Quote:

---

Originally Posted by Sentral

I thought since I made a recursive call, it would go the beginning of the function, and not execute the remove function. So why would I need a control path?

---

Control paths are not sometime things; every function by definition has (at least one) control path that specifies which statements are executed. (Some people call them "flowcharts" and draw them with boxes.) They exist whether or not you pay attention to them.

Recursive calls are fine and all, but a function always returns to where it was called from, so the function that calls itself recursively will still finish and run the rest of the function.

Quote:

---

Originally Posted by KCfromNC

I'd check that this expression in the for() statements

row >= 0, column >= 0

really does what you hope it does. You'd probably want some sort of logical operator there instead of the comma.

Come to think of it, the variables used inside the for loop might need some tweaking as well. The way it's written you're only checking one square for each for loop, but you're doing it a bunch of times.

---

I've fixed that, but I didn't post that code.

Quote:

---

Control paths are not sometime things; every function by definition has (at least one) control path that specifies which statements are executed. (Some people call them "flowcharts" and draw them with boxes.) They exist whether or not you pay attention to them.

Recursive calls are fine and all, but a function always returns to where it was called from, so the function that calls itself recursively will still finish and run the rest of the function.

---

I've put an else if(!isPathViable(row,column)) in the solve function, but It still didn't work. Why won't my recursive call increment to the next column. It doesn't even seem like it's getting called.