• 0

The hardest Sudoku problem?

Question

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

7 answers to this question

  • 0

Posted (edited) · Report post

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 by antipope
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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. (1016 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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

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 by dgreening
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

 - -|- -
|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|
 - - - -
0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

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 by dgreening
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.