The hardest Sudoku problem?

[bonanova]

Sudoku is a commonly played game where the digits 1-9 are placed in a 9x9 array.

The rules prohibit duplicate entries in rows, columns and the nine 3x3 sub-arrays.

Of course there is an astronomical number of solutions to that problem.

Now, any self-respecting Sudoku puzzle has a unique solution.

And to bring about a unique solution, some of the 81 cells come initially filled in.

One can imagine that the simplest Sudoku puzzle would have 80 cells -- all but one -- already filled in.

It would only take a glance at the 8 digits already in its row, column or 3x3 array to solve the problem.

And in general, the fewer cells that are filled in, the more difficult it is to find the unique solution.

So the question we ask is this:

If we want to make a Sudoku puzzle difficult simply by reducing the number of initially specified cells,

how many cells would have to be initially specified to still insure a unique solution?

For those who like to Google, your number probably will be too large.

[antipope]

It looks like this problem is not solved yet, is it?

According to Wikipedia (and some paper from year 2012) the number you're asking for is larger than **.

EDIT: Ok, I think this paper has the solution

Edited July 8, 2014 by antipope

[bonanova]

Problems like this one are amenable to brute force computation.

Assume the answer is n.

Take all the sets of clues that have only n-2 cells filled in.

Show that all of them permit at least two solutions.

That approach fails here because of size. (10¹⁶ sets of clues).

So a better discussion point would be:

How would you go about a getting reduction in size that would make it tractable?

Which permits me to comment that I think the best puzzles are much more about methods than about answers.

Basically, the difference between Aha! and Google.

[plasmid]

One thing I can say so far, which might or might not be pertinent, is that

with a 2x2 rather than 3x3 version of Sudoku, where the entire field has four large squares and each of those large squares is divided into four small squares that hold the numbers, the smallest number of clues I can specify a game with is four.

 - -|- -
|1| | | |
 - -|- -
| | |3| |
----+----
| | | |4|
 - -|- -
| |2| | |
 - - - -

The rationale about how I went about constructing it attempting to minimize the number of clues should become obvious if you solve this small puzzle.

[dgreening]

4 numbers to have a unique solution.

In this 2x2 example, change the 4 to a blank and you can still solve with a

unique solution.

One thing I can say so far, which might or might not be pertinent, is that

with a 2x2 rather than 3x3 version of Sudoku, where the entire field has four large squares and each of those large squares is divided into four small squares that hold the numbers, the smallest number of clues I can specify a game with is four.

 - -|- -
|1| | | |
 - -|- -
| | |3| |
----+----
| | | |4|
 - -|- -
| |2| | |
 - - - -

The rationale about how I went about constructing it attempting to minimize the number of clues should become obvious if you solve this small puzzle.

Edited July 14, 2014 by dgreening

[dgreening]

First, I would like to apologize for clobbering the posting above [pls ignore it!]

I tried to cover part of my reply with "spoiler" and ended up with a mess ... sorry!

Re: Plasmid's "One thing I can say so far, which might or might not be pertinent, is that"

You can simplify this even further by removing one of the numbers ... it still results in a unqiue solution.

[plasmid]

 - -|- -
|1|3|4|2|
 - -|- -
|2|4|3|1|
----+----
|4|1|2|3|
 - -|- -
|3|2|1|4|
 - - - -


 - -|- -
|1|3|2|4|
 - -|- -
|2|4|3|1|
----+----
|3|1|4|2|
 - -|- -
|4|2|1|3|
 - - - -

[dgreening]

You are correct!

I must had made a leap of faith, when I was solving - apologies!

in fact [in your second solution] you can reverse the order of 24 and 42 in the top right and lower right "large" squares to create one more solution.

Edited July 14, 2014 by dgreening