Sudoku solver

Ruby, cross-platform

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.

Download

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.

Comments

Skip to the comment form

  1. Antonio

    Wrote at 2006-07-18 15:42 UTC using Firefox 1.5.0.4 on Linux:

    Seems not to solve this
    ...5.9.3.
2..467..1
..98.3...
..2381.4.
814695273
.6.742...
...2.45..
7..1.8.29
.2.9.6...

  2. Paul

    Wrote at 2006-07-18 21:23 UTC using Firefox 1.5.0.4 on Mac OS X:

    Really? I get this solution:

    1 8 7 5 2 9 6 3 4
2 3 5 4 6 7 8 9 1
6 4 9 8 1 3 7 5 2
5 7 2 3 8 1 9 4 6
8 1 4 6 9 5 2 7 3
9 6 3 7 4 2 1 8 5
3 9 1 2 7 4 5 6 8
7 5 6 1 3 8 4 2 9
4 2 8 9 5 6 3 1 7

  3. RLM

    Wrote at 2008-09-21 21:02 UTC using Chrome 0.2.149.29 on Windows Vista:

    can you explain how to use this please

  4. RLM

    Wrote at 2008-09-21 21:17 UTC using Chrome 0.2.149.29 on Windows Vista:

    i get it now thanks

Leave a comment

Please read the comment guidelines before posting. Comments are Gravatar-enabled. Your email address will not be published.

To prove that you’re human, type human in the Bot check field.

Trying to post some program output or a long code sample? Please use a paste service and link to it instead.