Slashdot Mirror
Solving Sudoku With dpkg
Reader Otter points out in his journal a very neat use for the logic contained in Debian's package dependency resolver: solving sudoku puzzles. To me at least, this is much more interesting than the sudoku puzzles themselves. Update: 08/24 02:51 GMT by T : Hackaday just ran a story that might tickle the same parts of your brain on a game played entirely with MySQL database queries.
Sudoku can be solved by trying values in cells until a conflict is reached and backtracking to try other assignments. That's the brute-force approach.
Most sudoku puzzles can be solved via implication, however. There is no need to "try" anything. Certain configurations of values in some cells can imply values in other cells. As a very simple example, consider a row that has all cells filled but one. The value of that unfilled cell is implied and can be filled in without having to try any other values. This is a basic example, but clearly more complex ones exist. This is essentially how people solve the puzzles, and I believe it is what the grandparent was describing.
However, I do not believe that the grandparent is correct in stating that these methods solve sudokus in a fraction of the time of the brute force method if you allow for standard optimizations of the brute force method as developed for constraint processing (CP) or Boolean satisfiability (SAT) solvers. But then again, many of those optimizations are similar to the "clever logic and elegant methods," especially those that perform propagation and follow implications.
Sudoku doesn't have clever logic and elegant methods. There is only one method for solving sudoku puzzles, and it strongly resembles a computer doing brute force.
Don't mod me down if you disagree. If you disagree, consider writing a retort instead.
It would have been nice if you had written something backing up your own claim as well.
I suppose nothing will beat Prolog with constraint logic programming to concisely solve Sudoku.
Actually, let me put the whole code here from the above blog post:
sudoku(P) :-
fd_domain(P,1,9),
Xs = [1,2,3,4,5,6,7,8,9],
row(P,Xs),
col(P,Xs),
unit(P,Xs),
fd_labeling(P).
row(_,[]). :-
row(P,[X|Xs])
setof(V,[C,I]^(for(C,1,9),I is (X-1)*9+C,nth(I,P,V)),L1),
fd_all_different(L1),
row(P,Xs).
col(_,[]). :-
col(P,[X|Xs])
setof(V,[R,I]^(for(R,1,9),I is (R-1)*9+X,nth(I,P,V)),L2),
fd_all_different(L2),
col(P,Xs).unit(_,[]).
unit(P,[U|Us]) :- // 3)*3+1, Re is Rs+2,
Cs is ((U-1) mod 3)*3+1, Ce is Cs+2,
Rs is ((U-1)
setof(V,[R,C,I]^(for(R,Rs,Re),for(C,Cs,Ce),I is (R-1)*9+C,nth(I,P,V)),L),
fd_all_different(L),
unit(P,Us).