# 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 . 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;

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

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;
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)
```// 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

 8 queens puzzle
http://en.wikipedia.org/wiki/Eight_queens_puzzle

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.