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

Uh-oh

[Yvan256]

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:Uh-oh

[Koiu Lpoi]

I hate to be pedantic (ok, no I don't, I love it), but since it's a Japanese word, the plural of Sudoku is Sudoku. Also, there should be a macron on the u, but that's way less important.

Re:Uh-oh

[Al Dimond]

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 from Japanese that we have to use Japanese rules in English speech. If Sudoku turns out to be more than a fad and we come to use the word a lot I'd guess it would become more integrated with English and follow more typical English rules (I don't know if there's a commonly established way to do it now). Just my own guess.

Re:Uh-oh

[Koiu Lpoi]

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:Uh-oh

[Hal_Porter]

I hate to be pedantic (ok, no I don't, I love it), but since it's a Japanese word, the plural of Sudoku is Sudoku. Also, there should be a macron on the u, but that's way less important.

I thought the Makron was dead.

Re:Uh-oh

[Daengbo]

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.

Re:Uh-oh

[speilberg0]

The Makron will be pleased

Re:Uh-oh

[oxygenox]

The plural of English word "sudoku" is "sudokus", much like the plural of "forum" is "forums"--if you're speaking English, that is.

Re:Uh-oh

[hublan]

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:Uh-oh

[Daengbo]

I hope that you're not implying you can't say that. I'm not sure, so I'll just clarify. It happens in restaurants all the time. In your case, "a" milk is understood to be one glass and "a" beef is one order of the beef special for the day.

Re:Uh-oh

[Koiu Lpoi]

You know, I can also say anything I want in English, as long as it's understood to be imbrigligated.

No, sorry, there comes a gap when "what you're able to do" becomes separated from correct English, as with any language. "I waiting you here" is a perfectly understandable sentence (said to me by an Arab man), but you'd have to be an idiot (or extremely stubborn) to declare it correct.

Re:Uh-oh

[Koiu Lpoi]

Sudoku is a mass noun, because it describes the puzzle itself, not a singular one. A "Sudoku Puzzle" is a countable object. "Two Sudokus" would mean two completely different games or rule sets, not two individual puzzles. Just because masses of ignorant people say things like "Two Crosswords" or "Three Milks" doesn't mean it's correct. You wouldn't say "two papers" to talk about individual pieces, would you? No, you'd say "two pieces of paper".

Re:Uh-oh

[Anonymous Coward]

There is nothing wrong with "two mashed potatoes."

Recipe for "Two Mashed Potatoes"

Ingredients:
- Two potatoes

Instructions:
- Mash.

Yields two mashed potatoes.

Re:Uh-oh

[STrinity]

"Cul de sacs" doesn't make any more sense than "sodokus" -- "cul de sac" means "bottom of the sack" (which is why Bilbo and Frodo Baggins lived on Bag End) and culs de sac is the proper French plural. But everybody says "cul de sacs" because we aren't French.

Re:Uh-oh

[Koiu Lpoi]

Ah, but here lies the difference: In English, a "cul de sac" is both a general noun and a specific one. You can talk of cul de sacs and that cul de sac, as it has become one single thing. You're talking of something that has come into the language with a different meaning altogether. It's in the dictionary as "cul-de-sacs". Sudoku, on the other hand, is only general - it's the type of puzzle. Having two of them would only make sense if qualified some how, such as "two sudoku puzzles."

Re:Uh-oh

[Koiu Lpoi]

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, "Two| Mashed Potatoes" is not the same as "Two Mashed| Potatoes".

But I bet you knew that and were just being a smartass.

Re:Uh-oh

[Yvan256]

You all killed my joke with your "sudoku" vs "sudokus" debate.

Re:Uh-oh

[STrinity]

Other types of puzzles have their names pluralized in English, though -- crosswords, word searches, acrostics. Why should sodoku be treated differently, other than that's the way it's done in Japan?

Re:Uh-oh

[Daengbo]

What I just told you is taught in English books published by OUP. Count/non-count is not a hard and fast rule.

Steak is a count noun in America, while it isn't in Britain (one piece of steak). Conversely, lettuce is a count noun in Britain while it's non-count in America (one head of lettuce).

I'm not talking out of my ass here. It's difficult to search for this stuff to find a reference, but there's a grammar exercise by Oxford University Press which tests what I'm talking about here. Solve questions three and five. It just depends on whether the unit of measure is understood or not (e.g. chocolate vs. chocolates or candy vs. candies).

Re:Uh-oh

[Koiu Lpoi]

As I've said to other people, just because swaths of ignorant fools say it one way doesn't make that correct. It SHOULD be "two crossword puzzles", not "two crosswords".

Re:Uh-oh

[Anonymous Coward]

Don't be silly. I had two mashed potatoes for lunch! I took two potatoes, and I mashed them. Voila!

Re:Uh-oh

[Anonymous Coward]

Of course you can say "two mashed potatoes". Just like "two scrambled eggs" etc. Its equivalent to saying "I have two potatoes and both of them are mashed".

Re:Uh-oh

[Anonymous Coward]

I believe that "sudoku" is a mass noun, much like all nouns in Japanese.

Technical note: Not all Japanese nouns are mass nouns; they are simply unmarked for plurality (in most cases). The effect appears similar to how we use mass nouns, but that does not mean the Japanese nouns are actually mass nouns.

Just my $57.89 (two cents after taxes, inflation, and fees).

Re:Uh-oh

[Anonymous Coward]

Not any more retarded than Wapanese people butchering the Japanese language by mispronouncing the word in the first place.

Domo arigatoo, and good day to you.

Re:Cheat code for even Sudoku??

[pizzach]

Because cheats impress babes. left-right-left-right-a-b-start! left-right-left-right-a-b-start! I think I feel tingley.

Well, it's ultimately a logic puzzle.

[Shag]

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.

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

[Anonymous Coward]

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.

Or you could just write a few loops and brute-force the puzzle.

I just don't understand the appeal of such a simple puzzle. I guess it's better than the horoscope though.

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

[amaupin]

Yep, the numbers are just symbols.

In fact there are command line utilities out there that will randomly swap the numbers in existing puzzles and/or do transformations (mirror, rotation, etc.) on them to generate "new" puzzles.

And it's fairly easy to generate new puzzles anyway (even if rating their difficulty is nontrivial). Which is partly why there are fifty zillion self-published sudoku puzzle books for sale online. And tons of flash and javascript puzzles.

Here's one nifty javascript daily sudoku: sudoku cat.

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

[Anonymous Coward]

yes... but the kind of logic you need is a type of mathematical logic... so it is also a math puzzle. (digits are also symbols, and goldfish are also fish)

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:Well, it's ultimately a logic puzzle.

[WiseWeasel]

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:Well, it's ultimately a logic puzzle.

[EvanED]

Silly poster. The interesting thing isn't that you can use logic to solve Sudoku, it's that dpkg implements a logic strong enough to do it.

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

[Shag]

Just because numbers don't have to be used doesn't mean it's not math.

You must be a mathematician. :)

Sudoku is a set theory problem

Yes, but set theory is a subfield of mathematical logic, 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.

[Shag]

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. ;)

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

