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.
Because cheats impress babes. left-right-left-right-a-b-start! left-right-left-right-a-b-start! I think I feel tingley.
Once you start despising the jerks, you become one.
Sudoku isn't a math puzzle, it's a logic puzzle - just one where you're filling in digits instead of the man in the blue house smoking Pall Malls and having a goldfish.
The digits 1-9 in Sudoku could be replaced with any 9 other symbols without changing the underlying rules. So yeah, logic can be used to solve it.
Village idiot in some extremely smart villages.
Jesus Christ. If you're going to mention the greatest cheat code ever, get it right:
Up-Up-Down-Down-Left-Right-Left-Right-B-A-(Select)-(Start)
Amateur.
First, it's not "cheat codes".
Second, I, and I'm sure I'm not alone on this, would rather write a program to solve sudoku than actually play sudoku. Some people love sudoku; I found it boring. Now writing software to solve a puzzle, that's interesting.
Maybe not
It isn't about beating sudoku. It's about taking one tool, and using it to do something that its creators never imagined.
It's the same reason people use laser cutters to slice their pizza or try to create the shortest possible quine in their language of choice. This guy might not even give a shit about sudoku; he just wanted to see if he was clever enough to solve sudoku using dpkg.
Sudoku doesn't have clever logic and elegant methods.
Check out the various strategies listed on this Sudoku Solver.
Don't mod me down if you disagree. If you disagree, consider writing a retort instead.
You must be new here. Only posters that take the time to back up conclusions with reasoned responses are moderated down. Conversely, those that write short, unsupported attacks are moderated up... because in reality most people can only be trusted with 2 tags - I agree or I disagree.
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).