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.