[azgard]

Actually, Sudoku is a http://en.wikipedia.org/wiki/Vertex_coloring for a special graph. From mathematics perspective, it is thus pretty boring, although that doesn't mean it cannot be fun.

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

[jonaskoelker]

man in the $COLOR house smoking $BRAND and having a $SPECIES.

Spoiler warnings next time or you hand in your geek card! ;)

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

[jonaskoelker]

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 two vertices with an edge between them have the same color).

You can think of graph coloring as covering the nodes in as few independent sets as possible; is that where you're aiming at when you say it's a set theoretic problem?

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

[tukang]

Could you please express sudoku as a set theoretic problem?

It can be expressed as a set cover problem

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

[Shag]

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:Well, it's ultimately a logic puzzle.

[Von Helmet]

Indeed. The Viz once ran a feature called "Su Doc Who" with all the numbers replaced by pictures of the various Doctors.

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

[gedhrel]

Sudoku is a graph colouring problem. That counts as maths to me :-)

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

[fm6]

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 (which some people complained he taught half-heartedly) logic was all he taught, and that from a strictly formal perspective — no study of fallacious reasoning, no mention of syllogisms. Most of his students (all of them in his upper division and graduate classes) were math majors. In fact, most of his classes counted as "physical science" rather than "humanities" for satisfying your graduation requirements — even though they were offered by the Humanities Division! His career kind of parallels that of the discipline he taught.

Re:Cheat code for even Sudoku??

[Anonymous Coward]

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??

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

Re:Cheat code for even Sudoku??

[jlarocco]

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??

[FooAtWFU]

Well, I wrote an algorithm (web interface here) to solve it and it was an interesting enough process. :)

(Darned fast little program, too. Won a trivial little prize with it.)

Splitting Hairs

[Nymz]

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.

Re:Splitting Hairs

[WK2]

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.

Re:Splitting Hairs

[Anonymous Coward]

Mod it up!

Re:Splitting Hairs

[whatnotever]

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: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:Splitting Hairs

[uofitorn]

"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.

