Mitch's Technical Blog

Eight Queens

July 21, 2018
algorithms, golang, notes (revised August 4, 2018)
permalink

Practicing algorithms and programming strategies is a great way to stimulate and exercise your programming mind.

While flipping through Computer Science Distilled by Wladston Ferreira Filho, a surprisingly good self-published introductory book, I was reminded of the so-called eight queens problem in Chapter 3: Strategy. The idea is to place eight queens on an eight by eight chessboard, in such a way that no queen is under attack by any other. The author writes about backtracking as a strategy for this particular problem. I won't try to summarize or explain it here. If you'd like to learn more, I'll leave it up to you to do a bit of research.

The concept of backtracking clicked for me right away (which happens less often than not for me when studying computer-science). So I worked straight from the idea, without peeking at the author's solution on his website or otherwise studying example solutions.

This was a couple of months ago, and I still have pleasant memories of puzzling over this coding exercise for hours. I ended up using a bit of recursion in a way that didn't feel forced, and it was just plain fun to have code take shape around a powerful idea.

My intuitive "analysis" says that using backtracking brings the time complexity down from factorial to exponential or so.

I used Golang because I like its simplicity, and it was as good an excuse as any to get more practice with the language.

Code and sample output follow below.

package main

import (
    "fmt"
)

const BLANKSQUARE = "."
const QUEEN = "Q"

func main() {
    // Example use of radiateQueen
    board := blankBoard(8, 8)
    var row, col int
    if radiateQueen(0, 0, false, board) == true {
        fmt.Println("Queen placed without attacking any other Queen.")
        board[row][col] = QUEEN
        showBoard(board)
    } else {
        fmt.Println("radiate failed.")
    }
    // solve examples
    solve(8, 8, 0)
    solve(8, 8, 1)
    solve(8, 8, 2)
    solve(8, 8, 3)
    solve(3, 3, 0)
    solve(4, 4, 0)
    solve(5, 5, 0)
    solve(6, 6, 0)
    solve(10, 10, 4)
}

func blankBoard(rows int, cols int) [][]string {
    var board [][]string
    for r := 0; r < rows; r++ {
        // A fresh slice is essential to making each row independent
        colArr := []string{}
        for c := 0; c < cols; c++ {
            colArr = append(colArr, BLANKSQUARE)
        }
        board = append(board, colArr)
    }
    return board
}

func showBoard(board [][]string) {
    for row, rowArr := range board {
        fmt.Printf("%d", row)
        for _, val := range rowArr {
            fmt.Printf("%s", val)
        }
        fmt.Printf("\n")
    }
    fmt.Println()
}

func solve(rows int, cols int, firstQRowIndex int) {
    board := blankBoard(rows, cols)

    // Initialize a rowPointer slice to track successful Q placements
    // e.g. rowPointer[0] contains Q row index for column 0
    // This is used in backtrack bookkeeping, to enable easy
    // resumption forward from prior successful point
    rowPointer := []int{}

    for i := 0; i < rows; i++ {
        rowPointer = append(rowPointer, -1)
    }

    // For columns 1+, we'll try row 0 for the first Q placement
    // but the first row is user-configurable.
    startRow := firstQRowIndex

    // The algorithm will report back on how many tries
    // were required before a solution was found.
    numTries := 0

    // For each column...
    for col := 0; col < cols; {
        var row int
        colSuccess := false
        // Try each row. startRow can be non-0 for first column only.
        for row = startRow; row < rows; row++ {
            numTries++
            result := radiateQueen(row, col, true, board)
            if result == true {
                board[row][col] = QUEEN
                // Mark the row for backtracking reference.
                rowPointer[col] = row
                colSuccess, startRow = true, 0
                col += 1
                break
            }
        }

        if colSuccess == false {
            // Column not solveable as-is, so backtrack.
            startRow, col = backTrack(board, rowPointer, rows, row, col)
        }

        // If backtracking pushed beyond first column,
        // then there is no solution.
        if startRow == -1 {
            fmt.Printf("No solution found for (%d, %d).\n", rows, cols)
            fmt.Println()
            break
        }
    }

    // If a solution was found, print it.
    if startRow != -1 {
        fmt.Printf("Solved in %d tries:\n", numTries)
        showBoard(board)
    }
}

