sudoku

[meganursula]

I go through periods of being taken by sudoku. It is unfortunate, then, that i have a sudoku program on my computer at work. I have worked through 50 sudoku puzzles in this program in the last year or so. I have noticed that a large number of them eventually come down to me having to guess a solution, and then test it to see if it is correct. (A few even seem to have two correct solutions - symmetry is a bitch.) This really bugs me. I also do sudoku in the newspaper, and out of a book that i have, and i don't run into this problem anywhere else.

The thing that really irritates me is that it is possible to 'guess' wrong - in other words, there is a solution to these puzzles, but i can't figure out how to get at it from a logical standpoint. (Well, i suppose guessing and then proving that guess to be wrong is sort of logical, but i'd rather figure out how to eliminate the wrong answer up front.)

An example of such a puzzle is:

_9_ 762 314
637 154 982
4__ __9 675

_59 618 4_7
_46 927 15_
17_ 543 _96

_83 495 _61
9__ _76 _4_
_64 __1 __9

At this point, if i guess 5 in the upper right corner, i can fill in the rest with a correct solution. If i guess 8 in the upper right corner, i run into an eventual contradiction.

Does anyone know what i'm missing that might allow me to eliminate the incorrect solution?

Comments

[sinthrex.livejournal.com]

Almost precisely this has always made me disinterested in Sudoku.

[safetybitch.livejournal.com]

You might try asking our father, who also happens to be obsessed with sudoku and was in the habit of doing all the puzzles in the NY Times. Personally, it's the one game I have on my PDA, and I use it to fall asleep. I occasionally get the very hard ones, but I have to admit that I sometimes just give up and move on to the next puzzle.

[katybeth]

First of all, find a program that doesn't produce boards with two correct solutions. :-P In my opinion, a properly written sudoku puzzle should have a unique solution.

As far as puzzles with a unique solution but requiring guessing, I agree with you. I prefer to solve sudoku puzzles without having to hypothesize and backtrack. It is still logical, but it does seem like there should be a way to do it without. I usually give up at the point I have to guess, but I can solve most puzzles.

I also prefer solving on paper, where I can use whatever notation I want.

For this puzzle, I haven't found a way yet. I'm working on it. I thought I had an idea, but it didn't work out.

[blk]

I have only once come across a Sudoku puzzle that made me guess, although now I guess it's twice. I suspect it depends on the started assumed rules of the computer program that generates the puzzles, and the puzzles my phone generates don't allow that. I've never come across one with two solutions, and I would probably ditch any program that gave one to me, in disgust. :)

On puzzles I get truly stuck on, I've used Sudoku Solver to verify that I've gotten as far as I could on logic alone. I did your puzzle by hand, then entered your puzzle in there and it got as far as I did, then told me the next step required guessing.

I'd recommend you find a new program. :-/

[meerkat299.livejournal.com]

There is no way of solving that puzzle without using trial-and-error.

I do a lot of Sudoku using a freeware program called Simple Sudoku (http://www.angusj.com/sudoku/). It randomly generates puzzles of five difficulties and each always has a unique solution. You can also use it to solve puzzles and have it give a hint — the next step toward a solution. This program the above puzzle requires a technique it calls "colors" which is just a fancy name for trial-and-error.

[mh75.livejournal.com]

The 'colors' described by the website below this comment is probably what that means - i think its a step up from pure trial and error because it isolates where the contradiction is.

Nice, because i could do that with my trials, but, didn't see how to generate the contradiction directly. The colors technique does that.

[katybeth]

There is no way of solving that puzzle without using trial-and-error.

How do you come to that conclusion? I mean, not so much for this puzzle, but in the general case?
How do I know when I need to resort to trial and error, and that I haven't just overlooked something?

[meerkat299.livejournal.com]

The only way I am aware of it process-of-elimination: no other technique is applicable.

[katybeth]

Hmph. That only works if I know all possible techniques.

[meerkat299.livejournal.com]

http://www.angusj.com/sudoku/hints.php has a okay primer for Sudoku techniques.

[jedusor.livejournal.com]

My friend Tyler, who is one of those insanely brilliant puzzle-solving machines, says:

I recommend http://www.scanraid.com/sudoku.htm. Putting in what you have and seeing how that works it out can teach a few new techniques. Without actually analyzing the puzzles but noting the amount solved, XY-Wings or Unique Rectangles could be useful.

[mh75.livejournal.com]

Heh. Thats a nice site.

[msde.livejournal.com]

If you look at rows 4 through 7, columns 1-3 and 7 only:

_59 618 4_7
_46 927 15_
17_ 543 _96

_83 495 _61

and blow it up to only include the possible values you get

23?  5   9     4 
38?  4   6     1 
 1   7  28?   28?

27?  8   3    27?

you can see there's a contradiction in the 28? and the 27? in the 7th column if you set try to set the 28? on the left to 8.

[mh75.livejournal.com]

which, i think, with my cursory late night perusal, is doing the same thing as the color chain discussed above.

[msde.livejournal.com]

You guys have names for these things? I just like sudoku but I haven't had spare time for two jobs. :D

[bhudson.livejournal.com]

Sudoku is NP-complete (my colleague blogged (http://weblog.fortnow.com/2005/05/complexity-and-sudoku.html) a brief literature search about this some time ago). So if you have a fast algorithm that doesn't boil down to backtracking or trying all solutions in some way, email me.

[mh75.livejournal.com]

you might be interested in jedusor's website recommendation.

[bhudson.livejournal.com]

Actually, not really -- I find sudoku unbearably dull :)

But indeed, heuristics help reduce most cases you'll see.

[mh75.livejournal.com]

Well, you can see how they solve the sudoku, which seems like it could bee algorithm-ed. I do not know what the complexity would be like.