Stumped in Sudoku

February 28, 2005 9:54 PM

I'm having a lot of trouble finding a logical solution to a Sudoku problem.

The problem was published in The Times on 18 February 2005 with a rating of "fiendish". I have an Excel spreadsheet that solves Sudoku puzzles by brute force, and it confirms that the puzzle can be solved (albeit with a "very hard" rating of 8).

The puzzle is crudely reproduced below. Bold numbers are the original starting numbers; the rest are numbers I've solved. The Excel Sudoku solver confirms that the numbers I've placed thus far are in their proper positions.

I've reached the stage where I cannot logically deduce the positions of any other numbers. I've never had to guess to solve a Sudoku puzzle before - with a little thought, I can state with certainty that a particular number can only be placed in a particular position, and that therefore this number goes here, and that number goes there, and so on til the grid is solved. The Times claims that their Sudoku puzzles are constructed so that guessing is never required.

I'm not looking for a solution to the puzzle - I know what it is already. I'm hoping that somebody can say something like "well, given that C5 is a '3', and given that G6 is a '9', it follows that D1 must be a ..., because ...". Just one number to get me going would be lovely. A new solving technique I hadn't thought of would be brilliant.

For those not in the know, the challenge is to place numbers in the grid such that each row, each column and each 3x3 square contains the numbers 1 to 9.


_ 1 _ | _ 6 _ | _ _ _
5 8 9 | 7 3 4 | 6 2 1
_ _ 6 | 1 _ _ | _ _ _
__________________
8 9 7 | _ 1 6 | _ _ _
_ _ 3 | 8 4 7 | 9 1 _
_ _ _ | _ _ 3 | 8 7 6
__________________
_ _ _ | _ 7 9 | 1 6 _
_ 3 _ | 6 2 5 | 4 _ 7
_ _ _ | _ 8 1 | _ 5 _
__________________

posted by obiwanwasabi to Sports, Hobbies, & Recreation (13 answers total)

this algorithm description implies that it may sometimes be necessary to guess: http://www.di-mgt.com.au/sudoku.html
posted by juv3nal at 10:39 PM on February 28, 2005

so, thanks to your post I just spent an hour doing this puzzle. I didn't have to guess.
posted by mai at 11:35 PM on February 28, 2005

My process was just to play process of elimination a million times over. I kept track of all the possibilities for each square by writing them very small in the corner of the square. I suggest starting with rows that are more filled in.
posted by mai at 11:38 PM on February 28, 2005

maybe that is really bad obvious advice. if you want more hints just ask.
posted by mai at 11:39 PM on February 28, 2005

sometimes the way this reduces to a direct logical deduction is pretty complicated, I think.
posted by mai at 11:39 PM on February 28, 2005

mai -- if you're keeping track of all the possibilities and seeing which ones work and which ones do not, isn't that just the same strategy as guessing?
posted by evinrude at 12:53 AM on March 1, 2005

Best answer: For me, the breakthrough was noting that in the bottom left 3x3 matrix, the numbers 6 & 7 were both limited to one of the same two squares (the bottom left and bottom center). This meant that, even though I didn't know which was which, those two squares were taken. As a result of that, the 9 in that matrix had to be directly to the left of the 3, the 1 had to be directly to the right of the 3, etc. After that, it became a simple matter of looking for forced digits.

On preview: I was thinking just what evinrude was thinking.
posted by boaz at 12:57 AM on March 1, 2005

I don't think it is exactly the same - it is not that I guess and then see whether it works out. For example, the rightmost square in the middle row can be a two or a five given the info in the puzzle. Once you rack up enough info like this, it starts to become clear.

In practice, my process turns out to be like boaz's.

Philisophically speaking, I don't exactly know what the difference is between guessing and keeping track of multiple possible strategies and narrowing them down. It seems like it is just a distinction between linear and non-linear thinking or something. I'm too tired to figure this one out.
posted by mai at 1:52 AM on March 1, 2005

Incidentally, the kind of guessing that takes place isn't in any case the same kind as in, say, minesweeper, because here you have enough information to solve the puzzle. So maybe what I did is guessing.
posted by mai at 1:55 AM on March 1, 2005

Response by poster: evinrude - I know what mai's talking about. If a puzzle has me really stuck, I sometimes have to resort to writing all the possible answers for a given row, column or 3x3 then look for a number that only appears once. Occasionally, there'll turn out to be only one possibility that isn't immediately apparent. This technique failed for this puzzle, because all of the vacant squares can have more than one option, and no single number appears only once in a given row, column or 3x3.

As mai says, it can get a little more abstract. For example, I might know that a particular 3x3 needs a 7. While I might have a couple of squares to choose from, if they're all in a particular column or row then I can eliminate 7 as a choice for all of the squares in that column or row. Sometimes that's enough to reduce the number of choices for one of those squares to just one number. It's not guessing if it works out this way - just deduction through elimination. Guessing is saying "it could be a 2 or a 5 - I'll put 5 for now and see if it pans out".

The '4' in the bottom-right 3x3 was placed using mai's technique. There are no '4's in the 3x3s above or to the left, so you can't place the bottom-right 4 that way. However, in the row and column that intersect that square there is already a 1, 2, 3, 5, 6, 7, and 9, so it could only be a 4. Unfortunately, that 4 doesn't narrow the choices for any other 3x3s. The same technique let boaz know that the two bottom-left squares could only be a 6 or a 7 - he eliminated all other choices.

juv3nal - The Times insists that it constructs its puzzles in a way that ensures they can be solved logically, probably using this method. They claim that at any given stage there is always a clue that points to the next placement.

boaz wins. This is a new technique for me. As I wrote above, I've tried to reduce squares to a single possibility. However, if you know that two squares are either one number or another, you can eliminate all other choices from those squares, reducing the total choices for row, column or 3x3. In this case, getting rid of the 9 in the bottom-left square left just one other place for a 9 in the 3x3:

- the bottom-left square could be a 2, 4, 6, 7 or 9;
- the bottle-middle square could be a 2, 4, 6 or 7;
- no other squares in that 3x3 could be a 6 or a 7;
- therefore, assume that those squares are either a 6 or a 7;
- this eliminates the possibility of a 9 from the bottom-left square, leaving the middle-left square as the only other square in the 3x3 with a 9 as an option;
- fill in the 9; this leaves only one place in the 3x3 that could be a 1 (middle-right)
- et cetera, et cetera.

Thanks all!
posted by obiwanwasabi at 1:55 AM on March 1, 2005

This is interesting to me because I wasn't distinguishing, in my head, between boaz's technique and any other technique. I was just brute forcing the whole thing.
posted by mai at 2:00 AM on March 1, 2005

I love these things. Generally follow the same methods as boaz. Interestingly todays Times has a good article on steps to take to solve these.
posted by lloyder at 6:11 AM on March 1, 2005

Whoa. I think we need puzzles.metafilter.com. That'd be awesome! I've got some tricks I learned on bar napkins I could share.
posted by Mo Nickels at 7:10 AM on March 1, 2005