An Educated Guess

I was talking about Sudoku with my dad and my brother the other day over lunch, when we got into an unexpected argument. I had been considering how a computer might go about solving a Sudoku. I talked about how it could test many possibilities near-instantly; it could look at a square and think, "Could a 1 go here? Well, this would lead to that, and then we'd have a conflict. So, no, it can't be a 1." And my brother objected. "That's just guessing," he said. I was certain, however, that this was how people solved the puzzles, too. What my family was calling "logic, not guessing" was no more than mental guess-and-check. I set out to demonstrate it.

At first, you might instinctively side with the naysayers. If you walked by a person who was working on a Sudoku, and he said aloud, "Gee, I dunno. Let's put a 6 here and see what happens," you would say he's "just guessing." I would tend to agree. But what does the "logical" person do that's so different? Not much, I argue.

Take, as our example, the above puzzle. We're simply interested in solving for the top-left square, the one selected in pink. Can you determine the number (1-9) which belongs here?

Such an exercise is fairly easy. Looking down the left-most column, we see that the numbers 2-8 are present, meaning that 1 and 9 must fill the remaining gaps in the column. Thus, we have two possibilities: (A) That 1 goes in the pink box, or (B) that 9 goes in the pink box.

(A) If we put 1 in the pink box, we must put 9 in the remaining gap in the column. This gives us the following:

Now we have a problem. There are two 9's in the bottom-left nonant (quadrant, but for 9 pieces?), which violates one of the three pillars of Sudoku: no repeated values in rows, columns, or 3x3 squares. Thus, this is not the solution. That leaves us with:

(B) We put a 9 in the box. Note that when we put a 1 in the remaining space, this does not bother the 9 in that nonant:

Now, many readers will argue that they can do this in their heads. In other words, they look at the original puzzle:

And think, "A 1 cannot go there." But to think this, one must, perhaps without realizing it, play out some possibilities in his mind. It's all well and good to do so mentally, to figure that if such-and-such, something-or-other will result. That's certainly logical. But it kind of sounds like guess-and-check, doesn't it?

Well, that's all logic is. We might not like to think so, but it's true. You don't magically "see" the solution in a Sudoku problem; you think ahead. You think, "If this is here, then some possibilities I had been considering cannot be true." And you go on eliminating possibilities, or guesses, until there is only one left. And when there's one possibility left, it isn't a guess anymore; it's a fact!

Now, we like to do that fast. We like to perform our simulations so fast that we don't even think about it, so fast that we seem to just look and know. If one player was solving a Sudoku and came to a part where she said, "This box must either be a 3 or a 6," and then proceeded to just pick one, we don't give her very much credit when the puzzle just-so-happens to solve correctly. But a similar player looks at the puzzle and reckons, "This must either be a 3 or a 6, but I know that this is here, and that is there, and this will go there or there, and so, considering a few moves away, I can tell how a 3 would mess something up. Thus, it is a 6!" Such a player is complimented for being able to see how things came together.

Yet both players will effectively perform the same operations, one on paper, and one in her head. They will consider the possibility of a move, examine its implications, and determine its worth based upon those implications. On paper, that's a guess. In the mind, that's local thinking.

So suppose we have a computer program, and we want it to solve a Sudoku puzzle. And suppose, further, that we allow it to guess. We allow it to put a 1 in the box, without telling anyone. We allow it to see what happens, and realize its mistake. We allow it to try again, with a 9. And only when it has the answer does it bother to reveal it. Is such a program solving by guess-and-check?

Yes.

But guess what? So do we.