nf.id.au

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.