Eight Queens Algorithms

Question

I asked a question about solving the problem of eight queens using Java. I have a backtracking algorithm to solve the problem.

I tried using this algorithm, but I do not know what happened to my code. It holds up to 7 queens.

Here is the Queen Class:

public class Queen { //Number of rows or columns public static final int BOARD_SIZE = 8; boolean[][] board; //Indicate an empty square public static final boolean EMPTY = false; //Indicate a square which containing a queen public static final boolean QUEEN = true; //Number of moves public static final int MOVES = 4; //Horizontal moves int[] horizontal; //Vertical moves int[] vertical; public int queens = 0; public Queen() { //Constructor creates an empty board board = new boolean[BOARD_SIZE][BOARD_SIZE]; for (int row = 0; row < board.length; row++) { for (int col = 0; col < board[row].length; col++) { board[row][col] = EMPTY; } } horizontal = new int[MOVES]; vertical = new int[MOVES]; // up right horizontal[0] = -1; vertical[0] = 1; // down left horizontal[1] = 1; vertical[1] = -1; // up left horizontal[2] = -1; vertical[2] = -1; // down right horizontal[3] = 1; vertical[3] = 1; } public boolean placeQueens (int column) { if (column > BOARD_SIZE) { return true; } else { boolean queenPlaced = false; int row = 1; while (!queenPlaced && row < BOARD_SIZE) { if (isUnderAttack(row, column)) { ++row; }// end if else{ setQueen(row, column); queenPlaced = placeQueens(column + 1); if (!queenPlaced) { removeQueen(row,column); ++row; }// end if }// end else }// end while return queenPlaced; }// end else } private void removeQueen(int row, int column) { board[row][column] = EMPTY; System.out.printf("queen REMOVED from [%d][%d]\n", row, column); --queens; } private void setQueen(int row, int column) { board[row][column] = QUEEN; System.out.printf("queen PLACED in [%d][%d]\n", row, column); ++queens; } public boolean isUnderAttack(int row, int col) { boolean condition = false; // check row for (int column = 0; column < BOARD_SIZE; column++) { if ((board[row][column] == true)) { condition = true; } } // check column for (int row_ = 0; row_ < board.length; row_++) { if (board[row_][col] == true) { condition = true; } } // check diagonal for (int row_ = row, col_ = col; row_ >= 0 && col_ < 8; row_ += horizontal[0], col_ += vertical[0]) { if (board[row_][col_] == true) { condition = true; } } for (int row_ = row, col_ = col; row_ < 8 && col_ >= 0; row_ += horizontal[1], col_ += vertical[1]) { if (board[row_][col_] == true) { condition = true; } } for (int row_ = row, col_ = col; row_ >= 0 && col_ >= 0; row_ += horizontal[2], col_ += vertical[2]) { if (board[row_][col_] == true) { condition = true; } } for (int row_ = row, col_ = col; row_ < 8 && col_ < 8; row_ += horizontal[3], col_ += vertical[3]) { if (board[row_][col_] == true) { condition = true; } } return condition; } public void displayBoard () { int counter = 0; for (int row = 0; row < board.length; row++) { for (int col = 0; col < board[row].length; col++) { if (board[row][col] == true) { System.out.printf("|%s|", "x"); counter++; } else { System.out.printf("|%s|", "o"); } } System.out.println(); } System.out.printf("%d queens has been placed\n", counter); } } 

Answer 1

In Java, arrays are indexed to 0 , which means that the first element has an index of 0. You do not seem to fully understand this important fact, which led to writing code with many errors .

One problem here:

 int row = 1; 

It should be:

 int row = 0; 

---

The second problem is here:

 if (column > BOARD_SIZE) { return true; } 

It should be like this:

 if (column >= BOARD_SIZE) { return true; } 

---

You have not published the rest of your code, but I bet you have a third error in your code when calling the placeQueens method. If I know what kind of person you are, then you probably did this:

 queen.placeQueens(1); 

But it should be so:

 queen.placeQueens(0); 

---

With all these changes, everything works as expected. The final result:

  | x || o || o || o || o || o || o || o |
 | o || o || o || o || o || o || x || o |
 | o || o || o || o || x || o || o || o |
 | o || o || o || o || o || o || o || x |
 | o || x || o || o || o || o || o || o |
 | o || o || o || x || o || o || o || o |
 | o || o || o || o || o || x || o || o |
 | o || o || x || o || o || o || o || o |
 8 queens has been placed

See how it works online: ideone

Answer 2

The isUnderAttack method has several hardcodes:

// diagonally check the place of use 8 with BOARD_SIZE

use:

 col_ < BOARD_SIZE 

instead

 col_ < 8 

and it might be better to make BOARD_SIZE not static, but to make it an input parameter, make the code more universal and perform testing for boardSize = 4 or 12

Answer 3

I wrote a generic code that works for any number of queens.

The result is presented in 0 or 1. 1 is the queen, 0 is the empty square.

 static int[][] setupEightQueens(int queensNum) { if (queensNum <= 0) return new int[][] { {} }; int[][] chessField = new int[queensNum][queensNum]; int n = chessField.length; int startJ = 0; for (int i = 0; i < n; i++) { for (int j = startJ; j < n; j += 2) { chessField[j][i] = 1; i++; } i--; startJ++; } return chessField; } 

Conclusion for verified 4, 8, 11 queens counts:

__________________________
queens: 4
1 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
__________________________
queens: 8
1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1
__________________________
queens: 11
1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 0
0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0 0 0 0

---