The way human brains solve Sudoku doesn't necessarily use clever logic and elegant methods. Of course it is brute force.

However, it would be much more interesting IF a clever and elegant mathematical algorithm that doesn't rely on brute force could be devised to solve it in fewer operations. Does it exist? Maybe, and maybe not.

Re:Splitting Hairs

[Zosden]

Something like this for Sudoku?

Re:Splitting Hairs

[WK2]

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 if so. Going in random order doesn't help, it just makes them feel better, and less like they are brute forcing. And of course, every time you fill in a value, you then check every cell in the same row as that one, and column, and square. Then you go back to your primary brute force method.

I prefer puzzles that actually make you think. Ones that always have a solution, but you actually have to come up with a unique method for solving it. Like that thing with the horseshoes, the chains, and the ring. I suppose my first few sudoku puzzles were like that too. Before I knew how to figure them all out, I had to actually figure out how to figure them out. But continuing to do sudoku puzzles would be like doing a bigger version of that thing with the horseshoe and ring. I've already done that, I'm moving on.

Of course, sudoku puzzles have their place. They are very popular, and help people to relax. Of course, popular always means, "doesn't make you think." But bonus points for making people think they are thinking. I guess I'm just annoyed by these people who think that they are thinking, and am trying to burst their bubble.

Re:Splitting Hairs

[Daengbo]

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.

The value is determined. Implied would mean that there are certain common configurations and you stand a good probability of one outcome. I don't play sudoku, but it seems to me that there's no pattern in the choice of which numbers go in which squares (outside of the normal rules, of course).

Re:Splitting Hairs

[demallien2]

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 squares that has only two possibilities, and guess what the value might be.
4. If Sudoku is complete, end.
5. Goto 1

When humans do this, we don't actually perceive it as trial and error, because we try to did it without writing down the guess at step 3 (and subsequent consequences at step 1). But it infact what we are doing. You'll recognise this when you remember thinking 'That square is either a 4 or a 6, but it can't be a 4, because that would force the square over there to be a 7, which isn't allowed, because there is already a 7 in that row'. You're just using the algorithm above, but doing it in your head rather than explicitly.

Anyway, as others have noticed, there's no point in solving Sudoku by computer, except as an exercise in discovering what the algorithm truly is. Once you figure out that it's just a binary search tree, it quickly becomes very boring.

Re:Splitting Hairs

[jonaskoelker]

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)

Re:Splitting Hairs

[amorsen]

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:Splitting Hairs

[uofitorn]

Now you're splitting hairs here.

Re:Splitting Hairs

[adamofgreyskull]

First off, real brute force, not the kind I believe you alluded to in your first post, requires no thought at all, this much is true.

"Of course, sudoku puzzles have their place. They are very popular, and help people to relax. Of course, popular always means, "doesn't make you think." But bonus points for making people think they are thinking. I guess I'm just annoyed by these people who think that they are thinking, and am trying to burst their bubble."

Do you enjoy being condescending and arrogant? Unless you have some very narrow definition of "thinking" then you're talking out of your ass. Recognising patterns, applying logic, keeping track of sometimes complex state information, do they not count as "thinking" because they are relatively simple problems to implement in a computer program?

But then, perhaps the only Sudoku you've ever seen have had a handful of numbers missing (and been printed on circles of paper?), which this certainly implies:

"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."

Ok, so you apply your simplistic "brute-force" strategy to a Sudoku puzzle and you reach the final square, and you've filled in no squares using your ridiculously simple one-level deep attempt to imply the value of a cell from its row, column and 9-cell block. Now what? Perhaps you can agree that this requires some form of "thinking" even using your own inexplicable definition of the word. For further reading, another poster in this discussion showed this link with a number of the more complex sudoku solving strategies.

Re:Splitting Hairs

[amorsen]

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:Splitting Hairs

[glitch23]

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.

Sometimes brute-force is necessary.

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.

Yes, most can be solved via implication. There is a minimum number of values which must be present in a puzzle to even have a chance of solving it. I've heard the minimum is somewhere around 15-17 for a 9x9. There is a minimum number which must exist in order to solve it by implication otherwise backtracking must be implemented. This makes the logic to solve the puzzle more complicated since a snapshot of the puzzle must be stored multiple times in order to try every possible value placement until the right branch in the logic is found which solves the puzzle. There is no need to try anything for the easier puzzles (although those who don't understand the logic that well or who can't keep track of possibilities in their head will insert a number in pencil to see if it works out later on) but more difficult ones (where you have approx.

Re:Splitting Hairs

[Anonymous Coward]

