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.
Whats the point of using cheat codes to solving Sudoku? Doesn't anyone play a game for just the plain fun of it?
slashdot rocks
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.
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.
ATTENTION SHOPPERS: PAY NO ATTENTION TO THE NECROTIC DOG PENIS. I REPEAT, PAY NO ATTENTION TO THE NECROTIC DOG PENIS CURRENTLY LOOMING OUTSIDE LOT 4. CONTINUE SHOPPING BUT PLEASE ENSURE YOU LEAVE VIA AN ALTERNATIVE EXIT AS WE ARE NO LONGER ABLE TO GUARANTEE YOUR SAFETY IN LOT 4, DUE TO THE NECROTIC DOG PENIS. FOR YOUR INFORMATION, LOTS 1, 2, 3, 5 AND 6 ARE CURRENTLY FREE OF BAYING NECROTIC DOG PENIS. PAY NO ATTENTION TO THE NECROTIC DOG PENIS. THANK YOU.
NECROTIC DOG PENIS: YOU THOUGHT IT WAS GONE, BUT IT'S BACK!
Lameness filter encountered. Post aborted! Lameness filter encountered. Post aborted! Lameness filter encountered. Post aborted! Lameness filter encountered. Post aborted! Lameness filter encountered. Post aborted! Lameness filter encountered. Post aborted! Lameness filter = censorship, lameness filter = censorship, lameness filter = censorship, lameness filter = censorship, lameness filter = censorship, lameness filter = censorship.
Your comment violated the "postercomment" compression filter. Try less whitespace and/or less repetition.
Now solve my dependency:
dpkg --build girlfriend
At least have it answer with some saucy ascii for christ sakes
I record my sleeptalking
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.
And he didn't even use Super Cow Powers to do it!
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.
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.
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)
"You know, Hobbes, some days even my lucky rocketship underpants don't help" -- Calvin
Let's seem yum do THAT!
I kid I kid.
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!
There's a reason the game is best played with a pencil, and I've used nothing but pen in every math class I've ever taken.
The paper quality of newspapers and sudoku booklets is thin and brownish, so pencil marks aren't very easy to see, and erasing on cheap paper is a disaster. At first I resisted using a pen, but now I'd never go back.
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.)
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.
Maybe this can be used to stress test the resolve-engine in apt-get, aptitude and synaptic.
Sudoku isn't a math puzzle, it's a logic puzzle...
Well, a logic puzzle is `applied logic' (an application of the study of logic). And, applied logic in a formal system is essentially what mathematics is. In fact, (!) the act of solving a soduko puzzle is an instance of a type of graph coloring problem which appears in combinatorics -- hardcore mathematics. Even more interesting, a program which can solve an n^2 x n^2 soduku type puzzle in polynomial time (in n) would be a miraculous thing: it would show that P=NP, since the question of asking whether such an n^2 x n^2 instance is solvable is NP complete! I'm a graduate student in mathematics and this sort of stuff is my cup of tea -- though, I admit that _doing_ Sodoku puzzles doesn't interest me at all. The AMS Notices published a little article about this a while back, but I don't know the citation.
Hell, there are no rules here-- we're trying to accomplish something. --Thomas A. Edison
You don't need a full solver to create a solved puzzle, I should think. Just start with the most basic puzzle and make legal permutations of it:
123|456|789
456|789|123
789|123|456
---+---+---
231|564|897
564|897|231
897|231|564
---+---+---
312|645|978
645|978|312
978|312|645
For example, you should be able to swap any two numbers everywhere.
Comment removed based on user account deletion
The dependency resolver in RPM is just as powerful and can also solve these kinds of puzzle. No promises on how fast it will solve them, however.
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/
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
Ask me about repetitive DNA
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.
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 ;)
I am sure that Steven Hawking, like the rest of us, gets smarter by thinking. But they do not get smarter by playing sudoku. Do you understand the difference?
Yes, I understand the difference between your opinion, and all the studies done on this subject. Do Brain Age and Sudoku really make you smarter?
Sudoku is NP complete. NP completeness means by definition that the problem can be expressed as a SAT problem (http://en.wikipedia.org/wiki/Boolean_satisfiability_problem). Basically NP complete means that you can see the problem as a black box and only check if a given solution solves the problem.
So the usual solution is *not* to write a new program for each np-complete problem, but to express them as a SAT problem and use one highly optimized SAT solver.
Obviously, dpkg does nothing more than solve a SAT problem (Solve: (( libA-v1 AND libA-v1-depencency) OR libA-v2 OR libA-v3) AND (libB-v1) and so on ), and therefore it can be used for any SAT problem.
> 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.
No, you can use only those permutations which are guaranteed to create a legal puzzle.
Like I said, if you swap, you have to do it *everywhere* (swap all 4s to 6s and vice-versa, not just swap two of them on some column).
I'm sure there are other ways to permute it which guarantee that the puzzle remains valid, but I haven't proven them.
Assuming you can prove that your algorithm for permuting them always results in a valid puzzle, you don't need any check at all (though you might want one just to check for bugs).
Install a new glibc version and dpkg will faithfully remove all the packages that depended on the old version of glibc. Even if it means removing the linux kernel.
First rule of optimization: Don't.
NPC problems often exhibit "phase transitions" or pockets of the problem space that are easily solvable one way or the other. When the hard problems never occur in practice, keeping the code simple is the best way to go.
Once someone shows me a real-world, dpkg problem that would take unacceptably long to solve with the current dpkg solver (maybe one already exists), then we can talk about adding an optimized version. Until then, exponential dpkg problems should remain the province of jokes (as my post was originally intended).
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.
How many of you guys have actually done this?
I once had to write a code to solve the 2D Ising model with a Monte Carlo method, in this case basically a simulated annealing algorithm. I eventually realised I could apply it to sudoku solving, but I could only ever get it to solve rows and columns, and then it would get stuck in a fairly ordered solution, but one where more disorder was required to get into a more ordered state. I began to try and add random fluctuations to get it to work, but I eventually abandoned it to work on the actual physics project. It would probably make an interesting exercise for one of you...
xterm -n 8
Maybe you kid, but it is interesting that APT seems to be able to handle more complex dependency graphs than RPM. What I've never understood is why it needs to. What more is there to package dependency resolution than a simple recursive procedure? In pseudocode:
This year in my Artificial Intelligence class we were asked to right a program in java that would solve an inputed sudoku puzzle, after some internet googling and alot of papers read, me and my group partner discovered that it is considered a really bad way of solving this kind of puzzles, so we started to try to find a way that would make it possible to solve a puzzle in a short period of time. After a lot of hard work and big disapointments, even some teachers started saying that solving a easy puzzle in 20 000 generations would be considered good, but I didnt give up and in the last they I came with a solution that would use the power of constrains and only after it, genetic , what I did was create an individual where in each cell could only be put numbers that weren't on the same row column or sub matrix this made the number of possible individuals lower by a big chunk and we were able to solve the easy puzzle on 10 generations max and the medium/hard difficulty in 100. BUT even with this algorithm we weren't able to solve some of the harder puzzles like this one [url=http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#Exceptionally_difficult_Sudokus_.28Hardest_Sudokus.29]this one[\url](wikipedia) in a constant speed, come times it would solve under 100 gen other only after more than 20000, but this are sudoku puzzle that bypass any kind of logic and are considered impossible to be solved using human logic cause... So I guess I would like to see how dkpg would handle them ;)
...to readapt Debian's... hehe! "re-adapt", get it? ;-)
I am an ACCA student. Got a query on Accountancy/Finance? Maybe I can help!
This begs the questions...
1) Can you create the next cool game using logic from existing systems?
2) Can you create the next cool system using game logic?
Oh, I almost forgot ... profit
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.
College-Pages.com - Online Colleges, Degrees, and Programs