Python Sudoku Solver

Inspired by Richard Bird's sudoku solution in Pearls of Functional Algorithm Design, I wrote a Python solver.

Since the rules of Sudoku involve row, column, and box-wise operations, it makes sense to have a solution for iterating over each of the three ways of dividing up a board. One possible solution is to write functions that all have custom logic for row, column, and box-wise operations (perhaps based on indexing or dictionary lookups, depending on the board implementation). Another, more functional solution is to write helper functions that transform the board, such that all functions can iterate over the board in the same way, regardless of whether it is a row, column, or box-wise operation. Ideally, the transformation functions are involutions, such that it is easy to return the board to its original arrangement (e.g. cols(cols(board)) == board). The latter is adopted in this solver:

http://nbviewer.jupyter.org/url/tarokuriyama.com/notebooks/sudoku.ipynb

Explicit Type Annotations

In languages with good type inference, it's often quick and easy to omit type annotations. As a student prone to typos, I've found that this can lead to pernicious bugs when the function parameters are not obvious.

In this example ported to F# from Richard Bird's book, glue is supposed to take a digit and a tuple of (Expression, Values) and return a list of (Expression, Values) tuples. But there is a syntactic bug that cannot be inferred without more context (n.b. the list delimiter in F# is a semi-colon rather than comma):

type Digit = int
type Factor = Digit list
type Term = Factor list
type Expression = Term list
type Values = (Digit * Digit * Digit * Digit)

let glue x ((xs :: xss) :: xsss, (k, f, t, e)) =
        [(((x :: xs) :: xss) :: xsss, (10 * k, k * x + f, t, e)),
         (([x] :: xs :: xss) :: xsss, (10, x, f * t, e)),
         ([[x]] :: (xs :: xss) :: xsss, (10, x, 1, f * t + e))]

In an IDE, the type checker makes the error obvious once annotations are added. Editing for the correct list delimiters, glue is defined as:

let glue' (x: Digit) (ev: Expression * Values) : (Expression * Values) list =
    match x, ev with
    | x, ((xs :: xss) :: xsss, (k, f, t, e)) ->
        [(((x :: xs) :: xss) :: xsss, (10 * k, k * x + f, t, e));
         (([x] :: xs :: xss) :: xsss, (10, x, f * t, e));
         ([[x]] :: (xs :: xss) :: xsss, (10, x, 1, f * t + e))]


Just another reminder that "explicit is better than implicit".