Slashdot Mirror
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.
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.
Village idiot in some extremely smart villages.
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.
Maybe not
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.
Exactly. This guy doesn't care about the sudoku puzzle, he cares about the programming puzzle.
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.
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.
McCain/Palin '08. Now THAT's hope and change!
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...
ZuluPad, the wiki notepad on crack