Can Sudoku always be solved with 1 guess?

Question

I have an Excel spreadsheet I created to solve Sudoku puzzles.

It first finds all "simple forced" cells. I define those to be the cells for which (a) there is a number which can go into that cell, but cannot go into any other cell in the row, column, or 3x3 subsquare, or (b) there is only one number that can go into it.

If you look at each square, and note all the numbers that are not eliminated because it already occurs in the row, column, or subsquare, then a number is forced if it occurs only one time in a row, column or subsquare, or is the only number for that square.

Nothing special in all that--it's the way most people would start a methodical solution for a Sudoku, by writing down the allowed numbers for each cell, and then examining them.

For all but the easiest puzzles, you will run out of "simple forced cells" and will have to resort to "deeper" logic, or start making guesses to see if a guess leads to a contradiction, and then start over.

An example of deeper logic would be having 23 23 27 as the only possibilities for three cells in a given row, column or subsquare. You know the cells with 2 and 3 must have a 2 and a 3 in some order, so the cell that can only be 2 or 7 must be 7.

Deeper logic is harder to program, and comes in more varieties, so my spreadsheet takes the guessing approach. It looks at all numbers that haven't been eliminated, plugs them in one at a time, and sees if there is a contraction or if that guess results in a solution, based on finding "simple forced" numbers. If it doesn't find a solution, it backs up and tries another guess.

So far, even for the hardest puzzles (like with minimal 17 clues), it has found a single guess that results in finding the full solution. It takes the cells in order, so if such a key guess is close to the start, it will go quickly (< 5 seconds). If not, it may take up to 2 minutes to find the right guess among the hundred or so possible guesses.

My question is, once all the "simple forced" numbers are found, will there always be 1 guess that will result in all of the other numbers being "simple forced"? (In other words, will my spreadsheet design always be able to find a solution?)

Answer 1

This question interested me so I made a spreadsheet myself that doesn't programmatically solve Sudoku puzzles but will give you an answer to a cell that is highlighted in gold. If there are no gold cells then there are no suggestions and the state is in "guessing" mode. It's all manual and you would just to try another number or a different cell. One could implement a VBA addition to this that would automatically input the answer, and determine when it is necessary to randomly pick a number in "guessing mode".



https://drive.google.com/file/d/0B4vNeXzOlnXmMTEzU3l1Nklzckk/edit?usp=sharing



In the default Sudoku puzzle that I used, one quite easily gets the "forced answers" quickly at which point you enter the "guessing" mode. I did not add a feature to offer the possible answers as they would be quite time consuming, but it should be obvious to most which numbers you can choose. There is no error checking so if you type in an incorrect suggestion, there is no way to tell until you reach an unsolvable state.



I went through several possible guesses and it does seem as if there is almost always a "pivot" point in which the rest of the answers will be forced. In the default puzzle on the provided sheet, if you set J3 = 3, the rest of the puzzle will be naturally solved.



edit : I just noticed that it does miss some suggestions which I will have to figure out how to account for. They are forced cells that occur when a number may only occur in a row or column with a 3x3 block and the perpendicular row or column would indicate that a specific cell would equal that number.

Answer 2

Virtually any 'Sudoku' problem provided will be solvable by logic - however these initial problems are designed to be solvable and thus a solution can be obtained either by algorithmic methods or heuristics.



At the moment your spreadsheet comprises of both algorithmic (find the forced cells) and heuristic (guess an intermediate stage and see whether an answer arises). The fact that the only problems you work on are those with single solutions means that your heuristic is giving the impression of an algorithm.



If you were presented with a Sudoku where there might (or might not) be a single answer given the initial conditions, then your solution seems to be non-polynomial depending on the initial size of the Sudoku and there seems to be no way of checking whether a unique solution exists.

Answer 3

I don't quite understand your question.

So your program fills in all the boxes that are "forced" and then picks a random box that has multiple possibilities. Your program systematically examines each possibility on a case by case scenario until it finds one that leads to no contradictions.

Obviously, it can solve all Sudoku in this fashion. It's basically "brute forcing" its way through every possibility until it finds one that works.



In regards to the "one guess that forces the rest":

Sudokus are designed to have a single solution. Let's say at a guess-point you have x possibilities. Of those possibilities, only one will lead to the solution. After making the correct guess, you may end up in another guess-point. However, like before, only one of the possibilities at that guess-point will lead to the solution. It is completely possible that you can make the incorrect guess at the first guess-point and still arrive at the same second guess-point. However, because the first guess was incorrect, a contradiction will appear, regardless what guess you make at the second guess-point.

Answer 4

Generally, you should be able to do things with just one guess, especially if you are using deep logic like that.

In theory it should be possible to create a puzzle with multiple guesses required. However, the reason you are finishing with one guess is that you are down to just a few possibilities per square.

Answer 5

I would suggest looking at the logic used on the site linked below. There will be times when more advanced strategies will be required. The example you gave of 23 23 27 is referred to as "naked pairs."



Perhaps with this logic and explanations of each, you might be able to program your VBA accordingly.

Answer 6

Sudoku can always be solved without any guesses, just using logic.