My paper for FUN 2012, "Solving Single-digit Sudoku Subproblems", is now on arXiv.org as arXiv:1202.5074.

In it, I revisited a problem I'd looked at earlier in a blog post from 2005, in which you want to make deductions about a Sudoku puzzle by looking only at the candidate locations of a single digit at a time. In that blog post, I showed that this kind of deduction is NP-hard to make optimally, which is why I had resorted to heuristics that never make incorrect deductions but that might fail to make some correct deductions. In my new paper, I describe an exponential-time algorithm that finds all possible correct deductions and takes time \( o(2^n) \) on \( n\times n \) Sudoku puzzles. That's fast enough to be very practical for \( 9\times 9 \) and \( 16\times 16 \) Sudoku and makes the heuristics unnecessary.

By this point there's a large body of work on exact exponential time algorithms for NP-hard problems (mostly graph algorithms), and also a large body of work on the computational complexity of combinatorial games and puzzles showing that they give rise to NP-hard problems. What I haven't seen much of is work like my new paper that puts these two together and does worst-case analysis of algorithms for exactly solving games and puzzles. So I think there may be a lot of low-hanging fruit in this direction.

This wasn't just a theoretical exercise, by the way: I implemented my new algorithm and included it in the Sudoku software included as part of my PADS library of Python algorithm implementations. Relatedly, because of my migration from CVS to Git, PADS has a new distribution mechanism: rather than downloading a tarball, you can get it by cloning a Git repository. See the README file for details.