07-12-2012, 04:48 PM | #1 |
(ಠ⌣ಠ)
|
The World's Hardest Sudoku (June 2012)
Most people who actually solve this did so via guess and check, after you get a couple numbers filled in correctly it's not that hard. This puzzle is solvable completely by pure logic as all sudokus are meant to be. Discuss any type of logic and strategy here. Obviously seeing that you got it "all correct" is of no value if you don't have a logical explanation as to how you got your first number. I'm currently working on it now. half an hour or so the past three days and making some progress with my current approach. Hoping to get my first number after 3 more hours.
To put this into perspective, sudokus are officially judged on a scale of stars from 1-5. This puzzle scores 11. |
07-12-2012, 06:11 PM | #2 | |
Spun a twirly fruitcake,
Join Date: Feb 2009
Age: 31
Posts: 3,865
|
Re: The World's Hardest Sudoku (June 2012)
__________________
Quote:
|
|
07-12-2012, 06:15 PM | #3 |
x'); DROP TABLE FFR;--
Join Date: Nov 2010
Posts: 6,332
|
Re: The World's Hardest Sudoku (June 2012)
Yikes, that one is messy
|
07-12-2012, 06:43 PM | #4 |
x'); DROP TABLE FFR;--
Join Date: Nov 2010
Posts: 6,332
|
Re: The World's Hardest Sudoku (June 2012)
Oh, right, the explanation:
Normally you can seed each square with a subgrid containing all values 1-9 (indicating possible values) and then eliminate all those that are impossible. For easier puzzles this makes it clear which squares to fill in. When you do this for this puzzle, you find that none of the currently unknown-squares have one tick left. At this point, you typically invoke recursive techniques and what have you, which are trivial for computers to solve but not realistically feasible for humans. However, it's worth noting that the square in position (7,2) (the middle-row left-column square within the lower right primary square) only has two possible values: 9 and 3. None of the other unknowns have so few potentials, so that's a good place to begin a guess-and-check method. |
07-12-2012, 06:47 PM | #5 |
Descension from Heaven
Join Date: Apr 2009
Posts: 2,180
|
Re: The World's Hardest Sudoku (June 2012)
Okay Rubix.
__________________
|
07-12-2012, 06:52 PM | #6 |
x'); DROP TABLE FFR;--
Join Date: Nov 2010
Posts: 6,332
|
Re: The World's Hardest Sudoku (June 2012)
You disagree?
|
07-12-2012, 08:08 PM | #7 | |
D6 FFR Legacy Player
Join Date: Jan 2009
Age: 32
Posts: 4,342
|
Re: The World's Hardest Sudoku (June 2012)
Quote:
|
|
07-12-2012, 08:57 PM | #8 |
Snek
Join Date: Jan 2003
Location: Kansas
Age: 34
Posts: 9,192
|
Re: The World's Hardest Sudoku (June 2012)
|
07-12-2012, 09:13 PM | #9 |
FFR Simfile Author
|
Re: The World's Hardest Sudoku (June 2012)
are we guaranteed that there exists only one unique solution? If not, it would explain why it's easy to solve via guess and check, but hard to solve via logic.
|
07-12-2012, 10:01 PM | #10 |
The Doctor
Join Date: Apr 2006
Age: 35
Posts: 6,145
|
Re: The World's Hardest Sudoku (June 2012)
I would only be able to solve this by the guess and check method, and it's still questionable for me at that.
|
07-12-2012, 10:14 PM | #11 |
FFR Simfile Author
|
Re: The World's Hardest Sudoku (June 2012)
Nevermind, got my first number.
Edit: And solved by hand. Last edited by dag12; 07-12-2012 at 11:05 PM.. |
07-12-2012, 11:24 PM | #12 | |
x'); DROP TABLE FFR;--
Join Date: Nov 2010
Posts: 6,332
|
Re: The World's Hardest Sudoku (June 2012)
Quote:
What makes this puzzle "hard" is actually more a form of tedium. You have to plan ahead a few levels of depth since you don't wind up with single-ticked boxes after eliminating all the collisions. I solved it by hand by making a few educated guesses early on (and then the rest just kinda fell into place). I didn't solve it via braindead algorithm because it seemed like there were going to be too many instances where I'd be faced with two or more choices, which multiply out pretty quickly. But it's also possible that these dual-pronged dilemmas only last for a couple rounds -- I didn't check. Would have to ask dag what his approach was. dag: As far as I can tell, there's only one unique solution. Last edited by Reincarnate; 07-12-2012 at 11:28 PM.. |
|
07-12-2012, 11:29 PM | #13 | |
FFR Simfile Author
|
Re: The World's Hardest Sudoku (June 2012)
As far as I know, there isn't a clean logical way to do it.
My method used a brute force proof by contradiction haha (though for many places where there are two possible choices, it's hard even to just find a contradiction for one of them) Quote:
|
|
07-12-2012, 11:34 PM | #14 |
x'); DROP TABLE FFR;--
Join Date: Nov 2010
Posts: 6,332
|
Re: The World's Hardest Sudoku (June 2012)
On second thought I think you're right -- by "logic alone" I mean to imply that they can be algorithmically solved for even if collision-removals aren't sufficient. Of course, with sufficient depth, that algorithm becomes indistinguishable from brute force, which may not feel as "logical."
|
07-12-2012, 11:43 PM | #15 |
FFR Simfile Author
|
Re: The World's Hardest Sudoku (June 2012)
If there's only one unique solution, you could technically 'logically' disprove every other alternative to get to the solution. By definition, that's still logic.
Though of course, whether that intuitively feels logical is another matter. |
07-12-2012, 11:58 PM | #16 |
Fractals!
|
Re: The World's Hardest Sudoku (June 2012)
Guess and check is still logical, I thought. It's really just another form of reductio ad absurdum where if you have two possibilities and one of them leaves you with an impossible situation, then the other is correct.
Still, I'm not touching that thing. The "fiendish" puzzles that one NYTimes guy does are too much for me. |
07-13-2012, 12:12 AM | #17 | |
(ಠ⌣ಠ)
|
Re: The World's Hardest Sudoku (June 2012)
Quote:
Edit: Verified one unique solution. |
|
07-13-2012, 12:23 AM | #18 |
FFR Simfile Author
|
Re: The World's Hardest Sudoku (June 2012)
Just checked with a program that uses all known 'human-like' techniques to solve sudoku puzzles, and it wasn't able to solve it.
Solving it by brute force guess and check, I've verified that there's only one solution. That leads me to believe that the only way to solve it is by ruling out alternatives by contradiction... |
07-13-2012, 12:38 AM | #19 |
FFR Player
Join Date: Dec 2008
Age: 33
Posts: 6,205
|
Re: The World's Hardest Sudoku (June 2012)
Put a number in a square, if it doesn't work, it's the wrong number kpCE
__________________
|
07-14-2012, 04:48 AM | #20 |
FFR Veteran
|
Re: The World's Hardest Sudoku (June 2012)
I think the question is what is the most efficient algorithm for solving this, or other similarly arbitrarily hard sudoku puzzles? Is there one? And can it be proven to work for all, and not just most, cases?
Brute forcing it or "guess and check", while logically sound, is least algorithmically efficient, provided there is any other algorithm that will work. So the problem isn't so much "solve this" as it is "solve this efficiently". Or basically, to phrase this as a math problem, either find a mathematical algorithm which is more efficient than brute force for solving this problem or mathematically prove such an algorithm does not exist (and therefore that it must be brute-forced). |
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests) | |
|
|