Yeah. Thats close to how I solved sudoku: http://home.zcu.cz/~cima/sudoku_solver.htm
I'm using three dimensional array where used digits are removed. So if it is possible to determine the number belonging to the cell, it is the only digit that left in third dimension of an array.
Sudoku is quite brute force backtracking but contains few logic elements. Three years ago I tried to solve one manually, but my patience ran out so i decided to solve sudoku generally. And two afternoons later the html&javascript mentioned above was done.

Re:Splitting Hairs

[whatnotever]

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) 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 by someone else who tried this approach here. It's actually a great read on several related topics, including SAT solving/solvers in general, P vs NP, BDDs, and more. It's full of interesting links, too.

Re:Splitting Hairs

[turbidostato]

"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? I'm human and I clearly percieve this to be trial and error: I look at a square, then at its environment and I start making wider assumptions till I find a negate condition or a logic dead end that gives me just one choice (the extremest case would be holding the whole sudoku on my mind at once).

"Once you figure out that it's just a binary search tree, it quickly becomes very boring."

That's true both for computing solving *and* human solving. Of course, that doesn't mind if you try to solve it without pencil-guess: you only write down a figure when you are sure it's the right one by inference.

Re:Splitting Hairs

[Anonymous Coward]

Perhaps you can agree that this requires some form of "thinking" even using your own inexplicable definition of the word

If aptitude can solve it no thinking is needed.

Re:Splitting Hairs

[asc99c]

I have written a Sudoku solver, and it is very rare that this solution ever needs to be employed. I didn't find any in puzzle books or newspapers that required guesses. Although a quick google search turned up a few nasties.

The guess and check algorithm you are talking about is definitely pretty boring, but also takes a lot of CPU time. A decent algorithm that can solve most Sudokus by logic is a lot more interesting.

Re:Cheat code for even Sudoku??

[Anonymous Coward]

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?

Aptitude rather than Dpkg

[Asuranceturix]

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

Re:Aptitude rather than Dpkg

[entrylevel]

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."

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.

Re:Cheat code for even Sudoku??

[Anonymous Coward]

Bah, thats only for two player... Most /.ers play with themselves!

Re:Cheat code for even Sudoku??

[Drakonik]

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:Cheat code for even Sudoku??

[Drakonik]

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

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

[Firehed]

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.

Re:I Disagree and I Agree

[Anonymous Coward]

I've used nothing but pen in every math class I've ever taken.

Your kindergarten teacher must have been delighted when you brought ink swords to class.

Re:I Disagree and I Agree

[WK2]

Don't mod me down if you disagree. If you disagree, consider writing a retort instead.

You must be new here.

No, you must be new here. Referring to people modding you down by saying things such as "I have karma to burn" or "Mods, do your worst!" are sure-fire ways to get modded up. I don't know why it works, but it does.

On a barely related note, I never realized before that "you must be new here" meant "noob!".

Re:I Disagree and I Agree

[Nymz]

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:I Disagree and I Agree

[amorsen]

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:I Disagree and I Agree

[Yvanhoe]

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: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

Elegant methods

[SeanAhern]

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:Elegant methods

[thc4k]

What you do is minimizing a logical expression. Think of a sudoku as a list of expressions like "(field_1_is_1 or field_1_is_2 or field_1_is_3 or ... ) AND ( field_2_is_1 or .... ) /* every number can appear anywhere rule */
AND ( field_1_is 1 XOR field_2_is_1 XOR ... ) /* numbers are unique per 3x3 box */ AND ( ... */ numbers are unique per row */ ) AND ( field_43_is_9 AND field_14_is_7 AND ... ) /*here goes your starting set */

Now since we know that the whole thing has only one solution, this whole thing in 81*9 variables (9 for each number of the 81 fields) has to be equal to a expression like "(field_1_is_7 AND field_2_is_5 AND field_3_is_9 AND ... AND field_81_is_3)" which has only 9**2 variables and has a trivial solution (all True) and is the "solution" you seek. So, it's all just minimzing a logical expression, and that is where your "patterns" come from ... and as i've shown above, the solution itself is trivial, you just can't see it ;P

Re:Great

[Anonymous Coward]

I didn't have much luck using apt to handle dependencies either :(
slashdotter@momsbasement:~$ sudo apt-get install girlfriend
[sudo] password for slashdotter:
Reading package lists... Done
Building dependency tree
Reading state information... Done
Package girlfriend is not available, but is referred to by another package.
This may mean that the package is missing, has been obsoleted, or
is only available from another source
E: Package girlfriend has no installation candidate
slashdotter@momsbasement:~$

