# Eight queens problem

Published:

###### AlgorithmsGo

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.

##### Prime numbers titleee

With this post I want to begin a series of posts about general algorithms. It is not an accident I started with the prime numbers. This is basic problem to solve when you are starting with programming. And one more reason – I was curious how RSA algorithm works and the important part of the algorithm is to generate two random big prime numbers.

Read more
##### Google Code Jam 2017: Tidy Numbers titleee

Tatiana likes to keep things tidy. Her toys are sorted from smallest to largest, her pencils are sorted from shortest to longest and her computers from oldest to newest. One day, when practicing her counting skills, she noticed that some integers, when written in base 10 with no leading zeroes, have...

Read more