FlashFlashRevolution The World's Hardest Sudoku (June 2012)
 Register FAQ Members List Social Groups Calendar Search Today's Posts Mark Forums Read

 Critical Thinking An area specifically for higher-level thinkers. Debates, Essays, Politics etc.

 07-12-2012, 05:48 PM #1 awein999 beep     FFR Veteran Join Date: Oct 2007 Age: 22 Posts: 3,558 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. __________________ boop
 07-12-2012, 07:11 PM #2 SKG_Scintill TSIRLYAAAH FFR Simfile Author     FFR Veteran Join Date: Feb 2009 Age: 21 Posts: 2,516 Re: The World's Hardest Sudoku (June 2012) __________________
 07-12-2012, 07:15 PM #3 Reincarnate x'); DROP TABLE FFR;--     FFR Veteran Join Date: Nov 2010 Posts: 5,265 Re: The World's Hardest Sudoku (June 2012) Yikes, that one is messy
 07-12-2012, 07:43 PM #4 Reincarnate x'); DROP TABLE FFR;--     FFR Veteran Join Date: Nov 2010 Posts: 5,265 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, 07:47 PM #5 Herogashix AM I SEXY-CUTE TOO?!     FFR Veteran Join Date: Apr 2009 Location: 5key, Stepmania Age: 17 Posts: 1,732 Re: The World's Hardest Sudoku (June 2012) Okay Rubix. __________________ New Teaser! https://soundcloud.com/thesapphiredragon/unknown-remix-teaser-01 Check out the RE|INSTALLED Team thread! (Updated Often) Contact me: Facebook: TJ DeJong | AIM: herogashix Soundcloud : The Sapphire Dragon | Mixcloud : The RE|INSTALLED Team Skype: Herogashix | Twitter: Herogashix Updated the spoiler on August, 28, 2013
 07-12-2012, 07:52 PM #6 Reincarnate x'); DROP TABLE FFR;--     FFR Veteran Join Date: Nov 2010 Posts: 5,265 Re: The World's Hardest Sudoku (June 2012) You disagree?
07-12-2012, 09:08 PM   #7
iironiic
Diana is my queen <3
FFR Simfile Author

FFR Veteran
Join Date: Jan 2009
Age: 22
Posts: 4,152
Re: The World's Hardest Sudoku (June 2012)

Quote:
 Originally Posted by Reincarnate 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.
Although I agree with this, I'm sure there is a logical way to tackle all Sudoku puzzles. At least, from what I have been told, Sudoku challenges you to figure out the placement of numbers using pure logic. I suppose brute forcing your way through by guess and checking works, but it's more interesting to figure out a concrete logical way to place all of the numbers in their appropriate spots.
__________________
Check out my Tournament Blog | Check out my Top Ten Funniest Replays!!
__________________

Top Five Favourite FFR Files (in no order): A Beautiful Storm, Sirius, Parousia, Passage D [Heavy], Tenimuhou

Erdos Number: 4; Interests: Analytic Number Theory

07-12-2012, 09:57 PM   #8
Izzy
Frau Bow
FFR Simfile Author

FFR Veteran
Join Date: Jan 2003
Location: Kansas
Age: 23
Posts: 7,652
Re: The World's Hardest Sudoku (June 2012)

Quote:
 Originally Posted by SKG_Scintill
Not solvable. You already used up all the values you have.
__________________

 07-12-2012, 10:13 PM #9 dag12 FFR Simfile Author FFR Simfile Author     FFR Veteran Join Date: Dec 2004 Posts: 468 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, 11:01 PM #10 TheSaxRunner05 The Doctor     FFR Veteran Join Date: Apr 2006 Age: 24 Posts: 3,134 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, 11:14 PM #11 dag12 FFR Simfile Author FFR Simfile Author     FFR Veteran Join Date: Dec 2004 Posts: 468 Re: The World's Hardest Sudoku (June 2012) Nevermind, got my first number. Edit: And solved by hand. Last edited by dag12; 07-13-2012 at 12:05 AM..
07-13-2012, 12:24 AM   #12
Reincarnate
x'); DROP TABLE FFR;--

FFR Veteran
Join Date: Nov 2010
Posts: 5,265
Re: The World's Hardest Sudoku (June 2012)

Quote:
 Originally Posted by iironiic Although I agree with this, I'm sure there is a logical way to tackle all Sudoku puzzles. At least, from what I have been told, Sudoku challenges you to figure out the placement of numbers using pure logic. I suppose brute forcing your way through by guess and checking works, but it's more interesting to figure out a concrete logical way to place all of the numbers in their appropriate spots.
I wrote a Sudoku solver a long while back. You can indeed solve them through logic alone, but it usually involves deeper searches that humans aren't really up for performing.

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-13-2012 at 12:28 AM..

07-13-2012, 12:29 AM   #13
dag12
FFR Simfile Author
FFR Simfile Author

FFR Veteran
Join Date: Dec 2004
Posts: 468
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:
 Originally Posted by Reincarnate I wrote a Sudoku solver a long while back. You can indeed solve them through logic alone, but it usually involves deeper searches that humans aren't really up for performing. 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.

 07-13-2012, 12:34 AM #14 Reincarnate x'); DROP TABLE FFR;--     FFR Veteran Join Date: Nov 2010 Posts: 5,265 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-13-2012, 12:43 AM #15 dag12 FFR Simfile Author FFR Simfile Author     FFR Veteran Join Date: Dec 2004 Posts: 468 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-13-2012, 12:58 AM   #16
igotrhythm
Fractals!

FFR Veteran
Join Date: Sep 2004
Location: Meesheegan
Age: 28
Posts: 5,576
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.
__________________
Quote:
 Originally Posted by Choofers jesus christ you are such an insufferable thundercunt

07-13-2012, 01:12 AM   #17
awein999
beep

FFR Veteran
Join Date: Oct 2007
Age: 22
Posts: 3,558
Re: The World's Hardest Sudoku (June 2012)

Quote:
 Originally Posted by dag12 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.
Definitely a viable strategy. Probably the intended way for it to be solved by a human. And whatever the author allows goes. I believe that's anything that doesn't involve getting any number wrong to find out information. (aka guess and check just like any other sudoku)

Edit: Verified one unique solution.
__________________
boop

 07-13-2012, 01:23 AM #18 dag12 FFR Simfile Author FFR Simfile Author     FFR Veteran Join Date: Dec 2004 Posts: 468 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, 01:38 AM #19 Choofers Bann'd FFR Simfile Author   FFR Veteran Join Date: Dec 2008 Age: 23 Posts: 6,176 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, 05:48 AM   #20
FFR Veteran

FFR Veteran
Join Date: May 2008
Posts: 1,114
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).
__________________
Quote:
 Originally Posted by Crashfan3 Man, what would we do without bored rednecks?

 Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Introductions     Newbie Forum     Chit Chat         Ask Me Anything         Birthdays         Sports         Radio     FFR Events Flash Flash Revolution Game/Site Related Forums     FFR General Talk         FFR Songs/Permissions Subforum         FFR Tournaments Subforum         FFR Difficulty Subforum     FFR Bugreport & Suggestions     Multiplayer Plaza     Spin It Up     Brag Board         Brag Board Archives     FFR Profiles Gaming     General Video Games     Music Games     Stepmania         Simulator Files Life & The Arts     32-Bit RGB     Bits and Bytes     Critical Thinking         Homework & General Information Forum     "Game" threads         The Werewolf Game     Literature     Media     Musicians' Jungle Gym

All times are GMT -5. The time now is 08:46 AM.