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