8 queens puzzle brute-force solvers part 1

May 2, 2015 · 8 minute read · Comments
code 8 queens puzzle

Brute-force

Explanation

Brute-force algorithms are also known as exhaustive algorithms, they consist of testing all possibilities with 8 (or more) queens on a chessboard like that for the first one:

In this case a limit of 8 queens is set to end the test and rollback the last placed queen, the next posibility tested will be:

It is clear that this algorithm is uneficient because the second placed queen is already invalid and next positionned and tested queens are just a waste of time. No solution can be found with 2 queens on the 2 first positions for example.

Uber-brute-force

Explanation

It’s possible to make an algorithm more uneficient with no limit of simultaneous placed queens like this chessboard as the first tested “solution”:

This tested chessboard is just insane, only a brute-force program can test this as a solution. But this algorithm is a floor value to test speed-ups and optimisations.

Implementation

This is the slowest implementation I have done to resolve this puzzle:

/** Chessboard represented by a list of lists. */
private final List<List<Boolean>> chessboard;

private void solve(final int x, final int y) {

    // Put a queen on the current position
    chessboard.get(x).set(y, Boolean.TRUE);

    // Test if the chessboard is a solution with exactly N queens
    if (checkSolutionChessboard()) {
        solutionCount++;
        print();
    }
    else {

        //Recursive call to the next position
        final int nextX = (x + 1) % chessboardSize;
        //Switch to the next line
        if (0 == nextX) {

            //End of the chessboard check
            if (y + 1 < chessboardSize) {
                solve(nextX, y + 1);
            }
        }
        else {
            solve(nextX, y);
        }
    }

    // Remove the queen on the current position
    chessboard.get(x).set(y, Boolean.FALSE);

    //Recursive call to the next position
    final int nextX = (x + 1) % chessboardSize;
    //Switch to the next line
    if (0 == nextX) {

        //End of the chessboard check
        if (y + 1 < chessboardSize) {
            solve(nextX, y + 1);
        }
    }
    else {
        solve(nextX, y);
    }
}

The complete implementation is in this source file SlowBruteForceNQueensSolverWithListsNoQueensLimit.

This implementation has a lot of weakness:

The algorithm don’t stop after placing N queens
The solution is checked by analyzing the full chessboard after placing each queen
The chessboard is represented by list of lists

The first point is a complexity overkill because it greatly increases the number of moves required to test all possible solutions on the NxN chessboard. It’s a waste of time to test any combination with over N queens, a back-track is needed to test another untested combination.

Benchmarks

These benchmarks are done on a Core i5 2500K:

chessboard size	execution time
4	4.57 ms
5	2.47 s
6	2h09m
7	too long…

Even on 6x6 chessboard, the time needed to count all solutions is very long!

Brute-force

Implementation

This is just the previous implementation with a maximum limit of N placed queens at the same time on the chessboard:

/** Chessboard represented by a list of lists. */
private final List<List<Boolean>> chessboard;

private void solve(final int x, final int y) {

    // Put a queen on the current position
    chessboard.get(x).set(y, Boolean.TRUE);

    // All queens are sets then a solution may be present
    if (getPlacedQueens() >= chessboardSize) {
        if (checkSolutionChessboard()) {
            solutionCount++;
            print();
        }
    }
    else {

        // Recursive call to the next position
        final int nextX = (x + 1) % chessboardSize;
        // Switch to the next line
        if (0 == nextX) {

            // End of the chessboard check
            if (y + 1 < chessboardSize) {
                solve(nextX, y + 1);
            }
        }
        else {
            solve(nextX, y);
        }
    }

    // Remove the queen on the current position
    chessboard.get(x).set(y, Boolean.FALSE);

    // Recursive call to the next position
    final int nextX = (x + 1) % chessboardSize;
    // Switch to the next line
    if (0 == nextX) {

        // End of the chessboard check
        if (y + 1 < chessboardSize) {
            solve(nextX, y + 1);
        }
    }
    else {
        solve(nextX, y);
    }
}

The complete implementation is in this source file SlowBruteForceNQueensSolverWithLists.

This implementation is still very unefficient but is a lot faster because a lot of dead combination are not tested. This optimisation is the first little step to implement a back-tracking algorithm.

Benchmarks

These benchmarks are done on a Core i5 2500K:

chessboard size	execution time
4	3.50 ms
5	21.95 ms
6	432.14 ms
7	20.90 s
8	19.50 m
9	too long…

On 8x8 chessboard, the time needed to count all solutions is quite long!