5
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ I find "guessing" to be a rather vague term... if you have 3 cells in a row, which can all contain 3 and 5, and the last one can also contain 7. Then naturally the last one has to be 7. Would you say that you "guess" the 3rd cell is a 3 or 5, and then encounter a contradiction? Or is it just a logical deduction? In the same way, eventually all options you eliminate via "guessing" are logical deductions, "this cell can't be x because that would imply this row/column/3x3 can't be solved" $\endgroup$ – Lolgast Nov 30 '17 at 15:07
  • $\begingroup$ "if you have ...and the last one has to be 7" Yes I call this a logical deduction, there is only one cell in your row for 7. You can see "options" as values possible for a given cell, or cells possible for a given value in one of the subsets (row, column, block), but this is equivalent. * * * * At the end it becomes logic true, but at some point you are choosing between two options randomly, because you cannot plan ahead far enough. $\endgroup$ – AIDoubt Nov 30 '17 at 15:12
  • $\begingroup$ Okay, maybe my example wasn't the clearest. Imagine you have 3 3x3 blocks side by side, each several possibilities for the value 1. In the left block, 1 can be in the top or the lower row. In the middle block, it could be in the middle or the lower row. In the right block, the possibilities are all on the top row. Then it can quite easily be seen that since there is a 1 in the top row, the 1 in the left block must be in the lower row and thus the middle block must have it in the middle row, even though there's not a single possibility on a row by row or block by block basis. $\endgroup$ – Lolgast Nov 30 '17 at 15:26
  • $\begingroup$ Regarding "cannot plan ahead far enough"... I guess that constitutes guessing, eh? When can you "plan ahead" and when does it start "being guessing"? Note: No offense intended at all, I'm just wondering if it's possible to give any objective answer to such a question. $\endgroup$ – Lolgast Nov 30 '17 at 15:27
  • 1
    $\begingroup$ The question, it seems to me, is, "Can a complete set of solving rules/techniques be given that will solve any 9 by 9 Sudoku puzzle?" "Backtracking" or "Brute Force" is not allowed. If the answer is yes, give the complete set of such rules. $\endgroup$ – Robert Cowen Jan 18 '18 at 18:03
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I corrected how the link was typed in so it could be clicked on. However, I get a security warning when I click on it so haven't actually visited the page. I would recommend putting this in as a picture rather than a link as that is the case. $\endgroup$ – kaine Dec 1 '17 at 15:15
  • 1
    $\begingroup$ It doesn't seem to be working as an image, so I'll just copy it as a grid. $\endgroup$ – Jakob Lovern Dec 1 '17 at 18:42
  • $\begingroup$ Hello, thank you for your input, this cannot be seen as a valid answer though : see my addition. $\endgroup$ – AIDoubt Dec 3 '17 at 21:08
  • $\begingroup$ I seem to remember running my solver on this, or a very similar sudoku. Even though the solver had a lot more deduction rules than just the ”bare rules of grid”, there was something like nine nested layers of ”well, not getting anywhere with deduction, let’s just try every possible number in this spot and see if exactly one of them produces a solution.” $\endgroup$ – Bass Dec 4 '17 at 19:45
  • 1
    $\begingroup$ this puzzle is not and has never been considered by the sudoku community as the hardest puzzle. Today, in the hardest sudokus database, containing 1,959,402 puzzles, its ranking is # 1,014,937. For more details, see this thread [forum.enjoysudoku.com/… For the current database, see this post [forum.enjoysudoku.com/… $\endgroup$ – JPF Aug 14 '18 at 15:51
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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:

enter image description here

Here is the board after "bare rules" :

enter image description here

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

$\endgroup$
  • $\begingroup$ Thank you. I am afraid the question was still poorly worded :< The easiest but too obscure wording would be : "is there any sudoku grid that the program linked on github cannot solve?" Or in a more readable way : "are there sudoku puzzles with unique solutions that have 3+ options for every candidate number once the bare rules of the grid are applied?" In your example for example on submat line 2 column 3, there are only 2 positions possible for 5, hence a 50% guess exists. Your Easter Monster grid takes 14 of the above 50% guesses to solve. platinum blonde takes 653 but still solves. $\endgroup$ – AIDoubt Nov 17 '18 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.