This is a tough one. SimpleSudoku can’t solve it. SudokuSolver can’t solve it by logic - guessing is required. I agree that guessing should not be required.
I recommend Sudoku.org, which has a great tutorial, as well as a downloadable program that generates puzzles, and will allow you to enter your own. It allows for “pencil marks” in the boxes for possibilities.
I entered this puzzle, and it did not “verify”, meaning it could not be solved without guessing, which is apparently not how it’s supposed to work. I have never had to guess on the puzzles they provide. They could all be solved by logic. This one, though, apparently does not provide enough information, which they claim happens in 1 out of every 700 printed puzzles, and 1 out fo every 200 online puzzles
It did provide enough information, and it could be solved by logic. Reductio ad Absurdem is a perfectly valid logical method. But I agree that it’s less satisfying.
I’m trying to master Reductio ad Absurdem logic as it applies to sudoku, and I need to know if my logic in the example given below is correct or not. Let’s say that for a given number you have certain pattern of squares which might, or might not, be that number, such as the following simplified diagram (it can be presumed that the spacing of the 3x3 subgrids doesn’t eliminate any possibilities) :
* * *
* *
* *
Suppose that I presume that the square in the bottom left corner is in fact the number I"m considering (Y=true, N=not true). In that case, the status of all the other possibilities is determined:
N Y N
N Y
**Y** N
If the bottom left square is the number in question, then the top right square is not. Now if I start with the top right square and presume that it is the number, then again the status of the rest of the squares is determined:
N N **Y**
Y N
N Y
In other words, taking the bottom left square as A and the top right square as B, then we have (IF A THEN !B) and (IF B THEN !A).
Now in both instances, the top left square is always N, so at first glance it might appear that it’s proven that that square can’t be the number in question. The problem is that the logic doesn’t go the other way. If I presume A is not the number, that doesn’t prove that B is. And if I presume that B is not the number, that doesn’t prove that A is either:
? N ? ? ? **N**
? ? N Y
**N** Y ? ?
So I’m not sure if I have a true Reductio ad Absurdem or not. Is the top left square guaranteed to be N, or not?
FTR, I played 3 or 4 of the other USA Today games, and I didn’t take longer than 12 minutes for any of them. I gave up on this one after about 45. My bet is that this one was misdesigned or there was a typo (for instance one or two squares were left out).
Assuming that these programs are sufficiently thorough, when they require a guess, does it ever turn out to be wrong?
I know lots of logical methods to solve these. But some of them are sufficiently complex, and hidden among such a wealth of numbers, that I can certainly believe that people would overlook them. If you reach a point where you can’t find anything definitive, it’s time to guess. But if that guess leads to a contradiction, I suspect that the information for the correct number was available, if I could have found it.
It seems to me that if a truly rigourous computer program can not solve a puzzle without a guess from the user, then there is probably more than one solution.
Does anyone know if that’s true?
Well yeah, you did find it :). It’s really just a longer version of the regular methods of solving.
The solver I was using doesn’t require guesses from the user, but you can configure it to use specific techniques, and it couldn’t solve this puzzle without guessing on its own. It said there was only one solution, though.
Never mind my previous post. Five minutes after posting it I saw the logical fallacy (always after, never before :smack: ). At least I know how to do CODE now.
For the record, “reductio ad absurdem” is the method of making a guess and seeing if it leads to a contradiction. If it does, then the initial guess was wrong. It says nothing about the value of any other position. In sudoku, it’s really only useful when you either have a single square with two possibilities, or when you know that a particular number is in one of two different squares. That way, if you reach a contradiction, you can just fill in the other number in that square, or fill in the number in the other square.
There’s another guess-based method which it looks like you’re using (or trying to use). When you only have two possibilities for something, you can try both, one at a time, and get as much as you can. If there’s anything that works in both of them, you know it’s true, even though you might not know which of your initial guesses was correct. So long as you try all possibilities, this is a perfectly valid method, but it doesn’t get you anything that the right reductio couldn’t, and it’s generally harder to do.
It looks like someone at USA Today was reading this thread… As of today, they’ve added some new features to their sudoku, including making notes in squares.