Re:Cheat code for even Sudoku??

[Anonymous Coward]

Whats the point of using cheat codes to solving Sudoku?

You and the knucklehead who modded you insightful have completely missed the point.

Brute force?

[gehrehmee]

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)

Proof Positive

[fabs64]

Let's seem yum do THAT!

I kid I kid.

Re:Proof Positive

[mabinogi]

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.

Re:Proof Positive

[Daniel]

I don't know any reason you couldn't try this out, but I don't know enough about the Yum equivalent of Packages files to generate one. Anyone who wants to create a yumsudoku.py is welcome to. :-)

Daniel

Re:Cheat code for even Sudoku??

[omeomi]

Also, if you're going to write a Sudoku puzzle generator, you have to write a Sudoku solver first. New puzzles are created by coming up with a random valid solved Sudoku puzzle, removing a bunch of numbers, checking to see if it's still solvable, and then removing some more...rinse, wash, repeat...

Software used for weird purposes?

[suck_burners_rice]

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.

Re:Software used for weird purposes?

[Antique Geekmeister]

There used to be 'emacs -e tower-of-hanoi'. I'm not sure if it got yanked from the source tarball, but it was an interesting way to show why old tape-based rotation schemes and levels of 'dump' backups worked the way they did.

Re:Software used for weird purposes?

[Smallpond]

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.

Re:Cheat code for even Sudoku??

[hedwards]

Hey now, there's a reason why they're called "joysticks."

Re:Cheat code for even Sudoku??

[hedwards]

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 one square without guessing.

Re:Cheat code for even Sudoku??

[omeomi]

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

Real Men use a Pen

[Nymz]

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:Cheat code for even Sudoku??

[FireFlie]

Interesting? Writing a SAT program to solve sudoku takes less than five minutes. This is not an interesting puzzle for a computer.

Make

[michaelmalak]

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

Re:Make

[Anonymous Coward]

I am unable to comprehend your post. Did you miss a tab somewhere grandpa? :P

~Ant-head

Dpkg in NP hard?!

[mdmkolbe]

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:Dpkg in NP hard?!

[Anonymous Coward]

Well.. yeah, but luckily it appears that aptitude can solve NP-hard problems in reasonble time. The downside is that all our crypto will be useless once NSA finds this out.

Re:Dpkg in NP hard?!

[dominious]

From TFA:

The game is played by filling in a 9-by-9 grid

From Wikipedia:

Although typical Sudoku puzzles (with 9-by-9 grid and 3-by-3 regions) can be solved quickly by computer, the generalization to larger grids is known to be NP-complete.

Re:Dpkg in NP hard?!

[Poromenos1]

Satisfying dependencies is...

Re:Dpkg in NP hard?!

[PatDev]

It's a bit of a nitpick, but solving sudoku is not NP complete - there are algorithms that solve Sudoku in O(1) time. It's easy if you consider that there are no variables in the problem. Now, I'll grant that the *generalization of sudoku-like games to arbitrarily sized boards* is NP-complete, but those are not Sudoku.

Re:Cheat code for even Sudoku??

[Anonymous Coward]

Sudoku is boring, like running, or tai chi. But, that's also why I like playing. It keeps one part of my brain engaged and exercising, and the remainder can wonder off into fantasy land, dreaming up the next page of code I want to write.

At least, that's why I like playing Sudoku. I also hate the puzzles that force you to guess; or, well, force you to guess more than 2 or 3 or 4 cycles out (depending on how many squares in each "cycle", which would be shared implicit constraints). I refuse to erase a square once I place a number, so if I can't keep track of a set of guesses in my head, it's a poor puzzle in my opinion.

Re:Cheat code for even Sudoku??

[AmberBlackCat]

I don't know if a cheat code could ever turn somebody on but, as a person who has actually played Life Force and Contra, I can say that getting it wrong can definitely make you seem monkey-like.

Re:Cheat code for even Sudoku??

[AmberBlackCat]

Just imagine what the average Sudoku player thinks about Slashdot.

stress testing apt-get

[AeiwiMaster]

Maybe this can be used to stress test the resolve-engine in apt-get, aptitude and synaptic.

Re:stress testing apt-get

[Anonymous Coward]

Which, if you read the guys blog, is exactly what he's doing

A little more can be said about that...

[hypomorph]

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.

Re:A little more can be said about that...

[Anonymous Coward]

applied logic in a formal system is essentially what mathematics is.

Aha, so that xkcd cartoon linked to in another reply needs to be extended to the right, since math is just applied logic!

But then... what is logic an application of?

Just permute a valid solution!