func radiateQueen(queenRow int, queenCol int, blankMarkers bool, board [][]string) bool {
    ROW := 0
    COL := 1
    var rowMove int
    var colMove int

    boardMoves := map[string][]int{"N": {-1, 0}, "S": {1, 0}, "E": {0, 1}, "W": {0, -1}, "NE": {-1, 1}, "NW": {-1, -1}, "SE": {1, 1}, "SW": {1, -1}}
    directionSymbols := map[string]string{"N": "|", "S": "|", "E": "-", "W": "-", "NE": "/", "NW": "\\", "SE": "\\", "SW": "/"}

    numRows := len(board)
    r := board[0]
    numCols := len(r)

    for key := range boardMoves {
        var marker string
        rowMove = boardMoves[key][ROW]
        colMove = boardMoves[key][COL]
        if blankMarkers == false {
            marker = directionSymbols[key]
        } else {
            marker = BLANKSQUARE
        }

        // move away from Queen candidate, one square at a time
        rowIdx := queenRow
        colIdx := queenCol
        for rowIdx >= 0 && rowIdx < numRows && colIdx >= 0 && colIdx < numCols {
            if board[rowIdx][colIdx] == QUEEN {
                // attacks existing Queen, so halt search
                return false
            }

            if rowIdx != queenRow || colIdx != queenCol {
                board[rowIdx][colIdx] = marker
            }

            rowIdx = rowIdx + rowMove
            colIdx = colIdx + colMove
        }
    }
    return true
}

func backTrack(board [][]string, rowPointer []int, rows int, row int, col int) (int, int) {
    // Base case: trying to backtrack below column 0
    if col == 0 {
        return -1, -1
    }
    rowPointer[col] = -1

    // Back up one column and remove its Queen
    col--
    removeQueen(board, col)

    // Edge case: Queen is already on bottom row of prior column,
    // which requires a recursive call to backtrack
    if rowPointer[col] == rows-1 {
        return backTrack(board, rowPointer, rows, row, col)
    }

    // Advance the Queen one row down in the backtracked column
    row = rowPointer[col] + 1
    return row, col
}

func removeQueen(board [][]string, col int) {
    // A simple dumb function to "zero out" a column
    for key, _ := range board {
        board[key][col] = BLANKSQUARE
    }
}

Example output:

mitchell@ThinkCentre:~/projects/8queens$ go run 8q.go

Queen placed without attacking any other Queen.
0Q-------
1|\......
2|.\.....
3|..\....
4|...\...
5|....\..
6|.....\.
7|......\

Solved in 876 tries:
0Q.......
1......Q.
2....Q...
3.......Q
4.Q......
5...Q....
6.....Q..
7..Q.....

Solved in 195 tries:
0.....Q..
1Q.......
2....Q...
3.Q......
4.......Q
5..Q.....
6......Q.
7...Q....

Solved in 362 tries:
0.Q......
1.....Q..
2Q.......
3......Q.
4...Q....
5.......Q
6..Q.....
7....Q...

Solved in 185 tries:
0.Q......
1....Q...
2......Q.
3Q.......
4..Q.....
5.......Q
6.....Q..
7...Q....

No solution found for (3, 3).

Solved in 26 tries:
0..Q.
1Q...
2...Q
3.Q..

Solved in 15 tries:
0Q....
1...Q.
2.Q...
3....Q
4..Q..

Solved in 171 tries:
0...Q..
1Q.....
2....Q.
3.Q....
4.....Q
5..Q...

Solved in 601 tries:
0.Q........
1.....Q....
2.......Q..
3..Q.......
4Q.........
5........Q.
6....Q.....
7.........Q
8...Q......
9......Q...

Contact: hello at escapefromsql.net