# 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 mainimport (    "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 intdone = 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 & -possposs -= 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.

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.