Expressive Concurrency: A Go Sudoku Solver (Pt. 1)

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.

18954 views and 5 responses

  • Jul 17 2010, 2:28 PM
    syneii responded:
    I don't know what language you're using but the syntax is so awkward it drew me away from what you were trying to even talk about.

    Choose a more common syntax, maybe something similar to C++.

    Essentially your dialect is so strong in your syntax, and awkward, it makes no freaking sense to anyone with a strict knowledge of more common dialects/syntax.

  • Jul 17 2010, 5:20 PM
    Andrew Gerrand responded:
    Hi syneii, the language is Go - http://golang.org/ - and I am part of the team that is developing it. The point of this exercise is to explore writing software using Go's concurrent programming features. The syntax is a little unusual at first, but after a couple of days one gets used to it. You should check it out!
  • Jul 17 2010, 8:31 PM
    norepinephrine responded:
    @syneii: You think Go has awkward syntax? Whatever you do don't click these links: http://en.wikipedia.org/wiki/Clojure http://en.wikipedia.org/wiki/Erlang_(programming_language)
  • Aug 28 2010, 3:30 AM
    Lukasz responded:
    Love the language, can't wait for it to become mainstream.
    PS, the inner loop seems a little confusing, I would put it into the "c==8" condition:

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

  • Aug 28 2010, 7:20 PM
    Andrew Gerrand responded:
    There are a few different ways of writing that inner loop, and your suggestion is arguably better. Reflecting on it now, I'd probably go one step further and move the finding and sending of the solution outside of the "range elim" for loop, too.