Dreamtime

PS: The number of steps needed in my algorithm is very limited and you won't have to wait even one second for the solution to drop (no matter how hard the soduko is). Although, I must admit that my implementation is very cumbersome as it is now. I do a lot of conversions between different views of the data involved. I was too eager to try it out, so I didn't have time to straighten it out.

Right, the truth is that you do not ever need to guess. The mathematical proof is simple: If you need to guess, there are several solutions (at least at one point) and that makes the soduko invalid. Also, I have constructed a program that uses pattern matching to solve sodukos. As far as I know, I am the first one who does not need to resort to brute force. With a little optimisation of my implementation, that should be the fastest algorithm possible. It is completely deterministic, too (meaning: You cannot get stuck and you always obtain the only solution in a finite number of steps). If you are interested, I can explain the idea behind my algorithm to you.