Lambda the Ultimate

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?]

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 :-)]

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...

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.

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?

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 ;-)

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..

Quite ... ;-)

Lovely!