typodupeerror

## Solving Sudoku With dpkg190

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.
This discussion has been archived. No new comments can be posted.

## Solving Sudoku With dpkg

• #### Uh-oh (Score:3, Funny)

on Saturday August 23, 2008 @10:41PM (#24723565) Homepage Journal

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: (Score:2)

I hate to be pedantic (ok, no I don't, I love it), but since it's a Japanese word, the plural of Sudoku is Sudoku. Also, there should be a macron on the u, but that's way less important.
• #### Re: (Score:2)

Who ever said that when you're speaking English you have to apply the rules of pluralization for whatever language you're borrowing a loan word from? We do it sometimes, but not always. We also mix latin prefixes with greek root words sometimes (which gets George Orwell's panties in a twist, but I'm pretty sure I don't care). If the plural is commonly accepted as "sudoku" (is there precedent on this yet?) then we do it the Japanese way in this case. But there's no reason that just because the word comes

• #### Re:Uh-oh (Score:4, Interesting)

<{moc.liamg} {ta} {iopluiok}> on Sunday August 24, 2008 @12:30AM (#24724017)

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: (Score:2)

"Cul de sacs" doesn't make any more sense than "sodokus" -- "cul de sac" means "bottom of the sack" (which is why Bilbo and Frodo Baggins lived on Bag End) and culs de sac is the proper French plural. But everybody says "cul de sacs" because we aren't French.
• #### Re: (Score:2)

Ah, but here lies the difference: In English, a "cul de sac" is both a general noun and a specific one. You can talk of cul de sacs and that cul de sac, as it has become one single thing. You're talking of something that has come into the language with a different meaning altogether. It's in the dictionary as "cul-de-sacs". Sudoku, on the other hand, is only general - it's the type of puzzle. Having two of them would only make sense if qualified some how, such as "two sudoku puzzles."
• #### Re: (Score:2)

You all killed my joke with your "sudoku" vs "sudokus" debate.

• #### Well, it's ultimately a logic puzzle. (Score:5, Insightful)

on Saturday August 23, 2008 @10:46PM (#24723585)

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 (Score:3, Interesting)

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? (Score:3, Insightful)

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

• #### Re: (Score:3, Informative)

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.

How did this get modded insightful? Just because numbers don't have to be used doesn't mean it's not math.

Sudoku is a set theory [wikipedia.org] problem

• #### Re: (Score:2)

Just because numbers don't have to be used doesn't mean it's not math.

You must be a mathematician [xkcd.com]. :)

Sudoku is a set theory [wikipedia.org] problem

Yes, but set theory is a subfield of mathematical logic [wikipedia.org], which came about when people decided to apply logic to their math (before which all math was presumably illogical, and used only irrational numbers). And in studying, you would have learned that this sort of logic puzzle most likely predates the existence of set theory by some number of centuries, so I clearly cannot choose the wine in front of me.

• #### Re:Well, it's ultimately a logic puzzle. (Score:4, Insightful)

on Sunday August 24, 2008 @02:33AM (#24724421)

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.

• #### Re: (Score:2)

Sudoku is a set theory problem

Could you please express sudoku as a set theoretic problem? Bonus points if it's not the trivial solution of saying "... but everything is a set in ZFC, so this concerns sets" :)

I'd say that it's a combinatorics problem; in particular, it's nine-coloring graphs of a very restricted structure: one vertex per square, and for every square x there's an edge between x and y if y is in the same row, column or cluster as x. (N-coloring means assigning to each vertex a color from a set of N colors, such that no t

• #### Re: (Score:2)

man in the \$COLOR house smoking \$BRAND and having a \$SPECIES.

Spoiler warnings next time or you hand in your geek card! ;)

• #### Re: (Score:2)

Right, right... it's been so long since I did that puzzle, I doubt those were the real answers (though I suppose there should be multiple permutations of the puzzle floating around out there, potentially including one in which they are).

And let us not forget that he drinks \$BEVERAGE.

• #### Re: (Score:2)

Indeed. The Viz once ran a feature called "Su Doc Who" with all the numbers replaced by pictures of the various Doctors.

• #### Re: (Score:2)

Sudoku is a graph colouring problem. That counts as maths to me :-)

• #### Re: (Score:2)

The distinction between math and logic is pretty vague. Logic started out as the branch of philosophy that studied correct reasoning, but nowadays its students are mostly scientists and engineers interested in formal reasoning. That aligns it a lot more closely with math than with philosophy.

At the college I went to, logic was taught by a guy who had a degree in philosophy, but had lost interest in the entire subject, except for formal logic. Except for the mandatory turn at freshman intro to philosophy (wh

• #### Aptitude rather than Dpkg (Score:3, Informative)

on Saturday August 23, 2008 @11:17PM (#24723717)

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

• #### Re: (Score:3)

Finally, someone who GETS it.

I wanted to comment "Let's see rpm do that!" but before I could click, I realized that dpkg by itself cannot solve puzzles of any kind.

To the idiot who modded this "overrated," please pull your head out of your ass and type "aptitude --help" when you get a chance.

• #### Mod up P, GP and P=NP: choose two (Score:3, Informative)

Allow me to clarify parent and grand-parent for those of you who don't read articles:

As a proof-of-concept, I have written a hacky Python script, named debsudoku.py, that can convert ksudoku saved games into Packages files suitable for use with apt-get or aptitude.

(Source: TFA, at http://algebraicthunk.net/~dburrows/blog/entry/package-management-sudoku/ [algebraicthunk.net])

Emphasis added. Note that dpkg doesn't solve the dependency puzzle, but apt-get, aptitude and other package managers do (including synaptic and gnome-app-install [the "Add/Remove" thing]). Hence the suggested badtitle (which I agree with).

The 'aptitude --help' bit and the super cow powers: if you run 'apt-get moo', you'll get a cows

• #### Proof Positive (Score:3, Funny)

<beaufabry+slashdot,org&gmail,com> on Saturday August 23, 2008 @11:56PM (#24723901)
Let's seem yum do THAT!

I kid I kid.
• #### Re: (Score:2, Funny)

It probably could, but you'd have to wait ten times longer than it took to solve the problem for it to download all the headers first.

• #### Software used for weird purposes? (Score:5, Insightful)

on Sunday August 24, 2008 @12:07AM (#24723951)
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.
• #### Re: (Score:2)

There used to be 'emacs -e tower-of-hanoi'. I'm not sure if it got yanked from the source tarball, but it was an interesting way to show why old tape-based rotation schemes and levels of 'dump' backups worked the way they did.
• #### Re: (Score:2)

It's still there. esc-x hanoi It takes an argument which is the size of the towers. You can google for sudoku.el to find a sudoku solver in elisp.

• #### Make (Score:5, Funny)

<michael@michaelmalak.com> on Sunday August 24, 2008 @01:10AM (#24724139) Homepage
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.)
• #### Dpkg in NP hard?! (Score:3, Insightful)

on Sunday August 24, 2008 @01:12AM (#24724147)

Since Sudoku is NP complete, doesn't this mean Dpkg is NP complete?!

Oh, the humanity! I'm just waiting for an evil set of dependencies to crop up that makes it go exponential.

• #### Re: (Score:2)

Satisfying dependencies [wikipedia.org] is...

• #### 3x3 sudoku is constant-time (Score:3, Informative)

Sudoku, in the way that it's being solved here and how most people think of it (with 9 digits and 3x3 boxes), is not NP-complete. Its board size is finite, so there are a bounded number of possibilities to try (fewer than (9!)^9), so there exists a constant-time algorithm (trying every one of the possibilities, of which there must be less than 9!^9). But if you want to generalize to nxn boards, that changes things considerably.

• #### stress testing apt-get (Score:2)

Maybe this can be used to stress test the resolve-engine in apt-get, aptitude and synaptic.

• #### Time to plug myself (Score:3, Interesting)

on Sunday August 24, 2008 @04:20AM (#24724779)

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: (Score:2)

For puzzle generators that rely on brute-force for their solvers, this "only one solution" requirement is difficult to enforce.

It shouldn't be. They can just keep solving and see if they find more solutions.

• #### Re: (Score:2)

That assumes they can randomize enough not to simply try the same solutions over and over. Even randomized starts might lead to a later state which is the same as a previously tried state. Depending on your algorithm, you might then solve it exactly the same way as previously, without finding another solution. Proving that your algorithm is able to find all possible solutions would probably be harder than writing the algorithm.
• #### Re: (Score:2)

That assumes they can randomize enough not to simply try the same solutions over and over.

There's no need to randomize. Just pick 1 the first time, 2 the second...

#### Related LinksTop of the: day, week, month.

We all like praise, but a hike in our pay is the best kind of ways.

Working...