Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -

The hardest Sudoku problem?


  • Please log in to reply
7 replies to this topic

#1 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5918 posts
  • Gender:Male
  • Location:New York

Posted 07 July 2014 - 02:54 AM

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?

 

Spoiler for Hint


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#2 antipope

antipope

    Newbie

  • Members
  • Pip
  • 3 posts

Posted 08 July 2014 - 12:59 AM

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, 08 July 2014 - 01:03 AM.

  • 0

#3 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5918 posts
  • Gender:Male
  • Location:New York

Posted 08 July 2014 - 06:28 PM

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
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#4 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1459 posts
  • Gender:Male

Posted 14 July 2014 - 04:48 AM

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

  • 0

#5 dgreening

dgreening

    Junior Member

  • Members
  • PipPip
  • 75 posts
  • Gender:Male
  • Location:Maryland [DC area]

Posted 14 July 2014 - 01:40 PM

Spoiler for

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

Spoiler for

 


Edited by dgreening, 14 July 2014 - 01:42 PM.

  • 0

#6 dgreening

dgreening

    Junior Member

  • Members
  • PipPip
  • 75 posts
  • Gender:Male
  • Location:Maryland [DC area]

Posted 14 July 2014 - 01:59 PM

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

#7 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1459 posts
  • Gender:Male

Posted 14 July 2014 - 02:48 PM

Spoiler for two different solutions if the 4 is left out

  • 0

#8 dgreening

dgreening

    Junior Member

  • Members
  • PipPip
  • 75 posts
  • Gender:Male
  • Location:Maryland [DC area]

Posted 14 July 2014 - 05:42 PM

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, 14 July 2014 - 05:43 PM.

  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users