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.

Comments

Splitting Hairs

[Nymz]

Sodokus are typically solved by using logic and identifying relationships, but the article describes a clumsy brute force method. I will admit that I'm splitting 'mathematical' hairs here, and that it is an amusing thought to readapt Debian's simple dependency resolver, but crude solving functions, that simply guess at every possible solution, are fairly boring when compared to clever logic with elegant methods, that can solve sudokus in a fraction of time.

Re:Splitting Hairs

[whatnotever]

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??

[omeomi]

Also, if you're going to write a Sudoku puzzle generator, you have to write a Sudoku solver first. New puzzles are created by coming up with a random valid solved Sudoku puzzle, removing a bunch of numbers, checking to see if it's still solvable, and then removing some more...rinse, wash, repeat...

Re:Uh-oh

[Koiu Lpoi]

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??

[FireFlie]

Interesting? Writing a SAT program to solve sudoku takes less than five minutes. This is not an interesting puzzle for a computer.

Just permute a valid solution!

[Anonymous Coward]

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??

[Z00L00K]

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

[gringer]

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/

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

Re:Cheat code for even Sudoku??

[jacquesm]

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??

[seasunset]

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]) :-
  Cs is ((U-1) mod 3)*3+1, Ce is Cs+2,
  Rs is ((U-1) // 3)*3+1, Re is Rs+2,
  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).