Eight queens with Java

Question

The following code works great but take 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; i++) {
            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.length; i++) {
            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.length; i++) {
            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.length; i++) {
            if (isOccupied(board[i])) {
                for (int j = 0; j < board.length; j++) {
                    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.length; i++)
            board[i] = ' ';
        return board;
    }

    /** print displays the board */
    public static void print(char[] board) {
        for (int i = 0; i < board.length; i++) {
            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;
    }
 }

Answer 1

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 a 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; i++) {
        do {
            location = placeQueens(i);
        } while (isOccupied(board[location]));
        board[location] = 'Q';
    }
}

/** placeQueens randomly places one queen on the board */
public static int placeQueens(int row) {
    return row * 8 + (int)(Math.random() * 8);
}

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.