3 minutes
Solution to Eight Queens problem in Golang
We shall use the recursive backtracking technique for getting all the solutions to the Eight Queens Problem.
We shall use two 8x8 arrays, one to store the position of the queens and the other to store the counts of the queens that are attacking a particular position.
var hasQueen [8][8]bool
var inAttack [8][8]int
Next is the helper function that we call to place a queen at a position (i, j)
.
func placeQueen(i, j int) {
hasQueen[i][j] = true
// update attack counts
// row
for c := 0; c < 8; c++ {
inAttack[i][c]++
}
// col
for r := 0; r < 8; r++ {
inAttack[r][j]++
}
inAttack[i][j] -= 2 // the (i,j) cell has been counted twice in the above iterations
// diagonals
for r := 0; r < 8; r++ {
for c := 0; c < 8; c++ {
if r == i && c == j {
inAttack[r][c]++
continue
}
if r-i == c-j || r-i == -(c-j) {
inAttack[r][c]++
}
}
}
}
Next, we write the function to remove a queen form a position (i, j)
. This shall be used when we are backtracking due to some reason and need to remove a queen.
func removeQueen(i, j int) {
hasQueen[i][j] = false
// update attack counts
// row
for c := 0; c < 8; c++ {
inAttack[i][c]--
}
// col
for r := 0; r < 8; r++ {
inAttack[r][j]--
}
inAttack[i][j] += 2
// diagonals
for r := 0; r < 8; r++ {
for c := 0; c < 8; c++ {
if r == i && c == j {
inAttack[r][c]--
continue
}
if r-i == c-j || r-i == -(c-j) {
inAttack[r][c]--
}
}
}
}
This function is just the inverse of the place_queen()
function.
Next we use a global variable to hold he counts of the solutions discovered.
var solNo int
Next is the actual function that does the recursive backtracking to solve the problem.
func solve(r int) {
if r == 7 {
// can we place the queen somewhere
for c, cnt := range inAttack[7] {
if cnt == 0 {
placeQueen(r, c)
solNo++
fmt.Println("Solution No.", solNo)
pp2DBoolArr(hasQueen)
removeQueen(r, c)
}
}
} else {
for c, cnt := range inAttack[r] {
if cnt == 0 {
placeQueen(r, c)
solve(r + 1) // solve the next row (recursive)
removeQueen(r, c) // remove this queen (backtrack)
}
}
}
}
I also use a simple utility function to print the positions of the queens.
// `pp2DBoolArr` pretty prints a 2D int array
func pp2DBoolArr(data [8][8]bool) {
for i := 0; i < 8; i++ {
row := make([]string, 8)
for j := 0; j < 8; j++ {
if data[i][j] {
row[j] = "Q"
} else {
row[j] = "+"
}
}
fmt.Println(strings.Join(row, " "))
}
}
And the main
function that is the entry point of the code.
func main() {
solve(0)
}
The complete code is available here. The generated output is available here.