Solving Sudoku With dpkg 190
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.
Uh-oh (Score:3, Funny)
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)
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)
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)
Re: (Score:2)
Re: (Score:2, Insightful)
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.
Re: (Score:2)
Actually, it's a rather different grammatical structure that your directions yield. "Mashed potatoes" is a noun by itself, in what I was talking about. In your "Yields" sentence, mashed has reverted to a relative verb, and mashed potatoes no longer has the same meaning it had as a noun before. No, what you really have is "Two potatoes that have been mashed". If you were to use a counter word, (which is what we're actually talking about), you'd have to say "two portions of mashed potatoes." In other words,
Re: (Score:2)
Re: (Score:2)
You all killed my joke with your "sudoku" vs "sudokus" debate.
Well, it's ultimately a logic puzzle. (Score:5, Insightful)
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)
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
I Disagree and I Agree (Score:5, Informative)
Sudoku doesn't have clever logic and elegant methods.
Check out the various strategies listed on this Sudoku Solver. [scanraid.com]
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: (Score:2)
There are certainly some tricks to do it, but if you're starting with a fairly empty board then early on it does tend to end up as a lot of guesswork. 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.
Real Men use a Pen (Score:2)
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.
Re: (Score:2, Insightful)
Re: (Score:2)
There's a reason the game is best played with a pencil
You're missing half the point of Sudokus if you play them with a pencil.
Re: (Score:3, Informative)
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/ [sudokusolver.co.uk] that explains how it solves any Sudoku that you enter. This has a couple more methods to
Re: (Score:2)
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
I am trying to find a way to involve MS in the discussion but that seems too far fetched...
Re: (Score:2)
On a barely related note, I never realized before that "you must be new here" meant "noob!".
Hmm, I think "noob" (or newbie or rookie) refers to identifying a person whom has made a simple mistake, like someone newly hired to a job.
While "you must be new here" is used, in a cynical manner, to agree with and expound upon a commonly occurring problem. A full expression might look like: "if you just now noticed that problem, for the first time, then you must be new here, because it happens all the time".
Re:Splitting Hairs (Score:5, Interesting)
Sudoku can be solved by trying values in cells until a conflict is reached and backtracking to try other assignments. That's the brute-force approach.
Most sudoku puzzles can be solved via implication, however. There is no need to "try" anything. Certain configurations of values in some cells can imply values in other cells. As a very simple example, consider a row that has all cells filled but one. The value of that unfilled cell is implied and can be filled in without having to try any other values. This is a basic example, but clearly more complex ones exist. This is essentially how people solve the puzzles, and I believe it is what the grandparent was describing.
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 standard optimizations of the brute force method as developed for constraint processing (CP) or Boolean satisfiability (SAT) solvers. But then again, many of those optimizations are similar to the "clever logic and elegant methods," especially those that perform propagation and follow implications.
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.
It would have been nice if you had written something backing up your own claim as well.
Re: (Score:2)
Most sudoku puzzles can be solved via implication, however. There is no need to "try" anything. Certain configurations of values in some cells can imply values in other cells. As a very simple example, consider a row that has all cells filled but one. The value of that unfilled cell is implied and can be filled in without having to try any other values. This is a basic example, but clearly more complex ones exist. This is essentially how people solve the puzzles, and I believe it is what the grandparent was describing.
Actually, that is exactly the method I was referring to. You look at the first cell and say, "Can the value of this cell be implied by the values of the cells in the same row, column, and square?" If the answer is yes, then you write the value. If no, go onto the next square and ask the same question. Continue throughout all squares, and then start over. Eventually the puzzle is complete.
Most people do this, except out of order. They look at a random cell, and ask if the value can be implied, and fill it in
Re: (Score:2)
You've never written a Sudoku solver, have you? If you do, you'll quickly discover that there is a point where you have filled in all of the squares for which there is only one unique value that is possible, and now you have to start looking at the squares that have two possibilities. Here's the basic algorithm:
1. Fill in all the squares for which a unique solution exists.
2. If a conflict is discovered, back up the binary search tree (see step 3) and take the next unexplored branch.
3. Take one of the squa
Re: (Score:2)
"there is a point where you have filled in all of the squares for which there is only one unique value that is possible, and now you have to start looking at the squares that have two possibilities."
If there are in fact two possibilites, you just write down anyone of them and move on.
"2. If a conflict is discovered"
If a conflict is discovered, then you were *wrong* there were not two possibilities but just one.
"When humans do this, we don't actually perceive it as trial and error"
What kind of human are you?
Practice Makes Perfect (Score:3, Insightful)
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: (Score:2)
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. :-)
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?
Sudoku Makes You Smarter (Score:2)
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? [findingdulcinea.com]
Re: (Score:2)
Do you enjoy being condescending and arrogant? Unl
Re: (Score:3, Insightful)
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
Re: (Score:2)
Well, run some tests then ;)
I haven't run tests to compare approaches, but I have messed around with it a bit. I do research on Boolean satisfiability (SAT), so I wrote a script to convert sudoku puzzles to SAT problems and ran a fast SAT solver (MiniSAT [minisat.se]) on them. The actual solution for any 9x9 grids I gave it took on the order of milliseconds. I don't know how that compares to other techniques, but it was fast enough that I didn't see much point in looking into it more.
There is a very detailed explanation of this approach written
Elegant methods (Score:5, Insightful)
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.
Re: (Score:3, Informative)
The "Propagating Constraints" section of this article is quite a bit less brute force than the "search" section:
http://norvig.com/sudoku.html [norvig.com]
Re: (Score:2)
The way human brains solve Sudoku doesn't necessarily use clever logic and elegant methods. Of course it is brute force.
Nothing is brute force about the way the brain solves Sudoku. You would have to be seriously autistic to be able to do even the simplest brute force of a Sudoku in your head.
Computers, on the other hand, can easily solve a 9x9 Sudoku by brute force.
Re: (Score:2)
Now you're splitting hairs here.
Not at all. Sudoku for humans is mostly about pattern matching. Discovering new patterns and then learning to apply them is the fun part.
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)
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
Re: (Score:3, Insightful)
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.
Re: (Score:2)
Dunno, having used package management tools on several unix flavors, and having resolved dependencies manually on systems where such tools hadn't yet evolved, I have a lot of respect for their logic capabilities. ;)
Aptitude rather than Dpkg (Score:3, Informative)
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.
To everyone else, please tag this article "badtitle."
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)
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)
Re: (Score:2)
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)
Dpkg in NP hard?! (Score:3, Insightful)
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.
Premature optimization (Score:2)
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 remai
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)
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)
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...
Re:Cheat code for even Sudoku?? (Score:5, Funny)
Re:Cheat code for even Sudoku?? (Score:4, Funny)
Because cheats impress babes. left-right-left-right-a-b-start! left-right-left-right-a-b-start! I think I feel tingley.
Please hand in your geek card immediately.
Re:Cheat code for even Sudoku?? (Score:4, Funny)
I just feel sorry for geeks living in Soviet Russia. I've heard horror stories that suggest that over there, the geek cards hand in the geeks. Can you imagine the betrayal of your geek card giving you up like that?
Re:Cheat code for even Sudoku?? (Score:5, Informative)
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.
Re:Cheat code for even Sudoku?? (Score:4, Informative)
Up-Up-Down-Down-Left-Right-Left-Right-A-B-(Start) is single player contra.
Re:Cheat code for even Sudoku?? (Score:5, Funny)
WRONG!
You inverted the A and B.
Yes! That's another geek card today. Only 2 more until my geek upgrade.
Re: (Score:3, Funny)
Hey now, there's a reason why they're called "joysticks."
Re: (Score:2)
Re: (Score:2)
Because cheats impress babes. left-right-left-right-a-b-start! left-right-left-right-a-b-start! I think I feel tingley.
Up up down down left right left right B A B A
Have you never played Contra?!?
Re: (Score:2)
Only one B A is required....
http://en.wikipedia.org/wiki/Konami_Code [wikipedia.org]
Re: (Score:2)
Only one B A is required....
http://en.wikipedia.org/wiki/Konami_Code [wikipedia.org]
Not from my experience with Contra. Maybe in other Konami games, though.
Re: (Score:2)
You're simply incorrect. *shrug*
Re: (Score:2)
Really? I'll take if from you if you insist, it's been over a decade and a half since I've played that game. Maybe I'll start looking for an emulator and a ROM for linux, I'd really like to play it again.
Re:Cheat code for even Sudoku?? (Score:5, Insightful)
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:Cheat code for even Sudoku?? (Score:5, Insightful)
Exactly. This guy doesn't care about the sudoku puzzle, he cares about the programming puzzle.
Re: (Score:3, Interesting)
The article is really a nerd article, and now we all have a challenge!
What is YOUR software solution to solve Soduku puzzles? Think outside the box, or go for the classic brute force method.
I would think about using languages like Erlang or Prolog to solve the problem, but classic languages with iterating over the alternatives will do also. Pick your poison!
Re:Cheat code for even Sudoku?? (Score:5, Interesting)
I suppose nothing will beat Prolog with constraint logic programming to concisely solve Sudoku [wordpress.com].
Actually, let me put the whole code here from the above blog post:
sudoku(P) :-
fd_domain(P,1,9),
Xs = [1,2,3,4,5,6,7,8,9],
row(P,Xs),
col(P,Xs),
unit(P,Xs),
fd_labeling(P).
row(_,[]). :-
row(P,[X|Xs])
setof(V,[C,I]^(for(C,1,9),I is (X-1)*9+C,nth(I,P,V)),L1),
fd_all_different(L1),
row(P,Xs).
col(_,[]). :-
col(P,[X|Xs])
setof(V,[R,I]^(for(R,1,9),I is (R-1)*9+X,nth(I,P,V)),L2),
fd_all_different(L2),
col(P,Xs).unit(_,[]).
unit(P,[U|Us]) :- // 3)*3+1, Re is Rs+2,
Cs is ((U-1) mod 3)*3+1, Ce is Cs+2,
Rs is ((U-1)
setof(V,[R,C,I]^(for(R,Rs,Re),for(C,Cs,Ce),I is (R-1)*9+C,nth(I,P,V)),L),
fd_all_different(L),
unit(P,Us).
Re: (Score:2)
Re: (Score:2)
Sorry, but this is not actually "the best way of solving Sudoku". It's more like "mapping sudoku to a set theory library/tool/language syntax and then calling it to solve the problem". Unless your metric is "the least amount of lines containing clear syntax", your solution is one of the worst ones I have ever seen.
A real, nice way of solving Sudoku must include your own algorithms. Even better: custom tailore
Re: (Score:3, Interesting)
Re: (Score:2)
Not really, while that is one way of doing it, there are other ways of solving the problem.
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.
The actual logic involved would be very different, and with this way you'd be able to reuse calculations from before by just checking the rows and box affected by the change to make sure that you can still get that
Re:Cheat code for even Sudoku?? (Score:4, Insightful)
Isn't that pretty much exactly what I said? Create a random valid solved puzzle, then start removing squares...
Just permute a valid solution! (Score:3, Interesting)
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.
Re: (Score:2, Informative)
Re: (Score:2)
Isn't that pretty much exactly what I said?
I'm currently writing a solver for questions from Slashdot using the Debian package dependency resolver. I'll let you know in a few days...
Re: (Score:2, Interesting)
Re: (Score:2)
Re: (Score:2)
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.
Sudoku's only interesting at the very hardest level, where you have to apply real logic to take it on. But then again, I've always found only the hardest problems are ever persistently interesting; if you're bored, do something more difficult and stop wasting both time and braincells.
Re: (Score:3, Interesting)
Let me get that straight, if you can't solve a problem it's a bad problem ?
How would you feel then if someone else did solve the problem that you could not solve ? Is it still a poor puzzle then ?
I read what you are saying as 'I like sudoku, but only the simple ones because I'm not clever enough to hold more than a few permutations of it in my head'...
Re: (Score:2)
You do know that the "number of guesses you need to keep in your head" is the primary criterion for judging the difficulty rating for computer generated puzzles, don't you?
Re: (Score:2)
(Darned fast little program, too. Won a trivial little prize with it.)
Re:Cheat code for even Sudoku?? (Score:5, Informative)
RTFA. I know, I know, what am I suggesting, it's Slashdot.
Here's the quick version: Russell Coker remarked [coker.com.au] 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 [algebraicthunk.net], 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.
Re: (Score:2)
I, personally, think it's pretty damned cool. Useless, but cool.
Which is why it is fun.
Now, if somebody makes a sudoku generator out of it, installing Linux will get a bit more fun.
Yeah, I know, Caldera Linux called, they want their install-time Tetris back.
Re: (Score:2)
This is one of those instances of problems being the same though the fields of application are far apart.
It's exactly why algorithm development is such an interesting field.
Now to get the sudoku programs to be accepted as general dependency solvers for package managers :)
Re:Cheat code for even Sudoku?? (Score:5, Insightful)
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.
Re: (Score:2)