Determining whether a queen can attack another piece

[Jim Hester]

I'm working on a program to solve the n-queens problem, and am having trouble with determining whether a queen can attack another queen. For the problem, I assume that there is only 1 queen on each row, and they only move within that row to solve the problem. Thus, I can represent the locations of the queens with an array (int[] queens), where the position in the array is the row, and the value of the integer is the column. For example, queens[0] = 0 would mean the queen is in the top left corner of a board, and if there are 5 queens, queens[4] = 4 would indicate it's in the bottom right hand corner. I tried to make a simple problem below that just has a 5x5 board that sets the queens so they cannot attack each other. And I've narrowed down my problem to the "testAttack" method, but it's not working like I want it to. For that method, I assume that queens are not going to be in the same row, so the horizontal check would be redundant, so I'm just trying to implement the column check and the diagonal check.

Any help to improve the testAttack method would be helpful. thanks!

for reference, I also requested help here: http://www.java-forums.org/new-java/33235-determining-whether-queen-can-attack-another-piece.html#post147714

 import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // To hold the number of queens for the problem
        int numQueens;
        // Scanner class to get the input from user
        Scanner keyboard = new Scanner(System.in);
        // Prompt the user for the number of Queens
        System.out.println("Welcome to the N-Queens Solver.");
        System.out.println();
        QueenBoard test = new QueenBoard(5);
        test.setToGoal();

        boolean testGoal = test.isGoalState(test.getQueens());
        test.printBoard();
        System.out.println("Should be false: " + testGoal);
    }

public static class QueenBoard {
    // Going to use 2 dimensional array to represent the board. 1 will represent
    // a Queen, while 0 is a blank space
    private int[][] board;
    // the queen positions will be represented by a single array, since there
    // can only be one queen per row
    private int[] queens;
    // keeps track of what n is
    private int nSize = 0;

    // Constructor allows for a board with width/length n
    public QueenBoard (int n){
        board = new int[n][n];
        queens = new int[n];
        nSize = n;
    }

    public void setToGoal(){
        queens[0]=4;
        queens[1]=1;
        queens[2]=3;
        queens[3]=0;
        queens[4]=2;
        this.convertQueensToBoard();
    }

    public int[] getQueens(){
        return queens;
    }
    
/* Because we assume there are no queens in the same row, all we much do is
 * check to see if there is a queen in the same column or in a diagonal
 * line. This method checks to see if a queen placement at a given row/column
 * combination is valid
 */
    public boolean testAttack(int row, int column){
        for (int i = 1; i <= row; i++)
                // checks columns
            if (queens[row - i] == column
                // check diagonal to upper left
                || queens[row -1] == column - i
                // check diagonal to upper right
                || queens[row -1] == column + i)
                // if any of these match, there is a conflict
                return false;
        // only get to this point if there are no conflicts
        return true;
    }

        public boolean isGoalState(int[] state){
        boolean goal = false;
        for (int i=0; i < nSize; i++){
            // if a queen can attack another queen, then we know we haven't
            // reached our goal state yet and we can stop the for loop and
            // select a new operator
            if (testAttack(i, state[i]) == true){
                goal = false;
                System.out.println("Setting to False");
            }
            else {
                System.out.println("Setting to True");
                goal = true;
            }
        }
        return goal;
    }

            // Method to print the board
    public void printBoard(){
        System.out.println();
        // loop through the rows of the board
        for (int i = 0; i < board.length; i++){
            // loop through each column for each row of the board
            for (int j = 0; j < board.length; j++){
                // if the value is blank, print out an X
                if (board[i][j] == 0)
                    System.out.print(" .");
                // otherwise (if there's a value) there must be a queen,
                // so print out a Q
                else
                    System.out.print(" Q");
                // at the end of each row, print a new line
                if (j == board.length-1)
                    System.out.println();
            }
        }
    }

    private void convertQueensToBoard(){
        for (int i=0; i<nSize; i++){
            for (int j=0; j<nSize; j++){
                if (queens[i] == j)
                    board[i][j] = 1;
                else
                    board[i][j] = 0;
            } // inner for loop
        } // outer for loop
      } // end of method
    } // end of class

}   

[Roger F. Gay]

This is the first time I've ever heard of this problem, so forgive me if I'm being naive. Checking to see if the column is the same seems to be just a matter of seeing if the position value is equal, while an opportunity for a diagonal attack is one in which the absolute value of delta x and delta y are the same. So, what's the real point of building the algorithm? Are you trying to find the fastest method, or what? Should it gear up to large numbers of queens (so you need speed)?

[Jim Hester]

Roger F. Gay wrote: Should it gear up to large numbers of queens (so you need speed)?

This one. The problem I'm working on actually has a minimum of 10 queens on a n x n board (where n is the number of queens). Needs to be able to ramp up to N queens where N can be a very large value. Thanks for your response.

[Roger F. Gay]

OK, and it's not difficult to notice that testing every possibility becomes computationally expensive very quickly. Wikipedia supplies some numbers: http://en.wikipedia.org/wiki/Eight_queens_puzzle

Is there a description of your testAttack method somewhere, so we can easily understand how you're logically approaching the problem without figuring it out for ourselves?

[Jim Hester]

Roger F. Gay wrote:OK, and it's not difficult to notice that testing every possibility becomes computationally expensive very quickly. Wikipedia supplies some numbers: http://en.wikipedia.org/wiki/Eight_queens_puzzle

Is there a description of your testAttack method somewhere, so we can easily understand how you're logically approaching the problem without figuring it out for ourselves?

well, I reworked the 'testAttack' by both renaming it so it's clear what it should be returning (it should return true if the queen on the row,column provided can attack another queen, otherwise it should return false) and b/c it wasn't testing in all 4 directions that a diagonal could exist. It's not elegant, but it should be a lot more straightforward. Unfortunately, it still finds collisions when it should return false, so I did something wrong.

/* Because we assume there are no queens in the same row, all we much do is
 * check to see if there is a queen in the same column or in a diagonal
 * line. This method checks to see if a queen placement at a given row/column
 * combination is valid
 */
    public boolean canAttack(int row, int column){
        // first check is to see if there another queen in the same column as
        // the queen we're testing? loop through and first check to see that the
        // queen you see isn't the one attacking
        for (int i = 0; i < nSize; i++){
            // if it's the queen in (row,column), just skip it
            System.out.println("performing column check on row: " + i);
            if (row == i){
                continue;
            // otherwise, there shouldn't be a queen in same column
            } else if (queens[i] == column)
                return true;
        } // closes column check
        int rowCheck = Integer.valueOf(row--);
        int colCheck = Integer.valueOf(column--);
        // Check to see if a queen is diagonal to the reference queen.
        // First, we check up and to the left
        while (rowCheck >= 0
                && colCheck >=0){
            System.out.println("performing up, left on row: " + rowCheck);
            if (board[rowCheck][colCheck] == 1) {
                return true;
            } else{
                rowCheck--;
                colCheck--;
            }
        }
        // Next, we check up and to the right
        rowCheck = Integer.valueOf(row--);
        colCheck = Integer.valueOf(column++);
        while (rowCheck >= 0 && colCheck < nSize){
            System.out.println("performing up, right on row: " + rowCheck);
            if (board[rowCheck][colCheck] == 1){
                return true;
            } else{
                rowCheck--;
                colCheck++;
            }
        }
        // Next, we check down and to the left
        rowCheck = Integer.valueOf(row++);
        colCheck = Integer.valueOf(column--);
        while (rowCheck < nSize && colCheck >= 0){
            System.out.println("performing down, left on row: " + rowCheck);
            if (board[rowCheck][colCheck] == 1){
                return true;
            } else {
                rowCheck++;
                colCheck--;
            }
        }
        // Finally, we check down and to the right
        rowCheck = Integer.valueOf(row++);
        colCheck = Integer.valueOf(column++);
        while (rowCheck < nSize && colCheck < nSize){
            System.out.println("performing down, right on row: " + rowCheck);
            if (board[rowCheck][colCheck] == 1){
                return true;
            } else {
                rowCheck++;
                colCheck++;
            }
        }
        // if the method gets to this point, there are no queens that can be
        // reached by the queen at the selected (row,column), so return false
        return false;
      }

