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

Re:Cheat code for even Sudoku??

[Anonymous Coward]

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.

Aptitude rather than Dpkg

[Asuranceturix]

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

Re:Cheat code for even Sudoku??

[_xeno_]

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

Here's the quick version: Russell Coker remarked 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, 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.

I Disagree and I Agree

[Nymz]

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.

Re:I Disagree and I Agree

[asc99c]

It's very rare that I have found the need to guess in a Sudoku. I've never seen a printed one in a newspaper where that was necessary - even the 'diabolical' ones.

Certainly I've made mistakes on some, and a couple of times I've run out of ideas and had to make a guess, but on running it through my own program, it's got the solution without taking guesses.

There is a good online solver at http://www.sudokusolver.co.uk/ that explains how it solves any Sudoku that you enter. This has a couple more methods to try than my own solver program, but a lot less than some. I've seen all kinds of complicated algorithms, but I think many of them are never required if you've properly applied the simpler ones.

For a real challenge, this page has a number of grids that couldn't be solved using a proper algorithm (other than guess and check):
http://www.sudokusolver.co.uk/grids_nologic.html

Re:Splitting Hairs

[maxume]

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

http://norvig.com/sudoku.html

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

[tukang]

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 problem

Re:Cheat code for even Sudoku??

[DMUTPeregrine]

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

Mod up P, GP and P=NP: choose two

[jonaskoelker]

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/)

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 cowsay output (that is, an ascii-art cow saying "Have you mooed today"). Running 'aptitude moo' gets you "There are no Easter Eggs in this program". Running 'apt$GETITUDE --help' gives you "this apt[itude] does [not] have Super Cow Powers".

Just FYI ;)

Re:Just permute a valid solution!

[FireFlie]

Perhaps I'm misunderstanding you, but your method will still require a validity check. Many swaps will result in illegal puzzles. For instance, swap any two numbers on the same row or column.

3x3 sudoku is constant-time

[AySz88]

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.