N-Queens - Brute force - bit by bit

Question

A discussion in The 2nd Monitor made me realize I had never 'solved' the N-Queens problem. Additionally, as I read up on it, I realized that the 64-squares in a chess board would work well if represented as bits in a 64-bit long.... That was a nice thought, but it became complicated, and really, 8-size chess boards are quick to process.

Instead, I considered representing each queen as a bit in an integer, and each integer represents a row on the board. Using a 'long' I could have a 64/64 board, conceptually.

With that representation, I could solve any size board up to 32, and that makes it a decent N-Queen solver. Switching to longs would make it a 64-size solver.

Still, I also realized soon that anything beyond about 15 size boards is pretty slow to brute.

Regardless, Here is an N-Queen solver, with some utility methods to make it friendly. The algorithm I use relies on only adding a queen to the board (one queen in each row) when that queen is added to an un-protected square.

It calculates what squares are protected in each row by using bit-wise manipulation.

Hoping for reviews that focus on:

• performance suggestions
• Java 8 utilization

I am aware that heuristic approaches to the N-Queen problem are faster, but answers that rely on heuristics to solve it are not as interesting to me as solutions which improve the brute-force approach.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.IntStream;

public class NQueens {

    public static class Position {
        private final int row;
        private final int column;

        private Position(int row, int column) {
            this.row = row;
            this.column = column;
        }

        public int getRow() {
            return row;
        }

        public int getColumn() {
            return column;
        }

        @Override
        public String toString() {
            return String.format("(%d,%d)", row, column);
        }
    }

    public static class Solution {
        public final Position[] solution;

        private Solution(Position[] solution) {
            super();
            this.solution = solution;
        }

        public Position[] getPositions() {
            return Arrays.copyOf(solution, solution.length);
        }

        private char[] padChars(char[] chars) {
            char[] ret = new char[chars.length * 2 - 1];
            Arrays.fill(ret, ' ');
            for (int i = 0; i < chars.length; i++) {
                ret[i * 2] = chars[i];
            }
            return ret;
        }

        @Override
        public String toString() {
            int size = solution.length;
            char[][] board = new char[size][size];
            for (int i = 0; i < size; i++) {
                board[i] = new char[size];
                Arrays.fill(board[i], '\u02d1');
            }
            for (Position p : solution) {
                board[p.getRow()][p.getColumn()] = 'Q';
            }
            char[] border = new char[size];
            Arrays.fill(border, '-');

            StringBuilder sb = new StringBuilder((size + 2) * (size + 3));
            sb.append(" ").append(padChars(border)).append(" \n");
            for (int i = 0; i < size; i++) {
                sb.append("|").append(padChars(board[i])).append("|\n");
            }
            sb.append(" ").append(padChars(border)).append(" \n");
            return sb.toString();
        }

    }

    public static Solution[] solve(final int size) {

        final List<Solution> solutions = new ArrayList<>();

        // each candidate is a 1-bit in a different column.
        final int[] candidates = new int[size];
        for (int i = 0; i < size; i++) {
            candidates[i] = 1 << i;
        }

        // recursive call
        search(0, new int[size], candidates, solutions);

        return solutions.toArray(new Solution[solutions.size()]);
    }

    private static void search(final int depth, final int[] queens,
            final int[] candidates, final List<Solution> solutions) {
        if (depth == queens.length) {
            // solved it.
            Position[] locations = new Position[queens.length];
            for (int i = 0; i < queens.length; i++) {
                locations[i] = new Position(i, queens[i]);
            }
            solutions.add(new Solution(locations));
            return;
        }

        int mask = 0;
        for (int i = 0; i < depth; i++) {
            int queen = candidates[queens[i]];
            mask |= queen; // previous queens cover this column....
            mask |= queen >>> (depth - i); // previous queens cover this
                                           // diagonal to the right.
            mask |= queen << (depth - i); // previous queens cover this diagonal
                                          // to the left.
        }

        for (int i = 0; i < candidates.length; i++) {
            if ((candidates[i] & mask) == 0) {
                // then we are not in the same column, row, or diagonal as
                // another queen.
                queens[depth] = i;
                search(depth + 1, queens, candidates, solutions);
            }
        }

    }

