Forgot your password?
typodupeerror
Puzzle Games (Games) Debian It's funny.  Laugh. Math

Solving Sudoku With dpkg 190

Posted by timothy
from the after-all-it's-there dept.
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

Comments Filter:
  • by Shag (3737) on Saturday August 23, 2008 @10:46PM (#24723585) Homepage

    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.

  • by jlarocco (851450) on Saturday August 23, 2008 @11:10PM (#24723677) Homepage

    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:Splitting Hairs (Score:1, Insightful)

    by WK2 (1072560) on Saturday August 23, 2008 @11:17PM (#24723725) Homepage

    are fairly boring when compared to clever logic with elegant methods, that can solve sudokus in a fraction of time.

    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.

  • by Drakonik (1193977) <drakonik@gmail.com> on Saturday August 23, 2008 @11:26PM (#24723759) Homepage

    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.

  • by Drakonik (1193977) <drakonik@gmail.com> on Saturday August 23, 2008 @11:28PM (#24723765) Homepage

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

  • Elegant methods (Score:5, Insightful)

    by SeanAhern (25764) on Saturday August 23, 2008 @11:36PM (#24723811) Journal

    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.

  • Brute force? (Score:3, Insightful)

    by gehrehmee (16338) on Saturday August 23, 2008 @11:50PM (#24723877) Homepage

    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 learning approaches.

    The insight in this approach (although it's not an especially new insight to people playing with this sort of idea), is the relationship between puzzles and other day-to-day computing problems purely as constraint satisfaction problems, which essentially means that we describe the problem abstractly without all the trappings of how humans interpret the problem, and let a computer with little to no "general purpose" knowledge or "common sense" come up with the solution on its own (and of course, of us being able to read out the solution once the computer nails it)

  • by suck_burners_rice (1258684) 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.
  • by omeomi (675045) on Sunday August 24, 2008 @12:24AM (#24724007) Homepage
    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...
  • by WiseWeasel (92224) on Sunday August 24, 2008 @01:05AM (#24724115)

    Keeps your logic skills sharp. It's good mental exercise, in the vein of Brain Age and such... Gotta keep that noggin fit, especially if your day job isn't challenging you enough.

  • Dpkg in NP hard?! (Score:3, Insightful)

    by mdmkolbe (944892) 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.

  • by azgard (461476) 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.

  • by arctanx (1187415) on Sunday August 24, 2008 @02:40AM (#24724457)

    You're doing it wrong. You're going to get yourself in a mess if you take random guesses in sudoku. Getting the full value of the brain exercise is the act of reducing the clues to a single number for a particular square all in your head. Of course, with the hard ones unless your brain is awesome you get a stack overflow before you can piece together enough clues to narrow a square down to one number, but your average puzzle in the 'paper is quite reasonably solved in a progression of logically chosen steps.

  • Re:Splitting Hairs (Score:3, Insightful)

    by jonaskoelker (922170) <jonaskoelker@gnu.BLUEorg minus berry> on Sunday August 24, 2008 @04:52AM (#24724893) Homepage

    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 [...]

    Well, run some tests then ;) Seriously, though: as you point out yourself, if you add some simple heuristics to the brute-forcing it ceases being brute-force. Guess what, the heuristics for solving Sudoku problems (you've pointed one out yourself) eventually run out, and you have to guess and backtrack or brute-force in some other way.

    If we compare the completely vanilla brute force (that's 9^(n^2) tries where n^2 is the number of squares) with the heuristics-plus-brute-force, you may get something better than a constant factor time improvement (that is, time is reduced with more than just a fixed fraction). However, the Sudoku problem (for arbitrary-sized boards) is NP-complete, so you can't get down to polynomial time.

    Although typical Sudoku puzzles (with 9×9 grid and 3×3 regions) can be solved quickly by computer, the generalization to larger grids is known to be NP-complete. Various optimization methods have been proposed for large grids.

    (Source: http://en.wikipedia.org/wiki/Sudoku [wikipedia.org])

  • by Nymz (905908) on Sunday August 24, 2008 @05:00AM (#24724921) Journal

    I guess I'm just annoyed by these people who think that they are thinking, and am trying to burst their bubble.

    I already learned all the chords on the guitar,
    --and I'm just annoyed by these people who think that practicing will make me any better.

    I already learned how to swim,
    --and I'm just annoyed by these people who think that practicing will help me win an Olympic Medal.

    Steven Hawking was simply born as a fully formed genius,
    --and I'm just annoyed by these people who think that his thinking everyday has helped him achieve anything... but bursting your bubble. :-)

  • Re:Uh-oh (Score:2, Insightful)

    by hublan (197388) on Sunday August 24, 2008 @11:28AM (#24726409) Homepage

    But you can count anything you want in English, as long as the context is clear. If you treat the noun as countable, it's countable.

    I'll take four milks and three beefs.

If a 6600 used paper tape instead of core memory, it would use up tape at about 30 miles/second. -- Grishman, Assembly Language Programming

Working...