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:

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

1 comment:

  1. Really helpful down to the ground, happy to read such a useful post. I got a lot of information through it and I will surely keep it in my mind. Keep sharing. If you are looking for some useful data and information regarding Soduku Master then visit Sudoku Champs.

    ReplyDelete