Determining whether a queen can attack another piece
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 posed this same question at the coderanch: Determining whether a queen can attack another piece (Java in General forum at JavaRanch)
Code:
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
}
