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.

Uh-oh

1. Computers can generate Sudokus
2. Computers can solve Sudokus
3. Skynet determines that humans are useless. It then creates what is called "virtual worlds" in a campaign to exterminate the global human population birth rate.

Re:Uh-oh

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.

Well, it's ultimately a logic puzzle.

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.

Splitting Hairs

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.

Brute force?

Ultimately this approach simply encodes the rules of sudoku, and the state of an unsolved sudoku puzzle in logic statements, and then passes it off to a reasonably general logic solver, namely the dependency/conflict resolver in apt-get/aptitude. That's not really brute force at all.

Whether or not the solution is "brute force" depends on the manner in which debian's dependency/conflict resolver operates. There's many approaches to solving this problem, from gross brute force to reasonably complex machine le

I Disagree and I Agree

Sudoku doesn't have clever logic and elegant methods.

Check out the various strategies listed on this Sudoku Solver. [scanraid.com]

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.

Re:Splitting Hairs

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.

Elegant methods

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.

Sure, there are brute force methods. They are often techniques that dive into deep "consequence" trees to find contradictions. Those are, by their very nature, annoying for people to do and thus attractive for computer solutions. Nishio, tables, all of those just make sudoko boring and feel like you're executing a computer program in your limited-RAM brain.

But those aren't the "clever" or "elegant" methods. Sudoku techniques that I would consider elegant are things like sashimi x-wings, XYZ-wings, the various type of unique rectangles, and such. I enjoy trying to discover patterns like these in really tricky sudoku problems. I expect I'm not the only one, given the popularity of the puzzle over the last few years.

If you want to get really deep, you can use sudoku puzzles to explore mathematical group theory.

All of this (and what you said in your post) are true for other puzzles such as the Rubik's cube. Perfectly suitable for machine automation, but still fun for some of us us lowly humans as well.

Re:

The "Propagating Constraints" section of this article is quite a bit less brute force than the "search" section:

http://norvig.com/sudoku.html [norvig.com]

Re:Well, it's ultimately a logic puzzle.

Actually, Sudoku is a http://en.wikipedia.org/wiki/Vertex_coloring [wikipedia.org] for a special graph. From mathematics perspective, it is thus pretty boring, although that doesn't mean it cannot be fun.

Aptitude rather than Dpkg

And he didn't even use Super Cow Powers to do it!

Software used for weird purposes?

This is very cool! Kind of like implementing the Towers of Hanoi in vim or something. I'm going to test it against some puzzles from this here handy dandy Sudoku book. Now if only someone would make a Chess solver out of dpkg. You choose any out of the huge number of possible mate layouts and it will compute the dependencies from the start of the game to that mate layout! Implementing this should be so obvious that only a total fool won't immediately see how to do it, so it is left as an exercise for the reader.

Make

Probably also could be done using Make, which is really an expert system in disguise. Ant-heads won't know what I'm talking about. (Mod to +5 Flamebait.)

Re:Cheat code for even Sudoku??

Because cheats impress babes. left-right-left-right-a-b-start! left-right-left-right-a-b-start! I think I feel tingley.

Re:Cheat code for even Sudoku??

Because cheats impress babes. left-right-left-right-a-b-start! left-right-left-right-a-b-start! I think I feel tingley.

Please hand in your geek card immediately.

Re:Cheat code for even Sudoku??

I just feel sorry for geeks living in Soviet Russia. I've heard horror stories that suggest that over there, the geek cards hand in the geeks. Can you imagine the betrayal of your geek card giving you up like that?

Re:Cheat code for even Sudoku??

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.

Re:Cheat code for even Sudoku??

That's the 2-player code.
Up-Up-Down-Down-Left-Right-Left-Right-A-B-(Start) is single player contra.

Re:Cheat code for even Sudoku??

WRONG!

You inverted the A and B.

Yes! That's another geek card today. Only 2 more until my geek upgrade.

Re:Cheat code for even Sudoku??

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.

Re:Cheat code for even Sudoku??

Exactly. This guy doesn't care about the sudoku puzzle, he cares about the programming puzzle.

Re:Cheat code for even Sudoku??

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]) :-
  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).

Re:Cheat code for even Sudoku??

It's probably less costly to take a square away at a time and check to see if it's still solvable than to populate a random start and see if it's possible to solve it. And probably less complicated as well.

Isn't that pretty much exactly what I said? Create a random valid solved puzzle, then start removing squares...

Re:Cheat code for even Sudoku??

RTFA. I know, I know, what am I suggesting, it's Slashdot.

Here's the quick version: Russell Coker remarked [coker.com.au] that "a package management system that can solve Sudoku based on package dependency rules is not something that I think would be useful or worth having."

Daniel Burrows realized that apt could, in fact, currently be used to solve Sudoku puzzles [algebraicthunk.net], and wrote a Python script to automate the process of creating the packages required to do such a thing. That's the linked article, and it gives the background I'm repeating here.

I, personally, think it's pretty damned cool. Useless, but cool.

And, as the article points out, there exist better Sudoku solving algorithms. apt is a rather poor Sudoku solver, mainly because it's designed to come up with the "best" dependency resolution rather than solve Sudoku. It's not to "cheat" at Sudoku, but rather to demonstrate the power of the apt dependency resolver.

Re:Cheat code for even Sudoku??

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.