What are the eight queens Java?
The following code works great but takes too much time. placeQueens requires much time too. The program takes 5-10 seconds.
public class EightQueen {
public static void startSimulation(){
long startTime = System.currentTimeMillis();
char[] board; // Create an array
// Repeat while queens are attacking
do {
// Generate a board
board = getNewBoard();
// Place eight queens
placeQueens(board);
} while (isAttacking(board));
// Display solution
print(board);
long endTime = System.currentTimeMillis();
System.out.println(endTime - startTime);
}
/** placeQueens randomly places eight queens on the board*/
public static void placeQueens(char[] board) {
int location;
for (int i = 0; i < 8> do {
location = placeQueens();
} while (isOccupied(board[location]));
board[location] = 'Q';
}
}
/** placeQueens randomly places one queen on the board */
public static int placeQueens() {
return (int)(Math.random() * 64);
}
/** isAttacking returns true if two queens are attacking each other */
public static boolean isAttacking(char[] board) {
return isSameRow(board) || isSameColumn(board) || isSameDiagonal(board);
}
/** isSameRow returns true if two queens are in the same row */
public static boolean isSameRow(char[] board) {
int[] rows = new int[8];
for (int i = 0; i < board> if (isOccupied(board[i])) {
rows[getRow(i)]++;
}
if (rows[getRow(i)] > 1)
return true;
}
return false;
}
/** isSameColumn returns true if two queens are in the same column */
public static boolean isSameColumn(char[] board) {
int[] columns = new int[8];
for (int i = 0; i < board> if (isOccupied(board[i])) {
columns[getColumn(i)]++;
}
if (columns[getColumn(i)] > 1)
return true;
}
return false;
}
/** isSameDiagonal returns true if two queens are on the same diagonal */
public static boolean isSameDiagonal(char[] board) {
for (int i = 0; i < board> if (isOccupied(board[i])) {
for (int j = 0; j < board> if (isOccupied(board[j]) && Math.abs(getColumn(j) - getColumn(i)) ==
Math.abs(getRow(j) - getRow(i)) && j != i) {
return true;
}
}
}
}
return false;
}
/** isOccupied returns true if the element in x is the char Q */
public static boolean isOccupied(char x) {
return x == 'Q';
}
/** getNewBoard returns a char array filled with blank space */
public static char[] getNewBoard() {
char[] board = new char[64];
for (int i = 0; i < board> board[i] = ' ';
return board;
}
/** print displays the board */
public static void print(char[] board) {
for (int i = 0; i < board> System.out.print(
"|" + ((getRow(i + 1) == 0) ? board[i] + "|n" : board[i]));
}
}
/** getRow returns the row number that corresponds to the given index */
public static int getRow(int index) {
return index % 8;
}
/** getColumn returns the column number that corresponds to the given index */
public static int getColumn(int index) {
return index / 8;
}
}
For eight queens java, Just like bogosort will never be a fast sorting algorithm. Your "throw away the board and randomly place N new queens" solution will never really be faster than those 5 to 10 seconds.
Nevertheless it made me happy to see that it actually does find a solution somewhat consistently. And the question itself is composed fine as well, so I do think it deserves an answer.
Like CiaPan already suggested in a comment, a far better way to solve the n-queens problem is with backtracking. My quick test program with this approach solves the 8-queens in 1 millisecond (or less). (And the 20-queens in 50 ms).
However, the "reset and randomly place n new queens" approach is interesting to see, so let's add one major improvement to speed up finding a solution.
/** placeQueens randomly places eight queens on the board*/
public static void placeQueens(char[] board) {
int location;
for (int i = 0; i < 8 xss=removed board[location] = 'Q'>This little change here got the time till solution down to under 100 ms consistently. Why? Because this reduces the search space from O(n³) to O(n²). The reason this works is that in all solutions there is exactly 1 queen on each row. So I generate one randomly for each row, instead of on the entire board.