Is It OK to Guess in Sudoku? Trial and Error vs Proof by Contradiction

You have written every pencil mark and looked for every technique you know, and still no cell can be filled. There is a cell with only two candidates right in front of you, and it looks as if trying one of them would get you moving again. Anyone who keeps solving sudoku runs into this again and again.
In earlier posts I wrote that a lucky guess is not solving. But “just try a number” actually comes in several forms. This post covers the differences, and a kind of assumption that rests on a reason.
Guessing, trial and error, and contradiction
There are three main forms of “trying a number”.
Guessing. You put in one of the candidates and carry on solving. If you reach the end, you are done. If you get stuck, you end up erasing without knowing where things went wrong.
Trial and error. You put in one candidate and carry on. When you hit a contradiction, you go back to that cell and put in the other one. Repeat this and you will reach the answer eventually. This is basically how computers solve sudoku. English Wikipedia’s Sudoku solving algorithms describes backtracking, filling empty cells with digits in order and going back to an earlier cell when the rules are broken, as a kind of brute-force search.
Proof by contradiction. You assume “if this cell were 4” and follow the cells that are forced from there. If that leads to a contradiction, you conclude “this cell is not 4” and remove 4 from its pencil marks. The assumed number never stays on the grid.
The third is the same shape as proof by contradiction in mathematics. “If it were 4, there would be a contradiction, so it is not 4” is sound logic. Unlike a guess, the conclusion has a real reason behind it.
Assumptions by contradiction
One view is that assumptions in the form of proof by contradiction are fine to use. Two reasons can be given.
First, some named techniques already work with “what if”. XY-Wing, for example, splits into cases: “if the middle cell is A, this cell becomes C; if it is B, that cell becomes C; either way, one of them is C.” You could call it two small assumptions side by side. I wrote about it in Advanced Sudoku Techniques.
Second, even among experienced solvers there is no clear line where assumption starts. The English site SudokuWiki describes a technique called Nishio, which assumes one candidate and follows it to a contradiction, as a “semi ‘trial and error’ approach”, while still treating it as a strategy with defined rules.
Guessing and trial and error, on the other hand, can be seen as closer to checking the answer than to solving it. You fill in numbers to the end to see whether they fit, and a computer does that in an instant.
How to use contradiction
To use proof by contradiction, go in this order:
- Pick a cell with only two candidates. Assuming a number in a cell with many candidates spreads the trail too wide.
- Assume one, and follow only the forced cells. If “this cell is 4”, then 4 disappears from the pencil marks in the same row, column and box. Any cell left with one candidate is then fixed too. Follow only the cells that are forced, one at a time.
- Look for a contradiction. That means the same digit twice in a row, column or box, a cell with no candidates left, or a digit with nowhere to go in some row, column or box.
- If you find one, remove the assumed number. You now know “it is not 4”, so remove 4 from the original cell’s marks. Since it had two candidates, it is now the other one.
- If you get stuck without a contradiction, you have learned nothing. Erase everything you followed and go back to the original grid.
Step 5 matters most. No contradiction is not proof that the assumption is right. It only means nothing contradicted it as far as you could follow. If you carry on with the assumption still in place, what you meant as proof by contradiction has turned into a guess.
A small example
Here is just the shape. Say three cells in one box have these pencil marks:
- Cell A: 4 or 7
- Cell B: 4 or 9
- Cell C: 4 or 9
Assume A is 4. B and C are in the same box, so neither can be 4, and both become 9. That puts two 9s in the box. It is a contradiction, so A is not 4. A is 7.
As it happens, you can solve this example without any assumption. B and C are two cells whose only candidates are 4 and 9. Those two cells use up 4 and 9, so 4 and 9 can be removed from every other cell in the box. That is the naked pair from the first techniques beginners learn.
This is a useful lesson from using assumptions. A contradiction you find by assuming is usually a technique you haven’t spotted yet, said another way. When you find a contradiction, look back at the grid and ask why it happened. If you find a named pattern there, next time you can do the same thing without assuming anything.
Before you assume
Contradiction takes effort. Before trying it, there are two things to check.
First, whether your pencil marks are right. If you have erased a candidate you shouldn’t have, no technique and no assumption will work properly. How to check your marks is in Stuck on a Sudoku?
Second, the difficulty. As I wrote in What Makes a Sudoku Easy or Hard?, every Easy puzzle in Sudoku365 has been checked to solve with the basic techniques alone, and every Hard puzzle with techniques up to reservations and pairs and triples. If you are stuck in that range, looking for the technique you missed is quicker than assuming. In Expert, many puzzles can’t be finished even with every named technique, and that is where reasoning like proof by contradiction finally comes in.
Testing assumptions in Sudoku365
Sudoku365 is a sudoku app I make. It runs on iPhone, iPad and Android. It has 300 puzzles at each of four difficulty levels, 1,200 in all, and every puzzle has exactly one answer.
There is one thing to know before testing an assumption in the app. Every number you enter is checked against the answer straight away. A wrong number turns red and counts as a mistake, and three mistakes end the game. A right number stays in place. So if you enter a number as an assumption, you are really checking the answer.
So to test an assumption in the app, use pencil marks, not numbers. Change the marks of the cells you follow, and if you hit a contradiction, remove the assumed number from the original cell’s marks. Undo takes back the marks you changed along the way, one step at a time, including marks that were removed automatically when you placed a number. The mistake count does not go back, though.
You start with 10 hints, and you get one more each time you clear a puzzle or watch an ad. When even an assumption doesn’t settle anything, filling one cell with a hint and working out why that number goes there is also a good use.
The app is free with ads, and a one-time Remove Ads purchase turns them off. For your first puzzle, see Getting Started with Sudoku365.
Sudoku365Daily sudoku, alone or with twoSee the app →