I am working a problem that seems to be somewhat famous among beginning programmers, the 8 queens puzzle. I have seen several solutions to this problems using 2D arrays, recursion etc, but this problem is an assignment given in CS course book chapter introducing 1D arrays, so the available techniques to solve this problem are limited.
The procedure I have used, is by first creating a 1D array with the size of 64, which makes possible positions to place queens from index 0 to 63. A random position index is then generated, and a test is preformed to check if there is any queens attacking this position. If this position is not attacked by any queens, a queen is placed by setting the board[position] = true. When a queen is placed, the queenCount is incremented, and this process repeats until 8 queens have been placed.
If queens are placed in such a way that it is impossible to place 8, the board resets after 1 millisecond by preforming a timecheck, and retries to place the 8 queens. At the best I am able to place 7 queens, but the last remaining one is never placed. Each attempt is printed, along with queenCount for this attempt. Is it possible to use this approach, or is it a dead end?
Code example below:
package ch7;
public class Chapter_07_E22_EightQueens64bool {
public static void main(String[] args) {
int queenCount = 0;
int attemptCount = 0;
boolean[] board = new boolean[8 * 8];
final long TIME_LIMIT = 1; //Milliseconds
long startTime = System.currentTimeMillis();
while (queenCount < 8) {
int position = placeQueen(board.length);
if(checkPosition(position, board) && !board[position]) {
board[position] = true;
queenCount++;
}
long timeCheck = System.currentTimeMillis();
if (timeCheck - startTime > TIME_LIMIT) {
clearBoard(board);
queenCount = 0;
startTime = System.currentTimeMillis();
}
System.out.println("Attempt #" + ++attemptCount);
System.out.println(queenCount + " queens placed.");
printBoard(board);
}
}
public static void printBoard(boolean[] board) {
for (int i = 0; i < board.length; i++) {
if (board[i])
System.out.print("|Q");
else
System.out.print("| ");
if ((i + 1) % 8 == 0)
System.out.println("|");
}
}
public static int placeQueen(int boardSize) {
return (int)(Math.random() * boardSize);
}
public static boolean[] clearBoard(boolean[] board) {
for (int i = 0; i < board.length; i++)
board[i] = false;
return board;
}
public static boolean checkPosition(int position, boolean[] board) {
return checkTop(position, board) && checkBottom(position, board) && checkLeft(position, board) &&
checkRight(position, board) && checkTopLeft(position, board) && checkTopRight(position, board) &&
checkBottomLeft(position, board) && checkBottomRight(position, board);
}
public static boolean checkTop(int position, boolean[] board) {
// Checks each field above the current position while i >= 8
for (int i = position; i >= 8; i -= 8) {
if (board[i - 8])
return false;
}
return true;
}
public static boolean checkBottom(int position, boolean[] board) {
// Checks each field below the current position while i <= 55;
for (int i = position; i <= 55; i += 8) {
if (board[i + 8])
return false;
}
return true;
}
public static boolean checkRight(int position, boolean[] board) {
// Checks each field to the right of the current position while i % 8 < 7
for (int i = position; i % 8 < 7; i += 1) {
if (board[i + 1])
return false;
}
return true;
}
public static boolean checkLeft(int position, boolean[] board) {
// Checks each field to the left of the current position while i % 8 != 0
for (int i = position; i % 8 != 0; i -= 1) {
if (board[i - 1])
return false;
}
return true;
}
public static boolean checkTopLeft(int position, boolean[] board) {
// Checks each field top left of the current position while i >= 9
for (int i = position; i >= 9; i -= 9) {
if (board[i - 9])
return false;
}
return true;
}
public static boolean checkTopRight(int position, boolean[] board) {
// Checks each field top right of the current position while i >= 7
for (int i = position; i >= 7; i -= 7) {
if (board[i - 7])
return false;
}
return true;
}
public static boolean checkBottomRight(int position, boolean[] board) {
// Checks each field below the current position while i <= 54
for (int i = position; i <= 54; i += 9) {
if (board[i + 9])
return false;
}
return true;
}
public static boolean checkBottomLeft(int position, boolean[] board) {
// Checks each field below the current position while i <= 56
for (int i = position; i <= 56; i += 7) {
if (board[i + 7])
return false;
}
return true;
}
}
After working on this problem for a few days, I now have a solution that works that in a reasonable amount of time for N <= 20. It goes like this.
For i < N, initialize queens[i] = i. Each row can only hold 1 value, so no need to check for collisions on the left or right. As long as there is no duplicate values in the array, there will not be any column collisions either.
Use the method to check if a queen at a given point, shares a diagonal with a queen at another given point. The method checks to see if the distance between x1 and x0 is equal to the distance of y1 and y0. If the distance is equal, then the co-ordinates (x0,y0) and (x1,y1) share the same diagonal.
Use another method to invoke shareDiagonal(int x0, int y0, int x1, int y1) to check if a queen at a given row, for example on row 7, collides with a queen on any rows above row 7. As mentioned, only the rows above the given row are checked. The reason is that if you for example are checking row2 for any diagonal collisions, any collision with rows below row 2 will be revealed when checking a row with a higher index value. If a queen on row 2 collides with a queen on row 4, this will be revealed when checking row 4 and the rows above.
A third checking method invokes checkRowForCollision(int[] queens, int row), where each row is traversed checking for collisions on the rows above. Row 1 is checked if there is any collisions with queens on row 0, Row 2 is checked if there is any collisions on row 0 and 1, row 3 is checked if there is any collisions on row 0, 1 and 2, etc..
While there is diagonal collisions between any of the queens, the board shuffles until it shows a solution where no queens attack each other.
Code example below:
package ch7;
public class Chapter_07_E22_EightQueens {
static final int N = 8;
public static void main(String[] args) {
int[] queens = new int[N];
int attempts = 0;
for (int i = 0; i < N; i++)
queens[i] = i;
while (checkBoardForCollision(queens)) {
shuffleBoard(queens);
attempts++;
}
printBoard(queens);
System.out.println("Solution found in " + attempts + " attempts");
}
public static void printBoard(int[] queens) {
for (int row = 0; row < N; row++) {
System.out.printf("%-1c", '|');
for (int column = 0; column < N; column++) {
System.out.printf("%-1c|", (queens[row] == column) ? 'Q' : ' ');
}
System.out.println();
}
}
public static boolean shareDiagonal(int x0, int y0, int x1, int y1) {
int dy = Math.abs(y1 - y0);
int dx = Math.abs(x1 - x0);
return dx == dy;
}
public static boolean checkRowForCollision(int[] queens, int row) {
for (int i = 0; i < row; i++) {
if (shareDiagonal(i, queens[i], row, queens[row]))
return true;
}
return false;
}
public static boolean checkBoardForCollision(int[] queens) {
for (int row = 0; row < queens.length; row++)
if (checkRowForCollision(queens, row))
return true;
return false;
}
public static int[] shuffleBoard(int[] queens) {
for (int i = queens.length - 1; i > 0; i--) {
int j = (int)(Math.random() * (i + 1));
int temp = queens[i];
queens[i] = queens[j];
queens[j] = temp;
}
return queens;
}
}