0xDE (11011110) wrote,

Solving single-digit Sudoku subproblems

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(2n) on nxn Sudoku puzzles. That's fast enough to be very practical for 9x9 and 16x16 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.
Tags: exponential algorithms, papers, python, sudoku
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded