# Solving Sudoku With dpkg

#### timothy posted more than 5 years ago | from the after-all-it's-there dept.

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.

## Cheat code for even Sudoku?? (-1, Offtopic)

## ilovesymbian (1341639) | more than 5 years ago | (#24723555)

Whats the point of using cheat codes to solving Sudoku? Doesn't anyone play a game for just the plain fun of it?

## Re:Cheat code for even Sudoku?? (5, Funny)

## pizzach (1011925) | more than 5 years ago | (#24723579)

## Re:Cheat code for even Sudoku?? (4, Funny)

## Anonymous Coward | more than 5 years ago | (#24723597)

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?? (4, Funny)

## Anonymous Coward | more than 5 years ago | (#24723713)

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?? (5, Informative)

## Anonymous Coward | more than 5 years ago | (#24723609)

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?? (1, Funny)

## Anonymous Coward | more than 5 years ago | (#24723751)

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

## Re:Cheat code for even Sudoku?? (2, Funny)

## hedwards (940851) | more than 5 years ago | (#24723971)

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

## Re:Cheat code for even Sudoku?? (3, Informative)

## DMUTPeregrine (612791) | more than 5 years ago | (#24724717)

Up-Up-Down-Down-Left-Right-Left-Right-A-B-(Start) is single player contra.

## Re:Cheat code for even Sudoku?? (0, Redundant)

## Paradigm_Complex (968558) | more than 5 years ago | (#24725145)

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?? (1)

## AmberBlackCat (829689) | more than 5 years ago | (#24724299)

## Re:Cheat code for even Sudoku?? (1)

## dotancohen (1015143) | more than 5 years ago | (#24724515)

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?? (5, Insightful)

## jlarocco (851450) | more than 5 years ago | (#24723677)

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?? (4, Insightful)

## Drakonik (1193977) | more than 5 years ago | (#24723765)

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

## Re:Cheat code for even Sudoku?? (2, Interesting)

## Z00L00K (682162) | more than 5 years ago | (#24724619)

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?? (2, Interesting)

## omeomi (675045) | more than 5 years ago | (#24723933)

## Re:Cheat code for even Sudoku?? (1)

## hedwards (940851) | more than 5 years ago | (#24723981)

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?? (3, Insightful)

## omeomi (675045) | more than 5 years ago | (#24724007)

It's probably less costly totake a square away at a time and check to see if it's still solvablethan 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

solvedpuzzle, then start removing squares...## Just permute a valid solution! (3, Interesting)

## Anonymous Coward | more than 5 years ago | (#24724441)

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! (1)

## Filip22012005 (852281) | more than 5 years ago | (#24724815)

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

## DigitAl56K (805623) | more than 5 years ago | (#24724727)

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:Cheat code for even Sudoku?? (0, Offtopic)

## TheLink (130905) | more than 5 years ago | (#24725009)

Maybe it was written in dpkg too.

## Re:Cheat code for even Sudoku?? (2, Interesting)

## FireFlie (850716) | more than 5 years ago | (#24724021)

## Re:Cheat code for even Sudoku?? (0)

## Anonymous Coward | more than 5 years ago | (#24724189)

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?? (2, Interesting)

## jacquesm (154384) | more than 5 years ago | (#24724977)

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?? (1)

## AmberBlackCat (829689) | more than 5 years ago | (#24724305)

## Re:Cheat code for even Sudoku?? (1)

## dkf (304284) | more than 5 years ago | (#24725189)

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

everpersistently interesting; if you're bored, do something more difficult and stop wasting both time and braincells.## Re:Cheat code for even Sudoku?? (1)

## FooAtWFU (699187) | more than 5 years ago | (#24723691)

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

## Re:Cheat code for even Sudoku?? (4, Informative)

## _xeno_ (155264) | more than 5 years ago | (#24723727)

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

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

aptis 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 theaptdependency resolver.## Re:Cheat code for even Sudoku?? (1)

## cp.tar (871488) | more than 5 years ago | (#24724901)

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

## jacquesm (154384) | more than 5 years ago | (#24724989)

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?? (5, Insightful)

## Drakonik (1193977) | more than 5 years ago | (#24723759)

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?? (0)

## Anonymous Coward | more than 5 years ago | (#24723849)

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

## Uh-oh (2, Funny)

## Yvan256 (722131) | more than 5 years ago | (#24723565)

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 (1)

## Koiu Lpoi (632570) | more than 5 years ago | (#24723819)

## Re:Uh-oh (1)

## Al Dimond (792444) | more than 5 years ago | (#24723975)

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 (3, Interesting)

## Koiu Lpoi (632570) | more than 5 years ago | (#24724017)

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 (1)

