N-Queens using a stack, cannot find the bug

Question

I have attempted to complete my homework project and am seeking help finding a bug. I am using a backtracking algorithm to find all the solutions to an N-queens problem. My main concern is my conflict method-which is inside a stack class. Its purpose is to detect if the Queen object (parameter 1 of conflict method) being passed is in the same row, column, or diagonal as any other queens on the board. The queen object passed into the conflict method is stored inside the Queen class and its location is recorded with the help of an instance of the Point class. My code uses two methods in the Queen class that I created, public int getRow(), and public int getColumn(). Both return an int. Second parameter is a 2d array (or array of arrays) named board. Queens already on the board are denoted in this array with a boolean value of true. Boolean values of false indicate an empty square on the board.

Solution.n is a reference to a static int variable in another class. Its value denotes the edge of the board. Example...for the 8-Queens problem we create a 2d array with size 8. Solution.n is decremented by 1 to equal the last index of the 2d array.

Here is the code:

public boolean conflict(Queen x, boolean [][] board) //conflict method
{
    if(checkColumn(x, board) == false)
        return true; //conflict
    else if(checkRow(x, board) == false)
        return true; //conflict
    else if(checkDiagonal(x, board) == false )
        return true; //conflict
    else
        return false; //no conflict on board
}



private boolean checkColumn(Queen x, boolean [][] board)//returns true when column is safe
{
    int col = x.getColumn();
    for(int row = 0; row <= Solution.n; row++)
    {
        if(board[row][col] == true) //queen is in this column
        {
            return false;
        }
    }
    return true;
}

private boolean checkRow(Queen x, boolean [][] board) //returns true when row is safe
{
    int row = x.getRow();
    for(int col = 0; col <= Solution.n; col++)
    {
        if(board[row][col] == true) //queen is in this row
        {
            return false;
        }
    }
    return true;
}

private boolean checkDiagonal(Queen location, boolean [][] board) //returns true when diagonal is safe
{
    int row, col;
    row = location.getRow() - 1;
    col = location.getColumn() - 1;
    while(row >=0 && col >= 0) //iterate down-left
    {
        if(board[row][col] == true) //queen found?
        {
            return false;
        }
        row--;
        col--;
    }
    row = location.getRow() - 1;
    col = location.getColumn() + 1;
    while(row != -1 && col <= Solution.n) //iterate down-right
    {
        if(board[row][col] == true) //queen found?
        {

            return false;
        }
        row--;
        col++;
    }
    row = location.getRow() + 1;
    col = location.getColumn() + 1;
    while(row <= Solution.n && col <= Solution.n) //iterate up-right
    {
        if(board[row][col] == true) //queen found?
        {
            return false;
        }
        row++;
        col++;
    }
    row = location.getRow() +1;
    col = location.getColumn()-1;
    while(row <= Solution.n && col != -1) //iterate up-left
    {
        if(board[row][col] == true) //queen found?
        {
            return false;
        }
        row++;
        col--;
    }
    return true;
}

I am convinced this snippet of code contains a bug, but if i'm wrong then I apologize for wasting your time :P

Your help would be greatly appreciated. Thanks! :D

Answer 1

This answer won't solve your problem, since I'm not convinced your error is in the code you pasted, but here's your code, written a bit closer to how I might write it:

// returns true when column is safe
private boolean checkColumn(Queen x, boolean [][] board)
{
    int col = x.getColumn();
    for(int row = 0; row <= Solution.n; row++)
    {
        if(board[row][col]){ return false; }
    }
    return true;
}

// returns true when row is safe
private boolean checkRow(Queen x, boolean [][] board) 
{
    int row = x.getRow();
    for(int col = 0; col <= Solution.n; col++)
    {
        if(board[row][col]){ return false; }
    }
    return true;
}

// returns true if the position is valid given the board size
//  (as defined by Solution)
private boolean validPosition(int row, int col)
{
    if(0 > row || row > Solution.n){ return false; }
    if(0 > col || col > Solution.n){ return false; }
    return true;
}

// returns true when diagonal is safe
private boolean checkDiagonal(Queen x, boolean [][] board) 
{
    int row, col;

    // Down Left
    row = x.getRow();                           // "Start" on current position
    col = x.getColumn();
    while(true)
    {
        row--; col--;                           // Take a step in the direction
        if(!validPosition(row, col)){ break; }  // Stop if we've left the board
        if(board[row][col]){ return false; }    // Check whether it's occupied
    }

    // Down Right
    row = x.getRow();
    col = x.getColumn();
    while(true)
    {
        row--; col++;
        if(!validPosition(row, col)){ break; }
        if(board[row][col]){ return false; }
    }

    // Up Right
    row = x.getRow();
    col = x.getColumn();
    while(true)
    {
        row++; col++;
        if(!validPosition(row, col)){ break; }
        if(board[row][col]){ return false; }
    }

    // Up Left
    row = x.getRow();
    col = x.getColumn();
    while(true)
    {
        row++; col--;
        if(!validPosition(row, col)){ break; }
        if(board[row][col]){ return false; }
    }
    return true;
}

public boolean conflict(Queen x, boolean [][] board) //conflict method
{
    if     (  checkColumn(x, board) == false){ return true; }
    else if(     checkRow(x, board) == false){ return true; }
    else if(checkDiagonal(x, board) == false){ return true; }
    else                                     { return false; }
}

}

It simplifies a lot of the logic, adds a helper function validPosition(), and cleans up some of the tests and loops.

Answer 2

You have several small bugs in there - for example, you have loops that go from 0 to Solution.n, inclusive, while they should go to Solution.n-1. Most of the errors, however, can be eliminated by picking a more suitable data structure.

Think about it: you don't need a full NxN board to decide the placement of a queen:

• There's one queen per row, so queen's number is its row.
• There's one queen per column, so you need an array of boolean[N] to know which rows are taken.
• There's one queen per ascending diagonal, so you need an array of boolean[2N-1] to know which ascending diagonals are taken.

• There's one queen per descending diagonal, so you need an array of boolean[2N-1] to know which descending diagonals are taken.

  boolean[] columns = new boolean[N]; boolean[] ascending = new boolean[2*N-1]; boolean[] descending = new boolean[2*N-1];

At this point you've got all you need: instead of a square boolean[N][N] array you need three linear arrays of boolean. This lets you do your checks much faster, too:

int c = x.getColumn();
int r = x.getRow();
boolean conflict = columns[c]
                || ascending[r+c]
                || descending[N-r+c];

That's it - no loops required! Now you can code your backtracking algorithm using these three arrays instead of a square board.