[ondrasej]

If you do the constraint propagation right, the number of trials and errors will be very small (and it will be only one trial and no errors for the easy ones).

I'd be very interested to see what an algorithm that solves any valid sudoku puzzle looks like. (apart from pathologic solutions like querying a database of all valid 9x9 sudoku combinations).

[crux_]

That would be a big database. (10^21 entries,roughly.) http://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerati...

[ondrasej]

That's why I called it pathologic... ;)

Edit: using the symmetries described in the same Wikipedia article, the size of the database could be reduced significantly to roughly 5*10^9, which is quite manageable.

[jules]

> I'd be very interested to see what an algorithm that solves any valid sudoku puzzle looks like.

You might be interested in the article linked to by this post.

[ondrasej]

The code in the post is based on depth-first search, which basically is a trial and error approach. A well implemented and effective one thanks to constraint propagation, but it is still trial and error. And there are cases, in which backtracking (trial and error) is necessary - at least one of them is documented in the post (the puzzle "hard1" that took 188 seconds).

[jules]

There is no meaningful difference between trial and error and without trial and error. It makes this no less of an algorithm.

[wccrawford]

If you get down to trial and error at all, your best odds are 50/50. If it's easy enough to guarantee the right guess, it's not a guess.