[Anonymous Coward]

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:Just permute a valid solution!

[Filip22012005]

This is only half the problem. You also need to know which numbers can be deleted to create the actual puzzle. Not all numbers can be deleted while keeping it solvable. It's of course quite possible to have a difficult and an easy sudoku based on the same solution.

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.

Comment removed

[account_deleted]

Comment removed based on user account deletion

Re:Cheat code for even Sudoku??

[dotancohen]

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:Cheat code for even Sudoku??

[Z00L00K]

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!

In any case: RPM can...

[Anonymous Coward]

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.

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.

Re:Cheat code for even Sudoku??

[DigitAl56K]

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

Time to plug myself

[gringer]

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

Re:Time to plug myself

[amorsen]

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:Time to plug myself

[apoc.famine]

That assumes they can randomize enough not to simply try the same solutions over and over. Even randomized starts might lead to a later state which is the same as a previously tried state. Depending on your algorithm, you might then solve it exactly the same way as previously, without finding another solution. Proving that your algorithm is able to find all possible solutions would probably be harder than writing the algorithm.

Re:Time to plug myself

[amorsen]

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:Time to plug myself

[Anonymous Coward]

the puzzle must only have one solution

This is not true at all! No where in any rules I've read, does it specify that a unique solution exists. In my mind, an empty 9x9 board would classify as a sudoku 'puzzle', albeit a rather boring one.

When solving puzzles I often use the uniqueness criteria ('if this square would be a 9, then there would be two solutions for this set of squares' etc), but I'm always afraid that it won't work out because there are meant to be two solutions.

Re:Cheat code for even Sudoku??

[cp.tar]

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.

Practice Makes Perfect

[Nymz]

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:Practice Makes Perfect

[WK2]

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?

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:Mod up P, GP and P=NP: choose two

[Tweenk]

In addition try running the moo action with increasing verbosity (e.g. aptitude -v moo, aptitude -vv moo etc.)

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

[Nevyn]

Emphasis added. Note that dpkg doesn't solve the dependency puzzle, but apt-get, aptitude and other package managers do

But they do it using the sudoku game based on dpkg data, the rpm game is different. So it's a fir title, IMO.

Re:Cheat code for even Sudoku??

[jacquesm]

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:Cheat code for even Sudoku??

[jacquesm]

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??

[TheLink]

I think you just encountered a failed slashdot bot/AI.

Maybe it was written in dpkg too.

Re:Cheat code for even Sudoku??

[Paradigm_Complex]

Jesus Christ. If you're going to be a game-code-nazi, get it right:

The [start] isn't part of the code, nor is the [select]. After the last [a] the code is entered, the code input is done. You can hit [select] multiple times after the code trying to decide between single player and co-op and it will still work.

Re:Cheat code for even Sudoku??

[dkf]

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:Cheat code for even Sudoku??

[seasunset]

I suppose nothing will beat Prolog with constraint logic programming to concisely solve Sudoku.

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]) :-
  Cs is ((U-1) mod 3)*3+1, Ce is Cs+2,
  Rs is ((U-1) // 3)*3+1, Re is Rs+2,
  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).

Sudoku Makes You Smarter

[Nymz]

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?

No comp scientists on /. ?

[thc4k]

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.

Re:No comp scientists on /. ?

[omuls are tasty]

The other way around, dammit! :)

NP completeness of Sudoku means that any instance of (for instance) the SAT problem can be converted to an instance of Sudoku (in polynomial time). Being able to convert Sudoku to SAT depends on SAT being NP-complete (provided that Sudoku is in NP).

Re:Cheat code for even Sudoku??

[Bozzio]

WRONG!

You inverted the A and B.

Yes! That's another geek card today. Only 2 more until my geek upgrade.

Re:Cheat code for even Sudoku??

[zippthorne]

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:Cheat code for even Sudoku??

[armareum]

I wrote a Sudoku Solver in VB two years ago. That code you posted? Well, it's a hell of a lost more concise than mine! :(

Re:Cheat code for even Sudoku??

[Anonymous Coward]

All of this reemphasizes that sudoku is interesting as a mathematical solving exercise but pretty dull and boring as a human puzzle amusement. Give me a good crossword puzzle any time. Computers only create bad ones; it takes a human to make, and solve, a clever one.

Re:Cheat code for even Sudoku??

[Anonymous Coward]

You never need to guess, you just need to expand the list of patterns that you recognize. Everyone starts out with two:

1) Only one cell in this row, column or square where this value can be placed.
2) Only one value can go in this cell.

