Saturday, January 30, 2016

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: