Prove Sodoku does not require a guess.

[Diffy]

I am not a big Sodoku player. But I was having a conversation with a friend, about the game. My friend mentioned that in some of the very hard Sodoku puzzles you are forced to guess.

We got into a disagreement. I say that all Sodoku puzzles can be solved by logic. My friend says otherwise.

I was thinking of a way I can prove to my friends that I am right. I hope I am, but maybe not.

After thinking about it for a few hours I came up with an argument. I'd like to know what others think, and if I am right or wrong. Basically I need input. Or if there is a better way to say what I am trying to below.

Here is what I currently think:

Suppose there is a Sodoku puzzle where you have to guess. If you work out the rest of the missing numbers through logic eventually you will figure out if your guess was correct or not. But by doing so you have logically concluded the correct number for the square, implying a guess was not needed.

Say you have to guess with only 2 squares left, then the puzzle is not unique and thus not a Sodoku puzzle.

 

[Stephen Tashi]

I say that all Sodoku puzzles can be solved by logic. My friend says otherwise.

You (and your friend) haven't defined what you mean when you say "by logic". Many mathematical proofs involve considering all possible cases and showing that some of the cases considered are actually impossible. From one point of view, such a "logical" proof could be considered as making guesses and working out the consequences of each guess.

 

[mfb]

Good (and most) Sudoku puzzles have a unique solution. This implies that they can be solved without guessing - but the required chain of reasoning might be extremely long.
If there are multiple solutions, you have to choose one, you could call that "guessing".

 

[Bacle2]

Maybe you mean that there may or not be enough information (i.e., non-empty

squares) for the solution to be unique? An extreme case would be one with an

empty set. This setup clearly has no unique solution. I think there may be a minimal

number of non-blank entries needed for the solution to be unique, tho I think a

solution always exists if you do not have repeated numbers along either a row or

a column.

exists if you do not have

 

[Number Nine]

Some Sudoku puzzles require guessing, other don't; it depends how they're constructed.
Whether or not requiring guessing is "fair" is another matter entirely, and I'm sure you can find a flame war about it if you look in the right forums.

Suppose there is a Sodoku puzzle where you have to guess. If you work out the rest of the missing numbers through logic eventually you will figure out if your guess was correct or not. But by doing so you have logically concluded the correct number for the square, implying a guess was not needed.

In some puzzles, you will reach a point where the existing entries do not provide enough information to determine any definitive next entry (anywhere). In these cases, you have to make a guess and then keep on solving based on the guess in order to see whether or not you've guessed correctly. This is not terribly uncommon; it takes a fair bit of effort to build puzzles that don't require guesswork.

 

[Matt Benesi]

Do you have an example of a sudoko that requires guessing?

I'm pretty sure analysis can get you to the solution without a guess.

 

[jedishrfu]

I've heard that a given puzzle needs a minimum of 17 squares defined to make it have a unique solution. I don't think it's been proven mathematically yet. Given that logic alone should be sufficient to solve the puzzle. Sometimes it requires evaluating multiple squares interdependencies to find a solution and in those cases people begin guessing rather try all combinations.

 

[Bacle2]

Do you have an example of a sudoko that requires guessing?

I'm pretty sure analysis can get you to the solution without a guess.

Most trivially, like many have said here, imagine a sudoku with no known entries at all.

For the OP, it may work to first try a 4x4 Sudoku first.

I wonder if we can use decidability of a (finite) formal system; most of these concepts

AFAIK, apply to infinite systems.

Another interesting question, I think, is how many nxn sudokus there are.

 

[Number Nine]

Do you have an example of a sudoko that requires guessing

Here. Try solving it.

 

[Bacle2]

Here. Try solving it.

:

Hmm... interesting. I think 25 knowns is minimal; in this site:

http://www.websudoku.com/

The 'Evil' level ; the hardest, is a level where there are only 24 knowns, and

(I think) the puzzle has a unique solution. Would be nice to determine the

mininal number for nxn sudokus.

 

[Number Nine]

:

Hmm... interesting. I think 25 knowns is minimal; in this site:

http://www.websudoku.com/

The 'Evil' level ; the hardest, is a level where there are only 24 knowns, and

(I think) the puzzle has a unique solution. Would be nice to determine the

mininal number for nxn sudokus.

It does have a unique solution. The uniqueness of the solution has nothing to do with whether or not the puzzle requires guessing.

 

[Matt Benesi]

Here. Try solving it.

So you don't mean "guess", but rather test paths, such as when you have only 2 places to put a number, one of which will not work?

I suppose you could say that you are "guessing" which path will work out, but some people simply follow specific formulas when path testing.

Such as: pick 2 boxes with 2 possibilities, assign the lowest number to both, if it solves out, good, otherwise switch box one to higher number...

So really, guessing is totally unnecessary, provided you follow specific formulas for path testing. In fact, guessing would be a hindrance, as you might accidentally guess the same numbers more than once.

 

[Number Nine]

So you don't mean "guess", but rather test paths, such as when you have only 2 places to put a number, one of which will not work?

I suppose you could say that you are "guessing" which path will work out, but some people simply follow specific formulas when path testing.

Such as: pick 2 boxes with 2 possibilities, assign the lowest number to both, if it solves out, good, otherwise switch box one to higher number...

So really, guessing is totally unnecessary, provided you follow specific formulas for path testing. In fact, guessing would be a hindrance, as you might accidentally guess the same numbers more than once.

That's what guessing means. When people talking about "guessing" in Sudoku, they mean not knowing which number goes where (because it's unknowable at that point), and guessing at a solution, which they verify by assuming that the solution is true and proceeding with the puzzle. If you go on any Sudoku forum and ask about "guessing", they will interpret it the same way I've described it, and it's almost certainly what the OP's friend meant. What else could it mean?

 

[Matt Benesi]

That's what guessing means. When people talking about "guessing" in Sudoku, they mean not knowing which number goes where (because it's unknowable at that point), and guessing at a solution, which they verify by assuming that the solution is true and proceeding with the puzzle. If you go on any Sudoku forum and ask about "guessing", they will interpret it the same way I've described it, and it's almost certainly what the OP's friend meant. What else could it mean?

Formulaic path testing isn't the same as guessing. I suppose you could guess which path to take instead of following a specific formula for path testing, but following a specific formula will prevent you from accidentally skipping or duplicating a path.

Brute force formulaic path elimination is a logical method of solving sudoko when multiple paths exist. There is no need for guesswork.

 

[Bacle2]

It does have a unique solution. The uniqueness of the solution has nothing to do with whether or not the puzzle requires guessing.

In my definition if the solution is unique, it can be obtained without guessing; I can determine, for a given setup if a number fits a place or not. I believe there is a method for deciding what numbers goes where if the solution is unique.

 

[Bacle2]

To be honest, I do not have a proof that a "deasible" initial arrangement with enough knowns can be determined without guessing. I think I remember hearing that sudoku is decidable, i.e., that there exists an algorithm that will , in finitely-many steps, complete a sudoku puzzle, but I am not sure.

Number Nine: do you know of any argument otherwise, i.e., that there are sudokus that cannot be completed without guessing?

 

[mfb]

@Number Nine: If that is "guessing", you can basically call every nontrivial conclusion a guess.

Consider the attached example (click on it to zoom)

You can conclude that the lower left square needs a 3 in the upper right position. But how do you do that?
You see that the 3rd column misses {1,2,3,4} and that both 1 and 2 have to go in the lower two spots as they are already present in the rows above. Therefore, 3 and 4 remain for the upper two positions. 3 cannot go in the uppermost box, therefore you can determine its position.
What you call "guessing" is just a longer line of reasoning.

 

[Diffy]

Just thought it was interesting:
http://www.sudokuoftheday.com/pages/techniques-11.php

There apparently is a very fine line between guessing and a technique.

Say you have a puzzle. And say you have 2 squares. If you say, "suppose this square is a the 7, then that means that this square would be a 4 etc. etc." And that path of logic leads to a contradiction. Something like two of the same number in one row. Well then you know that the first square could not be a 7.

I could look at that and say well you used logic to figure out the correct number for the original square. Someone else could look at that and say you guessed 7 and eventually found it wrong.

 

[Bacle2]

I took the statement that guessing is necessary to mean that it is impossible to construct an algorithm which would, in finitely-many steps, be able to decide the number that fits in any given situation.

 

[Diffy]

I took the statement that guessing is necessary to mean that it is impossible to construct an algorithm which would, in finitely-many steps, be able to decide the number that fits in any given situation.

This is where I get caught up. I can't prove it, but it seems like if that were the case, it would imply that there is not a unique solution.

 

[jedishrfu]

When I do sudoku puzzles, I'd select some square to ponder and then realize I don't have enough info to select its number so I move to another square. The question would be is there ever a time when all blank squares are ambiguous when a guess is required to move forward (in a sense its like a proof by contradiction).

I think there must be one blank square always that is unambiguously decidable but that the logic needed to determine its number is too long to work out for the puzzler or that they may miss some logic connection due to their level experience in solving these kinds of puzzles.

 

[Bacle2]

When I do sudoku puzzles, I'd select some square to ponder and then realize I don't have enough info to select its number so I move to another square. The question would be is there ever a time when all blank squares are ambiguous when a guess is required to move forward (in a sense its like a proof by contradiction).

I think there must be one blank square always that is unambiguously decidable but that the logic needed to determine its number is too long to work out for the puzzler or that they may miss some logic connection due to their level experience in solving these kinds of puzzles.

Right; but it would be nice to see how this ability to be able to determine the connection breaks down when you have 25+ unknown numbers in your puzzle -- I have not gotten to work on the much-simpler 4x4 sudoku to see what the largest number of unknowns is.