Solving Sudoku With dpkg 190
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.
Splitting Hairs (Score:3, Interesting)
Re:Splitting Hairs (Score:5, Interesting)
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.
Re:Cheat code for even Sudoku?? (Score:3, Interesting)
Re:Uh-oh (Score:4, Interesting)
Then try this on for size: I believe that "sudoku" is a mass noun, much like all nouns in Japanese. In other words, you can't say "two sudokus" any more than you can say "two softwares" or "two mashed potatoes". You need a counter word, such as "two sudoku puzzles", which you'd have to use (something very similar) in Japanese anyways.
And besides, let's be honest. "Sudokus" sounds retarded.
Re:Cheat code for even Sudoku?? (Score:2, Interesting)
Just permute a valid solution! (Score:3, Interesting)
You don't need a full solver to create a solved puzzle, I should think. Just start with the most basic puzzle and make legal permutations of it:
123|456|789
456|789|123
789|123|456
---+---+---
231|564|897
564|897|231
897|231|564
---+---+---
312|645|978
645|978|312
978|312|645
For example, you should be able to swap any two numbers everywhere.
Re:Cheat code for even Sudoku?? (Score:3, Interesting)
The article is really a nerd article, and now we all have a challenge!
What is YOUR software solution to solve Soduku puzzles? Think outside the box, or go for the classic brute force method.
I would think about using languages like Erlang or Prolog to solve the problem, but classic languages with iterating over the alternatives will do also. Pick your poison!
Time to plug myself (Score:3, Interesting)
Here's my attempt at a solver / generator (Java backend, with a console frontend, a graphical frontend, and a j2me frontend):
http://cons.org.nz/~gringer/ [cons.org.nz]
I don't actually find sudoku puzzle *solvers* all that interesting, because they are able to do the solution by brute-force. Sudoku puzzle *generators*, on the other hand, tend to be more difficult, because one requirement for the traditional puzzles is that the puzzle must only have one solution. For puzzle generators that rely on brute-force for their solvers, this "only one solution" requirement is difficult to enforce.
Just to demonstrate this, see the following bug:
http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=351043 [debian.org]
Re:Cheat code for even Sudoku?? (Score:3, Interesting)
Let me get that straight, if you can't solve a problem it's a bad problem ?
How would you feel then if someone else did solve the problem that you could not solve ? Is it still a poor puzzle then ?
I read what you are saying as 'I like sudoku, but only the simple ones because I'm not clever enough to hold more than a few permutations of it in my head'...
Re:Cheat code for even Sudoku?? (Score:5, Interesting)
I suppose nothing will beat Prolog with constraint logic programming to concisely solve Sudoku [wordpress.com].
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).