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

}

#### References

[1] 8 queens puzzle

http://en.wikipedia.org/wiki/Eight_queens_puzzle

[2] 8 queens on github

https://github.com/ggeorgovassilis/8queens