8 ms·
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).
by ondrasej 15y ago
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).
- wccrawford 15y agoIf 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.
- crux_ 15y agoThat would be a big database. (10^21 entries,roughly.) http://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerating_all_possible_Sudoku_solutions http://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerati...
- ondrasej 15y agoThat'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 15y ago> 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 15y agoThe 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 15y agoThere is no meaningful difference between trial and error and without trial and error. It makes this no less of an algorithm.