    private static final void timeFunction(String name, Runnable task) {
        long start = System.nanoTime();

        task.run();

        long time = System.nanoTime() - start;
        System.out.printf("Ran task: %s in %.3fms%n", name, time / 1000000.0);

    }

    public static void main(String[] args) {
        timeFunction("WarmUp 100x5", () -> {
            for (int i = 0; i < 100; i++) {
                solve(5);
            }
        });
        timeFunction("WarmUp 100x8", () -> {
            for (int i = 0; i < 100; i++) {
                solve(8);
            }
        });

        IntStream.rangeClosed(1, 14).forEach(
                size -> timeFunction("Size " + size,
                        () -> report(size, solve(size))));

        Solution[] solutions = solve(8);
        for (int i = 0; i < solutions.length; i++) {
            System.out.printf("Soltion %d of %d for size %d:%n%s%n", i + 1,
                    solutions.length, 8, solutions[i]);
        }
    }

    private static void report(int size, Solution[] solve) {
        System.out.printf("Solved %d size with %d solutions%n", size,
                solve.length);
    }

}

The program generates output like:

Ran task: WarmUp 100x5 in 4.989ms
Ran task: WarmUp 100x8 in 12.117ms
Solved 1 size with 1 solutions
Ran task: Size 1 in 0.376ms
Solved 2 size with 0 solutions
Ran task: Size 2 in 0.246ms
Solved 3 size with 0 solutions
Ran task: Size 3 in 0.244ms
Solved 4 size with 2 solutions
Ran task: Size 4 in 0.241ms
Solved 5 size with 10 solutions
Ran task: Size 5 in 0.171ms
Solved 6 size with 4 solutions
Ran task: Size 6 in 0.135ms
Solved 7 size with 40 solutions
Ran task: Size 7 in 0.156ms
Solved 8 size with 92 solutions
Ran task: Size 8 in 0.230ms
Solved 9 size with 352 solutions
Ran task: Size 9 in 0.493ms
Solved 10 size with 724 solutions
Ran task: Size 10 in 1.712ms
Solved 11 size with 2680 solutions
Ran task: Size 11 in 9.026ms
Solved 12 size with 14200 solutions
Ran task: Size 12 in 53.223ms
Solved 13 size with 73712 solutions
Ran task: Size 13 in 308.354ms
Solved 14 size with 365596 solutions
Ran task: Size 14 in 2739.035ms

and

Soltion 1 of 92 for size 8:
 - - - - - - - - 
|Q ˑ ˑ ˑ ˑ ˑ ˑ ˑ|
|ˑ ˑ ˑ ˑ Q ˑ ˑ ˑ|
|ˑ ˑ ˑ ˑ ˑ ˑ ˑ Q|
|ˑ ˑ ˑ ˑ ˑ Q ˑ ˑ|
|ˑ ˑ Q ˑ ˑ ˑ ˑ ˑ|
|ˑ ˑ ˑ ˑ ˑ ˑ Q ˑ|
|ˑ Q ˑ ˑ ˑ ˑ ˑ ˑ|
|ˑ ˑ ˑ Q ˑ ˑ ˑ ˑ|
 - - - - - - - - 

Soltion 2 of 92 for size 8:
 - - - - - - - - 
|Q ˑ ˑ ˑ ˑ ˑ ˑ ˑ|
|ˑ ˑ ˑ ˑ ˑ Q ˑ ˑ|
|ˑ ˑ ˑ ˑ ˑ ˑ ˑ Q|
|ˑ ˑ Q ˑ ˑ ˑ ˑ ˑ|
|ˑ ˑ ˑ ˑ ˑ ˑ Q ˑ|
|ˑ ˑ ˑ Q ˑ ˑ ˑ ˑ|
|ˑ Q ˑ ˑ ˑ ˑ ˑ ˑ|
|ˑ ˑ ˑ ˑ Q ˑ ˑ ˑ|
 - - - - - - - - 

Answer 1

The thing that looked the slowest was

int mask = 0;
for (int i = 0; i < depth; i++) {
    int queen = candidates[queens[i]];
    mask |= queen; // previous queens cover this column....
    mask |= queen >>> (depth - i); // previous queens cover this
                                   // diagonal to the right.
    mask |= queen << (depth - i); // previous queens cover this diagonal
                                  // to the left.
}

