Solving the 8 Queens puzzle with bit operations

The 8 queens puzzle is a classic (and quite fun to solve) toy problem: place eight queens on a chess board in such a way that all queens could fully move without being obstructed by any other queen.

While without practical applications, it illustrates a number of aspects of designing algorithms and implementing programmes:

– simplicity of an algorithm
– radically different approaches towards a solution by choosing different representations
– implications of programming choices on execution time

For a class during my undergraduate studies we had to implement a solver for the generalized N queens puzzle in Prolog which resulted in an equally elegant and slow implementation: around 30 seconds (on a pentium) for all 92 solutions for N=8, including symmetrical solutions.

On a long transfer in Istanbul I decided that I wanted to know once for all: how fast can it be done? I’ll never know, because I wrote the solver in Java, but it turns out that a brute-force solver can do it in way under a second.

The solution

Leaving heuristic solutions aside, I am aware of only two solutions which are both brute force algorithms but differ in the way they represent the problem.

The first solution is to represent the chessboard as an 8×8 array, generate all combinations of queens and then check if any queen “sees” any other, thus simulating pretty much a sunday afternoon in front of a chessboard (with all pawns having been promoted to queens).

The second solution abandons the idea of a chessboard altogether and instead works with four lists: a list of free rows, free columns, free North-West diagonals and free North-East diagonals. Whenever a queen is placed on the imaginary chessboard, it occupies a row, a column and two diagonals which are removed from the respective lists. This solution has the benefit that it avoids a lot of unnecessary steps and solves the problem much faster since colliding positions are removed from the lists.

Bit operations

8×8 = 64, which is a long integer in java. A field on the chessboard is either occupied or not, thus the representation of an entire chessboard is possible with a long. A few simple bit mask operations can set or unset not only a single field but entire columns, rows and diagonals and even check single-handedly if a queen would run into another.

The central idea is to create a bit mask for every position on the board with all the valid moves for a queen. A bitwise AND of the board with the mask leaves only the path of the queen for that position and then checking for other queens on that path is again a simple bitmap operation.

The solution presented here makes use of a minor twist: normally one would represent empty fields with 0 and occupied fields with 1, but it turns out that we can save a few bitmap operations with the opposite representation (i.e. it is easier to check if the path for a queen is 0 than to check if any single bit is set) where 0 means occupied and 1 means free.

The resulting implementation computes on a 64 bit core i5, after warm-up, all solutions in 240 ms.

Out of fun (and a delayed flight) I implemented the second algorithm also with the use of bitmaps – it finishes close second with 260 ms, but the implementation yields fewer opportunities for bit fiddling and isn’t quite as interesting.

The code

You can easily check out this project on github [2]. I’m omitting the obvious AbstractBoard and Board classes, they are simple data holders (8×8 boolean array) and contain no logic.

package eightqueens.bitpack;

import java.util.ArrayList;
import java.util.List;

import eightqueens.AbstractBoard;

public class BitPackSolver{

private final long[] visibilityMask = new long[64];

boolean isValidPosition(int row, int column) {
return row >= 0 && column >= 0 && row < 8 && column < 8;
}

public BitPackSolver() {
for (int row = 0; row < 8; row++)
for (int column = 0; column < 8; column++) {
long board = 0;
for (int radius = 0; radius < 8; radius++) {
if (isValidPosition((row + radius), (column + radius)))
board = set(board, (row + radius), (column + radius));
if (isValidPosition((row + radius), (column - radius)))
board = set(board, (row + radius), (column - radius));
if (isValidPosition((row - radius), (column + radius)))
board = set(board, (row - radius), (column + radius));
if (isValidPosition((row - radius), (column - radius)))
board = set(board, (row - radius), (column - radius));
if (isValidPosition(radius, column))
board = set(board, radius, column);
if (isValidPosition(row, radius))
board = set(board, row, radius);
}
visibilityMask[index(row, column)] = board;
}
}

public static boolean getBit(long board, int row, int column) {
return (board & position(index(row, column))) != 0;
}

boolean getBit(long board, int index) {
return (board & (1l << index)) != 0;
}

AbstractBoard longToBoard(long board) {
return new Board(board);
}

public static int index(int row, int column) {
return (row * 8 + column);
}

public static long position(int index) {
return 1l << (long) index;
}

public static long set(long board, int row, int column) {
return board | position(index(row, column));
}

public static long unset(long board, int row, int column) {
return set(board, row, column) ^ position(index(row, column));
}

boolean isSingleBitSet(long x) {
// the strict check is this:
// x!= 0 && (x & (x - 1)) == 0;
// but we already know x!=0 because we ever only check after we've
// determined that the field is occupied
return (x & (x - 1)) == 0;
}

public List solve() {
long board = 255;
int rows[] = new int[8];
int carry = 0;
List abstractBoards = new ArrayList(92);
// carry = 0 -> the one time where it will be 1 it means that _all_
// columns have overflown (all queens were already on the last row)
while (carry == 0) {

// 1. verify if board is a valid solution
// in an older version i'd iterate over all 64 indexes instead of
// row[column] which turned out to take twice as long

int i = 0;
for (; i<8; i++) {
int index = index(rows[i], i);
if (((board ^ position(index)) & visibilityMask[index]) != 0)
break;
}
if (i==8)
abstractBoards.add(longToBoard(board));

// 2. compute next combination
   carry = 1;
   for (int column = 0; column < 8; column++) {
    int c = rows[column] + carry;
    rows[column] = c % 8;
    carry = c >> 3; // division by 8. Marginally (3ms) faster than
        // the division itself.
    if (carry == 0)
     break;
   }

 // 3. place queens according to next combination
   board = 0;
   for (int column = 7; column >= 0; column--) {
    board |= position(index(rows[column], column));
   }
  }
  return abstractBoards;
 }

}