8 queens puzzle brute-force solvers part 2

May 6, 2015 · 11 minute read · Comments
code8 queens puzzle

Adding a queen constraint

Explaination

Constraint programming consists of use some data structure to store some contraints that can be modified and checked faster than recompute it at each algorithm step.

In the N-queens-puzzle, the number of currently placed queens can stored in a variable, when a queen is put on the chessboard this variable must be incremented and when a queen is remove this variable must be decremented.

Implementation

This is the previous implementation with a queen counter (variable placedQueens) 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;
/** Current number of queens on the chessboard. */
private int placedQueens;

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

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

    // All queens are sets then a solution may be present
    if (placedQueens >= 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
    placedQueens--;
    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 BruteForceNQueensSolverWithLists.

Benchmarks

These benchmarks are done on a Core i5 2500K:

chessboard size	execution time	number of runs
4	146.68 µs	5000
5	4.24 ms	5000
6	162.88 ms	500
7	7.49 s	50
8	6.20 m	5
9	6.10 h	1
10	too long…

On 9x9 chessboard, the needed time to count all solutions is very long!

Algorithms comparisons

Comparison of the previous and this algorithm:

The number of read square is lower with the queen constraint because the chessboard don’t need to be read to check the number of placed queens.

Use a two-dimensional array for the chessboard

Explaination

The data structure used to represent the chessboard can be changed from a list of lists to a two-dimensional array. Data access is faster because it’s more direct without any method call, and the stored data can be a primitive type (boolean in this case intead of Boolean object).

Implementation

This is the previous implementation with an two-dimensional array instead of a list of lists:

/** Chessboard represented by a 2 dimensional array. */
private final boolean[][] chessboard;
/** Current number of queens on the chessboard. */
private int placedQueens;

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

    // Put a queen on the current position
    chessboard[x][y] = true;
    placedQueens++;

    // All queens on the chessboard then a solution may be present
    if (placedQueens >= 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
    placedQueens--;
    chessboard[x][y] = 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 BruteForceNQueensSolverArray.

Benchmarks

These benchmarks are done on a Core i5 2500K:

chessboard size	execution time	number of runs
4	84.20 µs	5000
5	2.89 ms	5000
6	94.52 ms	500
7	4.12 s	50
8	3.50 m	5
9	too long…

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

Algorithms comparisons

Comparison of theses 2 algorithms:

The number of called methods is much lower when using an array because square reads and writes don’t need method calls anymore.

Next optimisations?

Next optimisations are tested in the part 3, click on the link below.

8 queens puzzle series next article