The whole loop shouldn't be needed; normally one would build the mask as one got deeper into the call stack. This encouraged a slightly different method:

public static Solution[] solve(final int size) {

    final List<Solution> solutions = new ArrayList<>();

    search(
        0,                 // depth
        0, 0, 0,           // masks
        new int[size],     // queens
        solutions,         // solutions
        (1 << size) - 1    // full mask
    );

    return solutions.toArray(new Solution[solutions.size()]);
}

private static int getShift(int i) {
    int shift = 0;

    while (i != 1) {
        i >>>= 1;
        shift += 1;
    }

    return shift;
}

private static void search(
    final int depth,
    final int colTaken,
    final int upDiagTaken,
    final int downDiagTaken,
    final int[] queens,
    final List<Solution> solutions,
    final int fullMask,
) {

    if (colTaken == fullMask) {
        // solved it.
        Position[] locations = new Position[queens.length];
        for (int i = 0; i < queens.length; i++) {
            locations[i] = new Position(i, getShift(queens[i]));
        }
        solutions.add(new Solution(locations));
        return;
    }

    final int mask = colTaken | upDiagTaken | downDiagTaken;

    for (int bit = 1; bit < fullMask; bit <<= 1) {
        if ((mask & bit) == 0) {
            queens[depth] = bit;

            search(
                depth + 1,
                (bit | colTaken),
                (bit | upDiagTaken) >> 1,
                (bit | downDiagTaken) << 1,
                queens,
                solutions,
                fullMask,
            );
        }
    }
}

which gives a noticable performance increase (1.8s → 1.2s for me). I changed the loop a little to remove the need for a candidates array by generating the queens in the loop. To prevent speed reductions I ended up delaying unshifting until a solution is found. I also make the exit condition check a mask because it seemed faster.

Next I would simplify the exit. I would aim for something like:

if (colTaken == fullMask) {
    solutions.add(new Solution(queens));
    return;
}

which is simple enough by making Solution a bit brighter. I would also remove the Position class for simplicity; Maarten Winkels points out that you don't need it. I'm not much of a Java person but calling super when you aren't inheriting seems odd to me, as does exposing getPositions when you haven't shown a need (plus, solution is public).

On later consideration, I don't get why you have Solution at all; it wraps an array to allow access to two printing functions but you could just make those functions static. Not everything needs to be a class.

I don't really get why you did

Arrays.fill(board[i], '\u02d1');

instead of

Arrays.fill(board[i], '·');

Also, you should use this: ♛.

I get that string manipulation in Java is a bit verbose, but yours seems a bit much. I tried my hand and got

public static String drawAsQueens(int[] solution) {
    StringBuilder grid = new StringBuilder();

    String header = " " + String.join(" ", Collections.nCopies(solution.length, "-")) + " \n";

    grid.append(header);
    for (int col : solution) {
        String[] row = new String[solution.length];
        Arrays.fill(row, "·");
        row[col] = "♛";

        grid.append("|" + String.join(" ", row) + "|\n");
    }
    grid.append(header);

    return grid.toString();
}

Going back to search, you can iterate over set bits with this method. Inverting the bits allowed this and doubled the speed I got from the code.

int free = colFree & upDiagFree & downDiagFree;

while (free != 0) {
    // Split low bit from mask using hackery
    int bit = free;
    free &= free - 1;
    bit ^= free;

    queens[depth] = bit;

    search(
        depth + 1,
        (bit ^ colFree),
        ((bit ^ upDiagFree) >> 1) | highBit,
        ((bit ^ downDiagFree) << 1) | 1,
        queens,
        solutions,
        highBit
    );
}

Now almost half the time is just in

queens[depth] = bit;

since the rest of the code just fiddles with integers. Removing setting of the queen (and, by that measure, depth) would have a great benefit. As it stands, the information is in the stack but it's not trivial to retrieve so I don't know of a good solution. The real need is to encode queens in something that won't have bounds checks or require knowing the depth. Sadly, we only have the shifted bits and those are too large to pack into an integer. Oh well; a 3x improvement is good enough for now.

Personally I would not do IntStream.rangeClosed(1, 14).forEach. YMMV, but a normal