There are about twenty more of increasing levels of complexity which apply in fewer situations and are harder to spot. Although its only 10 lines of code to solve a sudoku with brute force, it is possible and much more interesting to solve all but the most insanely difficult ones using only the patterns. The Y-wing for example:

AB - x
| .. |
BC - CA

Where the lines indicate cells that "see" each other. "A" can be eliminated from cell x.

Use only legal permutations!

[Anonymous Coward]

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

Re:Use only legal permutations!

[Annymouse Cowherd]

Swapping rows or columns and rotating the puzzle both keep it valid.

Re:Use only legal permutations!

[MrResistor]

Swapping rows or columns and rotating the puzzle both keep it valid.

Rotation would keep it valid, but swapping may not. My understanding of sudoku is that you are restricted by the box (sub-matrix?) also, not just the rows and columns.

In the sample sudoku posted above, if you swap columns 3 and 4 you will have an invalid puzzle since, for example, the upper left square will have two 1's and no 9's.

Re:Use only legal permutations!

[xouumalperxe]

You can also switch two columns within the same block column or two lines within the same block line legally as well, as both operations maintain line, column and block consistency.

DPKG is brutal logic

[Anonymous Coward]

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.

Re:DPKG is brutal logic

[Ash-Fox]

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.

Didn't happen here. But maybe that's because the package was created to handle this situation, since it had "provides" and "replaces" paramters in the package. for the older version in question.

Re:Cheat code for even Sudoku??

[Sancho]

Only one B A is required....
http://en.wikipedia.org/wiki/Konami_Code

Re:Cheat code for even Sudoku??

[Anonymous Coward]

Minion is a *much* better too for this than even Prolog.

Premature optimization

[mdmkolbe]

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

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.

Re:Cheat code for even Sudoku??

[dotancohen]

Only one B A is required....
http://en.wikipedia.org/wiki/Konami_Code

Not from my experience with Contra. Maybe in other Konami games, though.

Re:Cheat code for even Sudoku??

[ydrol]

I remember doing prolog at uni. It seemed extremely weird and difficult until gradually you have a Damascus/light-bulb moment(ie stop thinking procedurally) and then all the power is revealed.

Re:Cheat code for even Sudoku??

[Sancho]

You're simply incorrect. *shrug*

Re:Cheat code for even Sudoku??

[daveime]

Actually playing Suduko, you employ what some would call "cheats", but the rest of us call logical rules. So all the PC does is speed up the solving process as they can perform thousands of logical checks in a fraction of a second, as opposed to us wetware, who tend to go cross-eyed around 3am.

Interesting

[sepelester]

How many of you guys have actually done this?

Re:Cheat code for even Sudoku??

[gregorio]

I suppose nothing will beat Prolog with constraint logic programming to concisely solve Sudoku.

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 tailored ones, instead of just copy-pasting solutions of classic problems.

Sure, mapping is nice and stuff (and some people will like the fact that you used only a few criptic lines to do that), but it's just... mapping. The real fun and optimization resides on doing the algorithm yourself.

Re:Cheat code for even Sudoku??

[dotancohen]

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.

Monte Carlo Sudoku solving

[invisiblerhino]

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

RPM versus APT

[fm6]

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:

resolve(x)
  addtolist(x)
  dependsOn = dependsList(x)
  for each y in dependsOn
      resolve(y)
end resolve

Re:RPM versus APT

[John Hasler]

Cycles.

Re:RPM versus APT

[Nevyn]

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.

DPKG == RPM, APT/DPKG == APT/RPM == YUM == SMART == ZYPP.

Note that APT/RPM can't solve the rpm sudoku game. Worth noting is that the above pseudo-code is pretty close to high level way explanation of how YUM solves deps. (without --skip-broken).

Re:RPM versus APT

[Daniel]

Package dependency resolution is actually NP-complete. The main complication you missed is versioned dependencies -- you have to pick a collection of versions that are consistent with one another. For instance, if packages A, B, and C have versions 1 and 2 each, with

    A (v1) Depends: B (v1), C (v2)
    A (v2) Depends: B (v2), C (v2)
    B (v1) Depends: C (v2)
    B (v2) Depends: C (v1)

you need to recognize that the only consistent installation is Av1, Bv1, and Cv2. This example is trivial, but multiply it by about a factor of 10,000 and you get Debian. :-)

Daniel

Re:RPM versus APT

[fm6]

B (v1) Depends: C (v2)
B (v2) Depends: C (v1)

You have a later version of B depending on an earlier version of C! How often does that happen?

Re:RPM versus APT

[Daniel]

B (v1) Depends: C (v2)
B (v2) Depends: C (v1)