## Daengbo (523424) | more than 5 years ago | (#24724545)

cancount 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 (1)

## Hal_Porter (817932) | more than 5 years ago | (#24724191)

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 (1)

## speilberg0 (1144645) | more than 5 years ago | (#24724735)

## Well, it's ultimately a logic puzzle. (5, Insightful)

## Shag (3737) | more than 5 years ago | (#24723585)

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

## Anonymous Coward | more than 5 years ago | (#24723637)

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. (2, Insightful)

## WiseWeasel (92224) | more than 5 years ago | (#24724115)

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

## Splitting Hairs (2, Interesting)

## Nymz (905908) | more than 5 years ago | (#24723701)

## Re:Splitting Hairs (1, Insightful)

## WK2 (1072560) | more than 5 years ago | (#24723725)

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.

## I Disagree and I Agree (5, Informative)

## Nymz (905908) | more than 5 years ago | (#24723775)

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

## Firehed (942385) | more than 5 years ago | (#24723931)

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 (1)

## Nymz (905908) | more than 5 years ago | (#24724011)

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

## Anonymous Coward | more than 5 years ago | (#24724323)

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 (2, Insightful)

## arctanx (1187415) | more than 5 years ago | (#24724457)

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

## Re:I Disagree and I Agree (1)

## amorsen (7485) | more than 5 years ago | (#24724999)

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 (0, Offtopic)

## WK2 (1072560) | more than 5 years ago | (#24724549)

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 (1)

## Nymz (905908) | more than 5 years ago | (#24724627)

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 (0)

## Anonymous Coward | more than 5 years ago | (#24723779)

## Re:Splitting Hairs (5, Interesting)

## whatnotever (116284) | more than 5 years ago | (#24723797)

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 (1)

## WK2 (1072560) | more than 5 years ago | (#24724531)

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 (1)

## demallien2 (991621) | more than 5 years ago | (#24724817)

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.

## Practice Makes Perfect (2, Insightful)

## Nymz (905908) | more than 5 years ago | (#24724921)

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,

bubble. :-)

--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## Re:Practice Makes Perfect (1)

## WK2 (1072560) | more than 5 years ago | (#24725327)

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?

## Re:Splitting Hairs (1)

## adamofgreyskull (640712) | more than 5 years ago | (#24725265)

notthe kind I believe you alluded to in your first post, requires no thought at all, this much is true.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:

Ok, so you apply your simplistic "brute-force" strategy to a Sudoku puzzle and you reach the final square, and you've filled in

nosquares 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. [scanraid.com]## Re:Splitting Hairs (1)

## Daengbo (523424) | more than 5 years ago | (#24724573)

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 (2, Insightful)

## jonaskoelker (922170) | more than 5 years ago | (#24724893)

However, I do not believe that the grandparent is correct in stating that these methods solve sudokus in a fraction of the time of the brute force method if you allow for [...]

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

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

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

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

## Elegant methods (4, Insightful)

## SeanAhern (25764) | more than 5 years ago | (#24723811)

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:Splitting Hairs (3, Informative)

## maxume (22995) | more than 5 years ago | (#24723845)

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

## uofitorn (804157) | more than 5 years ago | (#24724005)

"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 brainssolve 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 (1)

## Zosden (1303873) | more than 5 years ago | (#24724215)

## Re:Splitting Hairs (1)

## amorsen (7485) | more than 5 years ago | (#24725019)

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 (1)

## uofitorn (804157) | more than 5 years ago | (#24725081)

## Brute force? (2, Insightful)

## gehrehmee (16338) | more than 5 years ago | (#24723877)

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)

## Re:Well, it's ultimately a logic puzzle. (1)

## amaupin (721551) | more than 5 years ago | (#24723707)

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

## Re:Well, it's ultimately a logic puzzle. (0)

## Anonymous Coward | more than 5 years ago | (#24723763)

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. (3, Informative)

## tukang (1209392) | more than 5 years ago | (#24723891)

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

## Shag (3737) | more than 5 years ago | (#24724187)

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. (4, Insightful)

## azgard (461476) | more than 5 years ago | (#24724421)

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

## Re:Well, it's ultimately a logic puzzle. (1)

## jonaskoelker (922170) | more than 5 years ago | (#24724839)

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

## tukang (1209392) | more than 5 years ago | (#24724959)

Could you please express sudoku as a set theoretic problem?

It can be expressed as a set cover [wikipedia.org] problem

## Re:Well, it's ultimately a logic puzzle. (1)

## EvanED (569694) | more than 5 years ago | (#24724165)

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

## Shag (3737) | more than 5 years ago | (#24724395)

