I’m the kind of person to whom solving a puzzle by hand is not nearly as satisfying as breaking said problem down and getting a computer to do it for me. Perhaps it’s part of the notorious laziness that is actually a positive characteristic in programmers: the inability to do anything more than twice without being driven to automate it. Whatever, it was an interesting, but not especially hard, problem.
Most of the process of solving a sudoku simply consists of checking the constraints for each cell by looking at the filled cells in the same row, column, and three-by-three sub-grid. When there is only one possibility, that cell can be filled.
After a while, however, one comes to the point at which there are no longer any unambiguous cells, and one must take a guess from two or more possibilities. For a computer, this is simply a case of saving the state and choosing one of the forks; if the branch turns out to be fruitless, it is trivial to restore the previous state and to take the (or an-) other fork. This might happen more than once in a really hard puzzle. With a pen and paper, it requires either a good eraser and a copy of the pre-guess state, or the ability to visualise the grid several turns ahead.
Here’s my Ruby implementation of a sudoku solver. It’s fast: it solves a puzzle instantaneously.
It turns out, however, that generating a decent sudoku puzzle is much, much harder than merely solving one.
This is a
tar.gz archive containing the solver library, a command-line front end, and a couple of demonstration puzzles.
2005-07-26 15:18 UTC. Comments: 4.