Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove Sodoku does not require a guess.

  1. Jul 26, 2012 #1
    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.
     
  2. jcsd
  3. Jul 26, 2012 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    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.
     
  4. Jul 26, 2012 #3

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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".
     
  5. Jul 26, 2012 #4

    Bacle2

    User Avatar
    Science Advisor

    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
     
  6. Jul 26, 2012 #5
    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.

    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.
     
    Last edited: Jul 26, 2012
  7. Jul 26, 2012 #6
    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.
     
  8. Jul 26, 2012 #7

    jedishrfu

    Staff: Mentor

    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.
     
  9. Jul 26, 2012 #8

    Bacle2

    User Avatar
    Science Advisor

    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.
     
    Last edited: Jul 26, 2012
  10. Jul 26, 2012 #9
    Here. Try solving it.
     

    Attached Files:

  11. Jul 26, 2012 #10

    Bacle2

    User Avatar
    Science Advisor

    :

    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.
     
  12. Jul 26, 2012 #11
    It does have a unique solution. The uniqueness of the solution has nothing to do with whether or not the puzzle requires guessing.
     
  13. Jul 26, 2012 #12
    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.
     
    Last edited: Jul 26, 2012
  14. Jul 27, 2012 #13
    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?
     
  15. Jul 27, 2012 #14
    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.
     
  16. Jul 27, 2012 #15

    Bacle2

    User Avatar
    Science Advisor

    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.
     
  17. Jul 27, 2012 #16

    Bacle2

    User Avatar
    Science Advisor

    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?
     
  18. Jul 27, 2012 #17

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

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

    Attached Files:

  19. Jul 27, 2012 #18
    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.
     
  20. Jul 27, 2012 #19

    Bacle2

    User Avatar
    Science Advisor

    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.
     
  21. Jul 27, 2012 #20
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Prove Sodoku does not require a guess.
  1. Guess the equation. (Replies: 2)

Loading...