Sudoku and guessing : theory?

Question

It has been proven that the minimum number of givens for a uniquely solvable classic 9x9 sudoku is 17.

The usual solving method followed by people is : Fill all the cells where you are sure there is only one option, using the rules of the grid and a set of methods. Edit : we will restrain the problem first to the single position method (linking this again) since this is what I have implemented in my c program :)

If you have not filled everything yet, make a guess. Then solve the grid, or encounter a contradiction : then backpropagate. Maybe making sometimes chained guesses.

1 (prequel) - Is it proved that some sudokus need you to guess once all the rules have been applied? From what does the need for a guess happen?

2 (question) - Is it proved that, if you have to guess, you can solve the grid only guessing for cells that have two options, and not more (not three, four ... nine options)? Or do some sudokus need 3-option guesses or more, possibly asking for the exploration of three or more sub-sudokus? Better said : are there sudoku puzzles with unique solutions that have 3+ options in every cell [corrected 11/17/2018 : replace by "3+ position candidate"] once the bare rules of the grid are applied?

Answer 1

Yes, this is possible. It is very possible, in fact. Since you're writing a program for this, I'll use pseudocode, etc. to demonstrate some techniques you should try.

I had to write a sudoku solver for Project Euler #96 a while back in Python, so here's what I did:

1. Find all the obvious 'Only one value can go in this slot.' places.
2. For each square, row, and column, find values that can only go into one slot.
3. Repeat 1 and 2 until the grid doesn't change.

4. Find squares like this:

    2 1 X
    3 4 X
    9 7 X
   

   in the grid. Now, we don't know where to place the number 6, but we know it must be the third column. So we use that to eliminate possibilities in the other two squares in that column. This technique can be used for row-square interactions, as well.

5. Once all the obvious interactions have been exhausted (There are more complex interactions that you can use, but they require more complex code,) Use brute force. The algorithm looks something like this:

   For every row in the grid:
      For every cell in the row:
         Make a list of all the possible values for that cell.
         Choose the lowest value and push it into the cell.
         If the cell cannot take any value:
            Erase the cell and backtrack to the last cell you chose a value in. Increase the value to the next possible one. 
   Check to see if the grid is solved.
   

As for the 'is there a sudoku that requires multistage inference (read: guessing)' Yes, there is. Take a look at this:

┌─────┬─────┬─────┐
│8 . .│. . .│. . .│
│. . 3│6 . .│. . .│
│. 7 .│. 9 .│2 . .│
├─────┼─────┼─────┤
│. 5 .│. . 7│. . .│
│. . .│. 4 5│7 . .│
│. . .│1 . .│. 3 .│
├─────┼─────┼─────┤
│. . 1│. . .│. 6 8│
│. . 8│5 . .│. 1 .│
│. 9 .│. . .│4 . .│
└─────┴─────┴─────┘

It's widely regarded as the 'hardest sudoku' because of how much inference is required to solve it, even though it has one definite solution.

Answer 2

For the second part of your question, the answer is yes.
Here is an example with this puzzle - Easter Monster - I released in April 2007:

Here is the board after "bare rules" :

pics were taken from this site.
Many hard puzzles have the same property.
See the hardest sudokus database in this thread.

Answer 3

The problem was indeed poorly exposed.

See this c program : https://github.com/Maxzor/dummy_sudoku_solver.

Its pseudo-code is :

Iterate through values 1-9
   Iterate through the three subset types (row, column, submat)`   
      Iterate through each subset number in the subset type (row1, column8, submat6...)
         If only one cell in the subset number is an option for the value, fill the value in.

Do the same loop, but when two options are found for a subset number
 branch one matrix from the existing one, fill the two options in the
 two different matrices, and explore them
Backtrack if the matrix gets in a inconsitent state.

I have not found any (classic 9*9) grid that this algorithm cannot solve.

As the team that proved 17 is the god-number in sudoku did, we could prove that there is no need for a 3-option guess in this algorithm by exploring the whole search space. Which would answer my question but not in the most elegant way.

Arto Inkala grid as linked by Jakob Lovern takes an impressive 438 guesses but still solves in 200ms on my toaster. Some 17-clue grids require 0 guesses, single candidate position rule is enough. This looks interesting to me, looking for "from where does the complexity of the grid comes", "and where does the need for guesses arise".

This is not a terribly interesting question, but there is very little theory about the influence of the distribution of givens in the grid on its complexity and it could be explored.

Maybe mathematics would be a better stackexchange place for it, since I thought it was rather trivial, but might not be so easy.