# Eight queens problem

Published:

###### Algorithms Go

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.