I came across an interesting paper by Babu, Pelckmans, Stoica the other day, via my favourite Compressed Sensing blog Nuit Blanche.
The idea is that it is possible to formulate Sudoku as a linear system, with the board as a 9x9x9 indicator vector and the rules as a matrix encoding the different Sudoku constraints. The solution to this system with the minimal L1-norm will often be an indicator vector as well – and will represent the solution to the puzzle with the missing entries completed.
To play around with the ideas here I re-implemented the paper in Python, using CVXOPT. I’m going to try and explain all this coherently at the December London Python Dojo meetup…
Update: I’ve now updated the code with the help of the much-easier-to-use CVXMOD wrapper library, and put it on GitHub here if you want to play with it.
The original authors’ Matlab codes are available as well.