# Eight queens problem

If you know what is Bactracking, you sure know about Eight Queens problem – how to place eight queens on an 8×8 chessboard. I found nice solution using bitwise operations which counts all solutions for any given size.

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.

The common solution for this is to use backtracking. It is a good practice and you understand the algorithm realy fast. But it still can be improved a little bit…

## Bitwise solution in Go lang

I found this solution with very good explanation on internet. It uses only bitwise operations, therefore it is really fast. Originally, it was written in JavaScript, but I rewrote it in Go.

#### The code

``````package main

import (
"fmt"
"math"
)

func main() {
fmt.Println(countNQueenSolution(4))
}

func countNQueenSolution(n int) int {
var count int
count = 0

var done int
done = int(math.Pow(2, float64(n))) -1

var recursion func(ld int, col int, rd int)

recursion = func(ld int, col int, rd int) {
if col == done {
count++
return
}

poss := ^(ld | col | rd)

for poss & done > 0 {
bit := poss & -poss
poss -= bit
recursion((ld|bit)>>1, col|bit, (rd|bit)<<1)
}
}

recursion(0, 0, 0)

return count
}``````

#### Explanation

When you see it for the first time, it can be a little bit confusing, but later you find it perfect. I suppose you are familiar that computer stores data as sequence of bits ( 5 = 0101 ). Now look on the code and see the variables `ld`, `col` and `rd`.

• for N = 4, `col` having value of `0010` would mean that the 3rd column is already occupied by a queen
• for N = 8, `ld` having a value of `00011000` at row 5 would mean that the top-left-to-bottom-right diagonals that pass through columns 4 and 5 of that row are already occupied by queens
``````var done int
done = int(math.Pow(2, float64(n))) -1``````

The algorithm will not break the chess rules, that means it doesn't place queen on the same row / column / diagonal with any other queen. So when every place in row is taken - the `col` variable has each of its bits set to `1` - we found one of the solutions. The `done` variable is used for this. If N = 4, we set its value to `2<sup>4</sup> - 1` = `15` = `1111` in binary.

``````if col == done {
count++
return
}``````

Here is the condition to check if we found one of the solutions. If each column is occupied, then `col` = `1111` and it corresponds to `done` value ( for N = 4 ).

``poss := ^(ld | col | rd)``

In `ld`, `col` and `rd` are the queens positions for current row. When doing OR, we get all under attack positions in that row. Then negate (`^`) it to get free positions.

``````bit := poss & -poss
poss -= bit``````

Get the first available position and mark that position as taken in the current row.

``recursion((ld|bit)>>1, col|bit, (rd|bit)<<1)``

Move to next row. So you shift diagonals and mark new position in `col` variable.

## Conclusion

When you have some problem to solve, it is good to try and solve it your way ( if you have time of course ) and then look for another solution(s) so you can compare it and learn something.

#### References

Eight queens puzzle on Wikipedia with problem's history, solutions and related problems.

Original post, A bitwise solution to the N queens problem in JavaScript, which I found and rewrote.

PDF Backtracking Algorithms in MCPL using Bit Patterns and Recursion by Martin Richards, where you can find more informations.