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

This is the second part in a series of blog posts. If you haven’t done so already, you should probably read part one before continuing.

At the conclusion of part one, we had implemented the function ‘square’ which maintains the state of a single square on the Sudoku grid. It reads from a channel of elimination messages, taking note of which numbers it cannot contain, and when it has deduced a solution it sends that solution on a ‘done’ channel. The function signature is:

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

And the type definition of solution:

type solution struct { x, y, v int }

Now, let’s build some infrastructure around these. We’ll call our general data type Solver, and it will consist of 9x9 elimination channels, the done channel, and the set of known solutions:

type Solver struct {
    done     chan solution
    elim     [9][9]chan int
    solution [9][9]int
}

(A zero in the solution matrix will be considered “unknown”.)

We’ll then need a function that initialises these data structures, and runs our square functions in goroutines:

func NewSolver() (s *Solver) {
    s = &Solver{done:make(chan solution)}
    for y := 0; y < 9; y++ {
        for x := 0; x < 9; x++ {
            s.elim[y][x] = make(chan int)
            go square(x, y, s.elim[y][x], s.done)
        }
    }
    return
}

The way I envision this being used is that you call NewSolver to intialise the Solver, then call a method on Solver named Set to set the value of each of the known squares, and finally call the method Solve which returns the solution matrix.

Let’s tackle the Set method. To set the value of a square, we need to tell it all the values that it isn’t. For example, if we know that it contains a v, we should eliminate all numbers except for v:

func (s *Solver) Set(x, y, v int) {
    go func() {
        for i := 1; i <= 9; i++ {
            if i != v {
                s.elim[y][x] <- i
            }
        }
    }()
}

Note that this method launches a goroutine to perform these channel sends. This is to a prevent a call to Set from blocking, as these unbuffered channels require that both the sender and receiver are ready before a a send can proceed.

The Solve method will receive 81 solutions (9*9, one for each square) from the done channel, and return the solution matrix. As it receives each solution, it will invoke another function that sends elimination messages to the squares in the same row, column, and 3x3 group as the solved square.

func (s *Solver) Solve() [9][9]int {
    for n := 0; n < 9*9; n++ {
        u := <-s.done
        go s.eliminate(u)
        s.solution[u.y][u.x] = u.v
    }
    return s.solution
}

Note, again, that the eliminate method is called in a new goroutine. This is because eliminate will perform a number of channel sends which may block, and we don’t want to prevent our Solve method from reading further solutions from s.done lest we reach a deadlock.

The eliminate method is trivial, but a little fiddly:

func (s *Solver) eliminate(u solution) {
    // row
    for x := 0; x < 9; x++ {
        if x != u.x {
            s.elim[u.y][x] <- u.v
        }
    }
    // column
    for y := 0; y < 9; y++ {
        if y != u.y {
            s.elim[y][u.x] <- u.v
        }
    }
    // 3x3 group
    sX, sY := u.x/3*3, u.y/3*3 // group start coordinates
    for y := sY; y < sY+3; y++ {
        for x := sX; x < sX+3; x++ {
            if x != u.x && y != u.y {
                s.elim[y][x] <- u.v
            }
        }
    }
}

Now we have a functional Sudoku solver, albeit only for easier puzzles where no guessing (and thus backtracking) is required. In a future post I will delve into modifying this program to solve any valid Sudoku puzzle.

17677 views and 2 responses

  • Nov 13 2012, 7:23 AM
    Nick responded:
    Hi Andrew,

    I think that this is a very clever way of solving this. I have done similar things with other languages, but none have relied on concurrency in quite this way.

    Were you ever able to post a Sudoku solution that includes backtracking for more challenging puzzles?

    All the best,

    Nick
    (A happy Go user!)

  • Dec 29 2012, 2:33 PM
    Chris Christensen responded:
    Thanks for the excellent tutorial(s) - this def. helped me continue to wrap my head around different ways to solve problems with concurrency.

    I started with a simple test based on the expected results from the tutorial, but I am a little stumped as to how the solver is actually finding the missing numbers with the elimination blocks - it seems like it's just copying the Set() array.

    Here's a pass with the test that's failing for me:
    https://github.com/christianchristensen/gosudoku

    Thanks again!