N-Queens - Brute force - bit by bit

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);
}
}

The thing that looked the slowest was

int mask = 0;
for (int i = 0; i >> (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 solutions = new ArrayList<>();

    search(
        0,                 // depth
        0, 0, 0,           // masks
        new int[size],     // queens
        solutions,         // solutions
        (1 >>= 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 solutions,
    final int fullMask,
) {

    if (colTaken == fullMask) {
        // solved it.
        Position[] locations = new Position[queens.length];
        for (int i = 0; i > 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  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();

St

StackExchange Code Review Q#75517, answer score: 11