You have a later version of B depending on an earlier version of C! How often does that happen?

Not often. I was coming up with a simple and contrived example off the top of my head late at night, and it doesn't look much like what happens in real archives. But, of course, the choices of Cv1 and Cv2 are arbitrary; you could swap them and have the same situation:

A (v1) Depends: B (v1), C (v1)
A (v2) Depends: B (v2), C (v1)
B (v1) Depends: C (v1)
B (v2) Depends: C (v2)

The point is that you have to backtrack to solve this (unless you happen to pick a satisfying solution with your first choice of version for each package), which your pseudocode doesn't do. Even that isn't enough, though:

A (v1) Depends: B (v1), C (v1)
A (v2) Depends: B (v1), C (v1)
B (v1) Depends: C (v1)
B (v2) Depends: C (v2)

If the user asks to install B v2, you have to consider removing A to install it (because Bv2 requires Cv2, and all versions of A need Cv1). Note that the simple approach of walking through the dependencies of B and trying each one won't help here, because it's not a dependency of B that's broken. You need to look at the reverse dependencies of C too, and in a larger archive A might have reverse dependencies that also need to be taken care of once it's removed.

I've written a little bit about some of these issues at http://people.debian.org/~dburrows/model.pdf. You can find a lot of this in a basic AI textbook or in the theory behind constraint solving algorithms too, though; that link just applies some standard techniques to the problem of dependency resolution.

Daniel

Re:RPM versus APT

[fm6]

Thanks. You've answered my question quite clearly and concisely. Your examples are at the upper end of my CS comprehension skills, though; I certainly don't have it in me to follow up with the readings you suggest.

So now I have a new question: how do RPM-based distros manage without this feature.

Re:RPM versus APT

[Daniel]

So now I have a new question: how do RPM-based distros manage without this feature.

I don't use RPM distributions, so I can't answer that question. In Debian, we've gotten along fine for a long time without a complete resolver [0] (the resolvers most users use are still incomplete) because the problem is so easy. The situations users usually run into can be solved with a greedy algorithm like your initial suggestion; with a few extra heuristics you can cover many other typical scenarios (such as the one I posted above). When users hit a situation that it can't solve, they either add instructions to force a resolution, or they ask for help on a mailing list and someone tells them how to add instructions that force a resolution. :-) I presume that users of RPM distributions do something similar.

The main impetus behind the aptitude resolver was that I wanted to improve the UI by providing user-visible explanations for the resolver's decisions and by allowing users to interactively guide the resolver towards a solution (for instance, by telling it that they don't want it to install a particular package version). I also wanted to add support for installing versions other than the current "candidate" [1]. That I could make it complete at the same time was the icing on the cake. (but some very useful icing for people who have complicated dependency situations!)

Daniel

[0] "complete" here means "able to find any solution to a dependency problem". Actually, aptitude only guarantees that it will find minimal solutions, but that's what you want (if "install A" solves a dependency problem, it's possible that "install A and install B" also does; aptitude might return both of these or only the smaller one -- ideally it would only ever return the smaller one, but I wasn't able to find a technique that would quickly minimize solutions).

[1] An apt term: the candidate version of a package is the version that apt will select to install if it's told to install that package. If versions 1, 2, and 3 of A are available and 2 is the candidate, apt-get install A will install version 2. The standard dependency resolver can't handle situations where a version other than the candidate is needed to resolve a dependency.

Re:Cheat code for even Sudoku??

[silent_artichoke]

Sounds fun!

Solve this Sudoku before the time runs out or your partitions will be randomly reassigned to different mount points.

Re:Cheat code for even Sudoku??

[Anonymous Coward]

Damn PKers.

Genetic Algorithm, just a little off topic...

[Uipe]

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

HEY! you should declare your intentions for a pun!

[ryzvonusef]

...to readapt Debian's... hehe! "re-adapt", get it? ;-)

Re:Cheat code for even Sudoku??

[rant64]

Yes! That's another geek card today. Only 2 more until my geek upgrade

A frontal lobe?

Next...

[Anonymous Coward]

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

Re:Cheat code for even Sudoku??

[IntergalacticWalrus]

He would've been right for TMNT3 though.

Re:Cheat code for even Sudoku??

[Anonymous Coward]

Two points:

Writing an algorithm is "mapping". You are a good programmer when you do this automatically, at least for simple domains. If you're struggling, you need to take another look at the "real" problem, since you are missing something.

Sudoku is a constraint-based arithmetic game. Constraint-based programming is the natural way to solve the problem. (though functional programming might not be a terrible approach -- resolution is "just" beta reduction on truth functions) This is what you were missing.