Dunno, having used package management tools on several unix flavors, ;)

andhaving resolved dependencies manually on systems where such tools hadn't yet evolved, I have a lot of respect for their logic capabilities.## A little more can be said about that... (1)

## hypomorph (1305401) | more than 5 years ago | (#24724419)

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

## Anonymous Coward | more than 5 years ago | (#24724513)

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?

## Re:Well, it's ultimately a logic puzzle. (1)

## jonaskoelker (922170) | more than 5 years ago | (#24724793)

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

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

## ATTENTION SHOPPERS! (-1, Offtopic)

## Anonymous Coward | more than 5 years ago | (#24723601)

ATTENTION SHOPPERS: PAY NO ATTENTION TO THE NECROTIC DOG PENIS. I REPEAT, PAY NO ATTENTION TO THE NECROTIC DOG PENIS CURRENTLY LOOMING OUTSIDE LOT 4. CONTINUE SHOPPING BUT PLEASE ENSURE YOU LEAVE VIA AN ALTERNATIVE EXIT AS WE ARE NO LONGER ABLE TO GUARANTEE YOUR SAFETY IN LOT 4, DUE TO THE NECROTIC DOG PENIS. FOR YOUR INFORMATION, LOTS 1, 2, 3, 5 AND 6 ARE CURRENTLY FREE OF BAYING NECROTIC DOG PENIS. PAY NO ATTENTION TO THE NECROTIC DOG PENIS. THANK YOU.

NECROTIC DOG PENIS: YOU THOUGHT IT WAS GONE, BUT IT'S BACK!

Lameness filter encountered. Post aborted! Lameness filter encountered. Post aborted! Lameness filter encountered. Post aborted! Lameness filter encountered. Post aborted! Lameness filter encountered. Post aborted! Lameness filter encountered. Post aborted! Lameness filter = censorship, lameness filter = censorship, lameness filter = censorship, lameness filter = censorship, lameness filter = censorship, lameness filter = censorship.

Your comment violated the "postercomment" compression filter. Try less whitespace and/or less repetition.

## Re:ATTENTION SHOPPERS! (-1)

## Anonymous Coward | more than 5 years ago | (#24723715)

## Great (-1, Troll)

## sleeponthemic (1253494) | more than 5 years ago | (#24723605)

Now solve my dependency:

dpkg --build girlfriend

At least have it answer with some saucy ascii for christ sakes

## Re:Great (-1, Troll)

## Anonymous Coward | more than 5 years ago | (#24723633)

Oh, I see your problem. You want to build a co-dependency, which dpkg can't handle.

Try to manually build

relationfirst, making several passes.## Re:Great (0)

## Anonymous Coward | more than 5 years ago | (#24723847)

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:Great (-1, Troll)

## Anonymous Coward | more than 5 years ago | (#24723641)

dpkg --build girlfriend

This [imdb.com] might help you.

## Aptitude rather than Dpkg (3, Informative)

## Asuranceturix (1265166) | more than 5 years ago | (#24723717)

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

## Re:Aptitude rather than Dpkg (2)

## entrylevel (559061) | more than 5 years ago | (#24723967)

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

## In any case: RPM can... (0)

## Anonymous Coward | more than 5 years ago | (#24724645)

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.

## Mod up P, GP and P=NP: choose two (2, Informative)

## jonaskoelker (922170) | more than 5 years ago | (#24724949)

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

## Proof Positive (2, Funny)

## fabs64 (657132) | more than 5 years ago | (#24723901)

I kid I kid.

## Re:Proof Positive (2, Funny)

## mabinogi (74033) | more than 5 years ago | (#24724261)

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? (4, Insightful)

## suck_burners_rice (1258684) | more than 5 years ago | (#24723951)

## Make (4, Funny)

## michaelmalak (91262) | more than 5 years ago | (#24724139)

## Dpkg in NP hard?! (2, Insightful)

## mdmkolbe (944892) | more than 5 years ago | (#24724147)

Since Sudoku is NP complete, doesn't this mean Dpkg is NP complete?!

Oh, the humanity! I'm just waiting for an evil set of dependencies to crop up that makes it go exponential.

## Re:Dpkg in NP hard?! (1, Funny)

## Anonymous Coward | more than 5 years ago | (#24724741)

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?! (1)

## dominious (1077089) | more than 5 years ago | (#24725087)

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.

## stress testing apt-get (1)

## AeiwiMaster (20560) | more than 5 years ago | (#24724339)

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

## Time to plug myself (2, Interesting)

## gringer (252588) | more than 5 years ago | (#24724779)

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

## amorsen (7485) | more than 5 years ago | (#24725037)

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.