nf.id.au

Go’s concurrency primitives (goroutines and channels) afford us a novel approach to solving Sudoku puzzles.

Suppose each square can think, and is concerned with finding out what number belongs in the square. If we tell the square the numbers it cannot contain (ie, the numbers already taken by other squares in its row, column, or 3x3 group) then it is a simple process of elimination for the square to know when it has no other options, and tell us which number it must contain.

In Go terms, each square’s thought process happens in a separate goroutine. The messages from outside that say “you cannot contain x” and the square’s reponse “I have deduced that I must contain y” are channel receives and sends. The function definition for such a process might look like this:

func square(x, y int, elim <-chan int, done chan<- solution)

The arguments x and y are the square’s position on the board. elim is a read-only channel of ints – receives from this channel communicate which numbers cannot be in that square. done is a write-only channel of type ‘solution’ – this is the channel to which the square sends its deduced value. The type definition for solution could be:

type solution struct { x, y, v int }

Where x and y are the square’s board position, and v is the deduced contents of the square.

On to the implementation. First, we’ll read from elim and make a note of which numbers are eliminated:

func square(x, y int, elim <-chan int, done chan<- solution) {
    var eliminated [9]bool
    for n := range elim {
        eliminated[n-1] = true
    }
}

Now, let’s write a loop to see how many of the 9 numbers have been elimiated:

func square(x, y int, elim <-chan int, done chan<- solution) {
    var eliminated [9]bool
    for n := range elim {
        eliminated[n-1] = true
        var c int
        for _, v := range eliminated {
            if v {
                c++
            }
        }
    }
}

While iterating over eliminated, we should make a note of potential solutions. If c is equal to 8, then we’ve eliminated all but one number and thus the solution has been found.

func square(x, y int, elim <-chan int, done chan<- solution) {
    var eliminated [9]bool
    for n := range elim {
        eliminated[n-1] = true
        var c, s int
        for i, v := range eliminated {
            if v {
                c++
            } else {
                s = i+1
            }
        }
        if c == 8 {
            done <- solution{x, y, s}
            close(elim)
        }
    }
}

After sending the solution to done, the goroutine closes the elim channel. This will cause the main loop to terminate, the function to return, and prevent other goroutines from blocking while sending to the channel.

I have written Sudoku solvers in other languages, and simulating the state of the entire 9x9 matrix has typically required a lot of carefully crafted logic. This “one goroutine per square” approach allows us to focus solely on an isolated, simple logical problem and use channels as an interface to the rest of the code. This demonstrates the expressive power of these concurrency constructs.

The infrastructure that we’ve not thought about: setting up elim channels and launching goroutines for each square, reading solutions from the done channel and sending elimination messages to the affected squares, and, finally, determining when a solution has been found. This will be the topic of a future post.

Update: part 2 is now available.