for (int i = 1; i <= 14; i++)

is just much clearer. There is the need to make size final but I would make it explicit, not just do something different for a reason opaque to the reader. Hence, I find the best option to be:

for (int i = 1; i <= 14; i++) {
    final int size = i;
    timeFunction("Size " + size, () -> report(size, solve(size)));
}

You don't really need to use %n AFAICT. I'd stick with \n.

Here's the code:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.IntStream;
import java.util.Collections;

public class NQueens2 {
    public static String drawAsQueens(int[] solution) {
        StringBuilder grid = new StringBuilder();

        String header = " " + String.join(" ", Collections.nCopies(solution.length, "-")) + " \n";

        grid.append(header);
        for (int col : solution) {
            String[] row = new String[solution.length];
            Arrays.fill(row, "·");
            row[col] = "♛";

            grid.append("|" + String.join(" ", row) + "|\n");
        }
        grid.append(header);

        return grid.toString();
    }

    public static int[][] solve(final int size) {

        final List<int[]> solutions = new ArrayList<>();
        final int fullMask = (1 << size) - 1;

        search(
            0,                 // depth
            fullMask,          // colFree
            fullMask,          // upDiagFree
            fullMask,          // downDiagFree
            new int[size],     // queens
            solutions,         // solutions
            1 << (size - 1)    // high bit
        );

        return solutions.toArray(new int[solutions.size()][]);
    }

    private static int getShift(int i) {
        int shift = 0;

        while (i != 1) {
            i >>>= 1;
            shift += 1;
        }

        return shift;
    }

    private static void search(
        final int depth,
        final int colFree,
        final int upDiagFree,
        final int downDiagFree,
        final int[] queens,
        final List<int[]> solutions,
        final int highBit
    ) {

        if (colFree == 0) {
            solutions.add(Arrays.stream(queens).map(NQueens2::getShift).toArray());
            return;
        }

        int free = colFree & upDiagFree & downDiagFree;

        while (free != 0) {
            // Split low bit from mask using hackery
            int bit = free;
            free &= free - 1;
            bit ^= free;

            queens[depth] = bit;

            search(
                depth + 1,
                (bit ^ colFree),
                ((bit ^ upDiagFree) >> 1) | highBit,
                ((bit ^ downDiagFree) << 1) | 1,
                queens,
                solutions,
                highBit
            );
        }
    }

    private static final void timeFunction(String name, Runnable task) {
        long start = System.nanoTime();

        task.run();

        long time = System.nanoTime() - start;
        System.out.printf("Ran task: %s in %.3fms\n", name, time / 1000000.0);
    }

    public static void main(String[] args) {
        timeFunction("WarmUp 100x5", () -> {
            for (int i = 0; i < 100; i++) {
                solve(5);
            }
        });
        timeFunction("WarmUp 100x8", () -> {
            for (int i = 0; i < 100; i++) {
                solve(8);
            }
        });

        for (int i = 1; i <= 14; i++) {
            final int size = i;
            timeFunction("Size " + size, () -> report(size, solve(size)));
        }

        int[][] solutions = solve(8);
        for (int i = 0; i < solutions.length; i++) {
            System.out.printf("Solution %d of %d for size %d:\n%s\n",
                    i + 1, solutions.length, 8, drawAsQueens(solutions[i]));
        }
    }

    private static void report(int size, int[][] solve) {
        System.out.printf("Solved %d size with %d solutions\n",
                size, solve.length);
    }

}

Answer 2

This one surprised me:

public static class Solution {
    public final Position[] solution

That's an exposed public field. You are breaking encapsulation here, and it's not as "final" as you'd think it is. Even though outside code cannot change the whole array, outside code could change the contents inside the array.

Answer 3

The Position class is (although probably good design) quite redundant: you construct an array of Position objects, of which the row (first argument of the constructor) is always the same as the index in the array. In effect the int array queens at that point already contains all information for the solution. The conversion to Positions doesn't add any information, is redundant and the performance would increase (marginally) by removing it.

EDIT: The candidates array is static for each problem size: no need to pass it to the search method, if you would create a SolutionFinder class that is specialized for a particular problem size. Now the candidates can be final state in an instance of this class, the solve and search methods become simpler. Not sure if this would impact performance.