3
\$\begingroup\$

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;
    }
 }
\$\endgroup\$
  • 1
    \$\begingroup\$ Possibly you can use a searching method with backtracking. Just iterate placing queens one by one, each time choosing a first free (not occupied and not attacked) position. If there is no free position for some n-th queen, step back and move the queen no. (n-1) from the current place to the next free position. If there's no free position, remove (n-1) and step back again. If you stepped back to empty board, there is no more possible queen arrangements. If you successfully moved a queen (n-1) in the 'back' step, proceed with placing the n-th one. Random placing is just too inefective. \$\endgroup\$ – CiaPan Oct 27 '17 at 6:18
  • \$\begingroup\$ Where's the main() function? \$\endgroup\$ – Toby Speight Oct 27 '17 at 7:44
  • \$\begingroup\$ @CiaPan thanks, but i think there is a better solution. \$\endgroup\$ – Ibrahim Ali Oct 27 '17 at 7:45
  • \$\begingroup\$ @TobySpeight simply invoke the class into the main() !! \$\endgroup\$ – Ibrahim Ali Oct 27 '17 at 7:46
  • \$\begingroup\$ You can't invoke a class - you can construct an instance of one, or invoke its static methods. Is startSimulation() supposed to be the main function? If so, you could call it main() instead. \$\endgroup\$ – Toby Speight Oct 27 '17 at 8:39
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the great answer, but it's seems that i already finished fast one but still have issue with set random queen. \$\endgroup\$ – Ibrahim Ali Oct 27 '17 at 12:34
  • \$\begingroup\$ There is another point worth considering: @IbrahimAli didn't say what actually his aim is, finding any valid arrangement or all valid arrangments of 8 Queens. Systematic search enclosed in a loop will do the latter (return all possible solutions, and each exactly once), while random generating can not (may well repeat answers and we never know if it found all possibilities; with poor RNG quality it may be even unable to find some). \$\endgroup\$ – CiaPan Oct 27 '17 at 12:55
  • \$\begingroup\$ @CiaPan I'm thinking for n position for n boolean simply i create a boolean array and use it's index by depend on random queens, every generated queens i set illegal index to false in the boolean array which will be short much time. \$\endgroup\$ – Ibrahim Ali Oct 27 '17 at 13:31
  • \$\begingroup\$ @Imus You don't need the do – while loop, as each placeQueens(i) invoked by the for (int i = 0; i < 8; i++) loop allocates a position in a separate row, hence collisions are impossible and testing for them is a waste of time. \$\endgroup\$ – CiaPan Oct 27 '17 at 13:39
  • \$\begingroup\$ Aha true CiaPan. Well spotted. I only did the minimal change to generate one on each row in the original code. That's why I just passed in that i to the method. I also noticed the now redundant check, but that only gains you less than a millisecond in finding the solution. So you can't really tell the difference anyway. \$\endgroup\$ – Imus Oct 27 '17 at 13:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.