Sudoku

Sudoku is all the rage around here these days. I assumed Sudoku would be a standard example of constraint satisfaction by now, but it seems this isn't the case by the number of hits I get on google. I wonder why.

For your enjoyment: a Sicstus prolog solution, and an ECLiPSe solution.

Comment viewing options

Simple solver

I wrote a fairly stupid solver in Haskell, before I'd even tried solving a Sudoku puzzle manually. Turns out there are smarter ways to do it than they way I tried (and doing them manually is more fun). But it's an interesting exercise, all the same.

The interest in the puzzle lies in the fact that there are several different ways of deducing a "necessary" move (I tried only one, and used trial-and-error where that failed), and the best puzzles are solvable without the use of trial-and-error.

GUI + solver

David Easton has created a Tcl/Tk Sudoku GUI which includes code for solving puzzles. If you download the starkit, you can use SDX to unwrap it, and then the solver code is in sudoku.vfs/lib/app-sudoku/sudoku-solve.tcl, although the code is not as clear as the Prolog solver.

CSP solutions?

I would expect some DPLL kind of solution given the size of the statespace. Or is the solution [of a Sudoku problem] normally that far of the phase transition point/easy? (Not that I actually believe in phase transition)

Is that what you were wondering about too?

Ugh?

Is that what you were wondering about too?

Not really ;-)

Hmmm....

Maybe I shouldn't type LtU messages in between meetings ;-)

[But your are right BTW, looks like a pretty normal CSP problem to me]

[And also, I guess the intent of the original statement was: are Sudoku problems easily solved by trivial brute force? So no need for CSP solving?]

Too easy....

It is not really an interesting example because it is to simple, most puzzles are solved using only propagation, given a domain-consistent propagation algorithm for all different. The really hard instances require a few choice-points.

Ah

Maybe it's then a nice case to [derive by] brute-force minimal one-sat instances (or otherwise smallest unsat/hitting set instances), there was some interest for minimal one-sat on wikipedia ;-); then again, there are a lot of symmetries in the puzzle so preferably one would need to solve that first.

[Oh, forgot my manners; thanks :-)]

Limits of brute-force

The following puzzle only has 17 given numbers which, according to Wikipedia, is the minimal known.

This presents the pure brute-force solvers with a rather large space to search. You'll probably solve it long before the prolog code in the original post could.

1 - -  - - -  - - -
- - 2  7 4 -  - - -
- - -  5 - -  - - 4

- 3 -  - - -  - - -
7 5 -  - - -  - - -
- - -  - - 9  6 - -

- 4 -  - - 6  - - -
- - -  - - -  - 7 1
- - -  - - 1  - 3 -

(I found this puzzle here.)

Took a few seconds...

Select empty space with mouse to see solution:

184 963 725
562 748 319
397 512 864

239 657 148
756 184 293
418 239 657

941 376 582
623 895 471
875 421 936


My solver (which is not much evolved beyond brute force) took a few seconds to get there. I would have taken a lot longer to do it manually...

Brute Force is a relative term

Sure, searching all 9^64 possible ways of filling in the 64 blanks with the digits 1..9 is a (very!) slow way of solving the puzzle. But I wouldn't call this brute force, I would call it unreasonable.

There are easy and obvious ways to improve this algorithm. Consider this simple backtracking algorithm:

To check if a position is solvable:

1. Choose a blank square

2. Place an untried number in that square.

3. Did that placement violate the rules? Then go to 2.

(No numbers left to try? Then this position isn't
solvable)

4. Otherwise, check if this new position is solvable.

(No blank squares left? Then you have a solution!)

This recursive algorithm can be thrown at many different problems. It is easily implemented in almost any modern language. It is a brute-force approach that is a great place to start when you don't understand the problem very well.

There are non-deterministic choices in the first and second steps, but they don't affect correctness of the algorithm. They do effect the performance. (rather profoundly!) Simply choosing a blank square with a minimal number of possibilities is a great heuristic for step 1. This heuristic is essentially what Dominic's Solver does.

What I meant was ...

When I said "brute force" I actually meant the "guess and check" depth-first search strategy that Leon Smith described. I should have qualified my statement by pointing out how slow my hardware and run-time are. Re-implementing in C yields a 100-fold speed up.

What I meant by "avoiding brute force" was "using the rules of inference that human solvers use". This becomes essential as we scale up to, say, 25x25 grids.

We can still keep things elegant. For example, if we represent the grid as a 4-dimensional 3x3x3x3 grid, then the different kinds of region (rows, columns and squares) become constraints on different pairs of co-ordinates of the grid. We can also combine all of the inference rules into one as follows:

"Consider each cell to be the set of possible values that we know, or have inferred, that it might contain. Thus, a cell known to contain a 1 is {1} and a cell about which we know nothing is {1, 2, ... , 9}. A region is one of the 1x9 rows, 9x1 columns or 3x3 squares that are constrained to contain each of the digits 1--9. For any region, R, and for any subset of R, r, let V be the union of the possible values of all the cells in r. If the size of r is the same as the size of V, then no cell in R - r can contain any of the values in V."

Are we having fun yet?

20 ms

on a lowly K6 (or thereabouts, it's below timer resolution). This solver just keeps a bitmap of legal symbols per cell, updated whenever a symbol is entered into a cell. It repeatedly tries a symbol in a cell with the minimum number of options left, which most of the time avoids any need for backtracking.

The program started out in Haskell, but I rewrote it in C when I noticed that startup of the runtime dominated actual processing time. Now I don't consider Sudoku a puzzle for clever minds anymore... unless the grid is made a lot bigger.

This particular puzzle required finding 47 "hidden singles" and not a single guess, everything else was stupidly filling in the "obvious singles". That was easy ;-)

Not by hand

For your program, it was easy perhaps, but I did it by hand, and while I didn't have to guess, it wasn't easy..

Peter Norvig

A python solution, with a detailed exaplanations.

Generating Soduku is more interesting than solving

Designing a program to generate Soduku puzzles was one of the challenges in the Extravagaria workshop at OOPSLA last year.

Quite ... ;-)

Sudoku as homework problem in Oz

I thought there might as well be a link to the Sudoku page on HaskellWiki.

forth solver

I remember seeing is here.

I like semantics of forth, but I dislike its readability..

As part of a new Advanced Functional Programming course in Nottingham, I presented a Haskell approach to solving Sudoku puzzles, based upon notes from Richard Bird. The approach is classic Bird: start with a simple but impractical solver, whose efficiency is then improved in a series of steps. The end result is an elegant program that is able to solve any Sudoku puzzle in an instant. It’s also an excellent example of what has been termed “wholemeal programming” — focusing on entire data structures rather than their elements.

A literate Haskell script is available here.

Lovely!