The World's Hardest Sudoku (June 2012)

[awein999]

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.

[SKG_Scintill]

[Reincarnate]

Yikes, that one is messy

812 753 649
943 682 175
675 491 283

154 237 896
369 845 721
287 169 534

521 974 368
438 526 917
796 318 452

[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.

[Herogashix]

Okay Rubix.

[Reincarnate]

You disagree?

[iironiic]

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.

[Izzy]

Originally Posted by SKG_Scintill

Not solvable. You already used up all the values you have.

[dag12]

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.

[TheSaxRunner05]

I would only be able to solve this by the guess and check method, and it's still questionable for me at that.

[dag12]

Nevermind, got my first number.
Edit: And solved by hand.

[Reincarnate]

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.

[dag12]

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)

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.

[Reincarnate]

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."

[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.

[igotrhythm]

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.

[awein999]

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.

[dag12]

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

[Choofers]

Put a number in a square, if it doesn't work, it's the wrong number kpCE

[UserNameGoesHere]

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).