Eight queens with 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 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 &lt; 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.