![]() |
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. |
Re: The World's Hardest Sudoku (June 2012)
![]() |
Re: The World's Hardest Sudoku (June 2012)
Yikes, that one is messy
|
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. |
Re: The World's Hardest Sudoku (June 2012)
Okay Rubix.
|
Re: The World's Hardest Sudoku (June 2012)
You disagree?
|
Re: The World's Hardest Sudoku (June 2012)
Quote:
|
Re: The World's Hardest Sudoku (June 2012)
Quote:
|
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.
|
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.
|
Re: The World's Hardest Sudoku (June 2012)
Nevermind, got my first number.
Edit: And solved by hand. |
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. |
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:
|
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."
|
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. |
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. |
Re: The World's Hardest Sudoku (June 2012)
Quote:
Edit: Verified one unique solution. |
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... |
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
|
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). |
Re: The World's Hardest Sudoku (June 2012)
I quit.
|
Re: The World's Hardest Sudoku (June 2012)
Well, I fed the puzzle into SudokuWiki's solver, which has the added advantage of sequentially going through all the techniques humans use to solve the puzzles, one step at a time. If you've never tried this thing out it is FANTASTIC for learning new techniques or just help in general since it shows you in the puzzle where specific logical headway can be made, what the technique's name is, and a description of what's being done (and clicking the name of it on the list to the right explains in depth whats really going on).
In any case, the solver couldn't find a way to get a number in any cell, and that INCLUDES Nishio (grid coloring/guess and check). Obviously just picking numbers in cells and seeing if it works will eventually work, but if this solver doesn't find a way to make progress with Nishio, its because it takes far too many guesses to even begin using other techniques. So pretty much what other people have said in here: it can be solved somehow with some deep underlying patterns by a computer, but nothing that a human would likely be able to produce. |
Re: The World's Hardest Sudoku (June 2012)
I don't consider myself an expert in sudoku but all of what Rubix said is correct with regards to this puzzle. Most 'difficult' puzzles will at least have 4 or 5 initial numbers you can place, in addition to having more starting numbers already placed, making the number of guess-and-checks (or forks in the road if you look at it that way) a lot less than this nasty pos. I don't find these type of puzzles enjoyable since it becomes a guessing game (albeit an educated one but still).
|
Re: The World's Hardest Sudoku (June 2012)
tl;dr: This is most certainly not the world's hardest sudoku. In fact, far, far from it. This Arto Inkala guy is nobody other than a whiny attention seeker who just wants his 15 minutes of fame in the press by creating a hard sudoku and claiming it as the hardest ever.
As someone who used to be active on a sudoku forum a while back and witnessed a lot of theory as it unfolded, I'd like to share my views. I was a regular member of sudoku.com/forums (with the username 999_Springs) until the site was bought by some random people who were only interested in creating a gaming site for sudoku and other games and they were completely unaware that a forum - with several years of history - associated with the sudoku game they bought actually existed; it crashed and nobody could revive it. Not to mention that the admins and mods and stuff had long since left a rapidly declining community. Someone got together a partial backup here http://forum.enjoysudoku.com but it has a lot of stuff missing. I haven't posted for over two years, so I'll mention what I can remember. Way back when, in like 2005 or something, all the hype on sudoku forums was about whether all sudokus could be solved by a brute-force-like method of guessing a number, using a basic collection of techniques to advance the puzzle, and then claiming it as a solution if it's right and discarding the original number if it's wrong. If a puzzle can't be solved like this, that means at some stage no number placed anywhere can be proved or disproved to be true, so to make any progress, you will have to guess two numbers at the same time and see what happens. Some people thought there existed 'unsolvable' puzzles like this but finding one was hard. This Arto Inkala guy, who was active at the time (username ArtoI), made the breakthrough by finding this puzzle, which in fact was the hardest known at the time and the first ever counterexample to the conjecture: AI Escargot ![]() Ok, so he had his genuine moment of glory on the forums. However, others were working on it too and within a day or two, people were churning out harder puzzles than AI Escargot, and posting them. ArtoI responded by quitting the forums instantly, without a trace or goodbye post or anything, and sent the puzzle to the press. He got his unfair share of the limelight. Nobody really cared. This was 7 years ago. Fast forward 7 years and Arto Inkala comes up with a new puzzle, as the OP suggests. This is only marginally harder than AI Escargot. However, during that time people have advanced sudoku creation methods massively, and now not only is this not the hardest puzzle ever, but it won't make a dent on the radar of anybody's hardest list by any method of rating whatsoever. One person has, as of last month, amassed 400000+ puzzles rated harder than this by SE rating (see below). However, ArtoI decided to be a greedy bastard and take his half-baked work to the press and publish it. I have zero respect for this guy, and none of you should have any respect for him either. He is essentially boycotting the whole sudoku community and dishonestly taking all the credit that the community deserves for himself. It's extremely hard to state this too harshly - if he had any sense of humility or empathy he would care to realise how much hard work goes into creating new algorithms for finding hard sudokus, but he is cold, arrogant and selfish. That is all I have to say about him. The rest of this post is a bit of technical background. Rating sudokus by difficulty Terminology Different types of chains, according to SE Relative difficulty of this puzzle vs others An alternative view of forcing chains Fin cells and crap like that Relevance to human solving How much spare time did I have this afternoon? |
Re: The World's Hardest Sudoku (June 2012)
Quote:
|
Re: The World's Hardest Sudoku (June 2012)
I reiterate what I said earlier about brute-force solving of sudoku's based on guess-and-check: not nearly as fun as puzzles solved purely by logic and more a waste of time if anything. I get way more out of time-trialing intermediate/hard sudoku puzzles than going through possible chains until finding a contradiction for those stupid hard ones.This is just my opinion of course hehu
|
Re: The World's Hardest Sudoku (June 2012)
Quote:
|
Re: The World's Hardest Sudoku (June 2012)
no idea that sudoku could get this involved!!
Quote:
|
Re: The World's Hardest Sudoku (June 2012)
Quote:
|
Re: The World's Hardest Sudoku (June 2012)
Guess and check = guess a number and try to solve.
Logic = guess a number and try to solve in your head. The only difference is that with logic you don't get a paper full of eraser residue. |
Re: The World's Hardest Sudoku (June 2012)
Quote:
There aren't any precise definitions anywhere of what constitutes solving logically and what is guess-and-check. Your definition is as good as any. (Though having a "definition" that depends on your mental capacity isn't exactly ideal) However, part of the ambiguity lies in the fact that there's no consensus on whether the whole point of sudoku is to prove that there is a unique solution, or whether given a unique-solution puzzle to find it. In the former case, when you guess a number and it gets to a solution you have to discard it. Quote:
WHAT DO YOU DO NOW, HUH? :P also try this one for size, just discovered last week, and there is a clever one-step logical solution but if you really want to brute force it go ahead Code:
...|.5.|7..http://www.youtube.com/watch?v=KlyXNRrsk4A#t=86s |
Re: The World's Hardest Sudoku (June 2012)
lol |
Re: The World's Hardest Sudoku (June 2012)
ironically, we have Sudoku puzzles as supplementary exercises to do after we're done with the course material
it's supposed to teach us logic and how to implement that logic into algorithms, whether it's mathematical algorithms we figure out on paper or something we write in a scripting language (bash, powershell, etc), as well as how to look for certain patterns (oddly this has helped me see patterns in complex subnetting, routing tables, and registry settings when it comes to ad schema) So I'm gonna try tackling this puzzle, fuck lunch xd (ps bump) |
Re: The World's Hardest Sudoku (June 2012)
sudoku is rly fun
|
Re: The World's Hardest Sudoku (June 2012)
one thing i like is how some random guy on the enjoy sudoku forums stumbled upon this thread earlier this year in mid-january and now it's the go-to link on the sudoku forums to point newcomers who join over there asking whether it's actually the hardest sudoku, even though these forums have nothing to do with sudoku, i hadn't posted there in over 2 years, and i don't have sources for anything
also one thing i hadn't in fact posted earlier in this thread is an actual solution path. i'll try to get that done |
Re: The World's Hardest Sudoku (June 2012)
do you have a list of good sudokus for intermediate peeps who just bruteforce most of the time?
|
Re: The World's Hardest Sudoku (June 2012)
Only that you should stay away from Wayne Gould's "fiendish" collection. I had a book of "brown belt" puzzles a while back that felt just right. Ended up solving all 300 of them.
|
Re: The World's Hardest Sudoku (June 2012)
I don't know which difficulty level you're at specifically but here are a few resources
menneske.org - millions of puzzles that go from "super easy" to "impossible" Andrew Stuart's daily sudoku - gentle/moderate/tough/diabolical/extreme Andrew Stuart's weekly sudoku vanhegan's sudoku site - easy to fiendish/extreme Daily Telegraph - British right-wing newspaper that occasionally has surprisingly(!) good sudoku puzzles As a rough difficulty guide: menneske's "Impossible", vanhegan's "Fiendish", the Torygraph's "Diabolical" and Andrew Stuart's daily "Diabolical" are around the stage where you start branching out from pattern based techniques into chains. SE ~7 vanhegan's "Extreme" are harder but only by a little bit. Andrew Stuart's daily "Extreme" are harder still, like SE 8+ Andrew Stuart's weekly unsolvables are entering obnoxious territory, SE 9+ igotrhythm: Wayne Gould (I think) still sticks to his 2005 mentality that sudokus should all be doable with pairs/triples and x-wings. That worked back in 2005 when they were pretty much the only techniques around, but that's no longer the case. At least you can say his puzzles don't suffer from rating inflation then. :P When did you get his book? and finally, run like hell away from sudoku.com, the first puzzle it gave me had 15 clues and so obviously had multiple solutions |
Re: The World's Hardest Sudoku (June 2012)
ok so x-wing is an actual term
I learned about x-wings, y-wings, hidden/naked pairs/triples, and line-block intersection are there otheres that I should learn about lol |
Re: The World's Hardest Sudoku (June 2012)
Quote:
I think there are 12x12 sudoku now, those are really fun. |
Re: The World's Hardest Sudoku (June 2012)
choofers: that's a pretty nice set of techniques you know already, you should be able to do basically every puzzle that has or ever will be published in a newspaper or book with what you know. if you want to learn something new, i suggest some guy's tutorial called Strong Links For Beginners which describes the technique known variously as "2 strong links", "turbot fish", "2-string kite", "skyskraper", etc. be warned that it's written in a slightly patronising way on purpose. by the way you may like to know the 3x3 extension of an x-wing is called a "swordfish"
igotrhythm: the thing is sudoku books tend not to over-reach in terms of difficulty because they're supposed to be accessible to the general public who have usually not progressed beyond all-singles puzzles, and that's to boost sales. i'd recommend you check that the puzzles actually have a unique solution before you solve them, from what you said i think it's more likely that the puzzles are flawed rather than being too hard. i may be wrong though. also i miss borders, shame about it going bankrupt :( anything over 9x9 is too much damn hard work |
Re: The World's Hardest Sudoku (June 2012)
considering the number of clues there and this video
the "hardest puzzle" claim is fucking laughable hahaha |
Re: The World's Hardest Sudoku (June 2012)
"Hardest" doesn't have much to do with the number of clues. Some of the 17-clue puzzles are quite straightforward.
|
Re: The World's Hardest Sudoku (June 2012)
i'm not sure what you mean by that. in general there's not really a correlation between how many clues a puzzle has and how hard they are, unless you're secretly a computer bot who only solves sudokus by brute force, in which case solving 17 clue puzzles would definitely be harder for you than (say) AAAing vertex beta vrofl or something.
hardest sudokus today typically range in the 22-24 clues region. that's just because there happen to be more minimal (i.e. you can't remove a clue and get another valid puzzle) sudokus within that clue range. in fact, some random guy did an analysis of rating over clues for minimal puzzles and they got that minimal puzzles get a little bit harder when they've got more clues. nobody knows why, though! i have no idea how hard the hardest 17 is, but i'd be surprised if it's like a mid-9 or higher here's a nice ridiculously hard 49 clue puzzle for your enjoyment Code:
795|6..|8.. |
Re: The World's Hardest Sudoku (June 2012)
thats interesting as fuck and i didnt know that. thank you for bringing to light my ignorance
|
Re: The World's Hardest Sudoku (June 2012)
Alright, so I finally solved this damn thing. Have a look at my solution path if you're interested/stuck/bored. By bored I mean VERY bored.
Warning: contains spoilers. That's it. Thread over. You can all go home now. |
Re: The World's Hardest Sudoku (June 2012)
wow zap nice one minute waltz
|
Re: The World's Hardest Sudoku (June 2012)
Quote:
|
| All times are GMT -5. The time now is 11:19 PM. |
Powered by vBulletin® Version 3.8.1
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
Copyright FlashFlashRevolution