[Roger F. Gay]

If you're checking them all by "brute force," couldn't you just:

if (queen[i] == queen[j]) return(true);

rowdif = Math.abs(i-j);
coldif = Math.abs(queen{i]-queen[j]);

if (rowdif == coldif) return (true);

[Jim Hester]

Roger F. Gay wrote:If you're checking them all by "brute force," couldn't you just:

if (queen[i] == queen[j]) return(true);

rowdif = Math.abs(i-j);
coldif = Math.abs(queen{i]-queen[j]);

if (rowdif == coldif) return (true);

I took this and created the method below, but it still isn't finding conflicts AND it's finding conflicts where it isn't supposed to (on row 3 of my test setup)... Any idea what I'm doing wrong?

    public boolean canAttack(int row, int column){
        // first check is to see if there another queen in the same column as
        // the queen we're testing? loop through and first check to see that the
        // queen you see isn't the one attacking
        // if the method gets to this point, there are no queens that can be
        // reached by the queen at the selected (row,column), so return false

        for (int i=0; i<nSize; i++){
            if (queens[i] == column){
                System.out.println("Found column conflict on pass: " + (i+1));
                return true;
            }
            else if (Math.abs(i - row) == Math.abs(i - column)){
                System.out.println("Found diagonal conflict on pass: " + (i+1));
                return true;
            }
        }
        return false;
    }

>

[Jim Hester]

never mind, found and corrected problem. First correction found the queen on the row I was checking. This one doesn't.

    public boolean canAttack(int row, int column){
        // first check is to see if there another queen in the same column as
        // the queen we're testing? loop through and first check to see that the
        // queen you see isn't the one attacking
        // if the method gets to this point, there are no queens that can be
        // reached by the queen at the selected (row,column), so return false

        for (int i=0; i<nSize; i++){
            if (queens[i] == column && i!=row){
                System.out.println("Found column conflict on pass: " + (i+1));
                return true;
            }
            else if (Math.abs(i - row) == Math.abs(i - column)){
                System.out.println("Found diagonal conflict on pass: " + (i+1));
                return true;
            }
        }
        return false;
    }

[Jim Hester]

ok, it was failing to check for itself in the diagonals. Now it does. Works like a champ! Thanks, Roger!

    public boolean canAttack(int row, int column){
        // first check is to see if there another queen in the same column as
        // the queen we're testing? loop through and first check to see that the
        // queen you see isn't the one attacking
        // if the method gets to this point, there are no queens that can be
        // reached by the queen at the selected (row,column), so return false

        for (int i=0; i < nSize; i++){
            if (queens[i] == column
                    && i!=row){
                System.out.println("Found column conflict on row: " + i);
                return true;
            }
            else if ((Math.abs(i - row) == Math.abs(queens[i] - column))
                    && (Math.abs(i - row) != 0)){
                System.out.println("Found diagonal conflict on row: " + i);
                return true;
            }
        }
        return false;
    }

[Roger F. Gay]

A little faster, on average. Makes a significant difference when something is repeated many, many times.

 
 public boolean canAttack(int row, int column){  
         // first check is to see if there another queen in the same column as  
         // the queen we're testing? loop through and first check to see that the  
         // queen you see isn't the one attacking  
         // if the method gets to this point, there are no queens that can be  
         // reached by the queen at the selected (row,column), so return false  
   
         for (int i=0; i < nSize; i++){  
           if (i != row) {
             if (queens[i] == column){  
                 System.out.println("Found column conflict on row: " + i);  
                 return true;  
             } else if ((Math.abs(i - row) == Math.abs(queens[i] - column)){  
                 System.out.println("Found diagonal conflict on row: " + i);  
                 return true;  
             }
           }
         }  
         return false;  
     }