Flash Flash Revolution: Community Forums

Flash Flash Revolution: Community Forums (http://www.flashflashrevolution.com/vbz/index.php)
-   Critical Thinking (http://www.flashflashrevolution.com/vbz/forumdisplay.php?f=33)
-   -   The World's Hardest Sudoku (June 2012) (http://www.flashflashrevolution.com/vbz/showthread.php?t=124807)

awein999 07-12-2012 05:48 PM

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.

SKG_Scintill 07-12-2012 07:11 PM

Re: The World's Hardest Sudoku (June 2012)
 

Reincarnate 07-12-2012 07:15 PM

Re: The World's Hardest Sudoku (June 2012)
 
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 07-12-2012 07:43 PM

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.

Herogashix 07-12-2012 07:47 PM

Re: The World's Hardest Sudoku (June 2012)
 
Okay Rubix.

Reincarnate 07-12-2012 07:52 PM

Re: The World's Hardest Sudoku (June 2012)
 
You disagree?

iironiic 07-12-2012 09:08 PM

Re: The World's Hardest Sudoku (June 2012)
 
Quote:

Originally Posted by Reincarnate (Post 3724901)
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 07-12-2012 09:57 PM

Re: The World's Hardest Sudoku (June 2012)
 
Quote:

Originally Posted by SKG_Scintill (Post 3724889)

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

dag12 07-12-2012 10:13 PM

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.

TheSaxRunner05 07-12-2012 11:01 PM

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.

dag12 07-12-2012 11:14 PM

Re: The World's Hardest Sudoku (June 2012)
 
Nevermind, got my first number.
Edit: And solved by hand.

Reincarnate 07-13-2012 12:24 AM

Re: The World's Hardest Sudoku (June 2012)
 
Quote:

Originally Posted by iironiic (Post 3724945)
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 07-13-2012 12:29 AM

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 (Post 3725060)
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 07-13-2012 12:34 AM

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

dag12 07-13-2012 12:43 AM

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.

igotrhythm 07-13-2012 12:58 AM

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.

awein999 07-13-2012 01:12 AM

Re: The World's Hardest Sudoku (June 2012)
 
Quote:

Originally Posted by dag12 (Post 3725076)
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 07-13-2012 01:23 AM

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

Choofers 07-13-2012 01:38 AM

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

UserNameGoesHere 07-14-2012 05:48 AM

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

rushyrulz 07-14-2012 10:42 AM

Re: The World's Hardest Sudoku (June 2012)
 
I quit.

Dark_Chrysalis 07-15-2012 04:44 AM

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.

Dynam0 11-16-2012 09:29 PM

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

Zapmeister 12-10-2012 02:19 PM

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

Obviously sudoku rating isn't objective. There are several ways to rate sudokus and none of them will agree with each other entirely. Some will rate according to perceived difficulty by humans; others will rate according to perceived difficulty by brute-force; others will start with a base of advanced strategies or even a generalised method of solving all sudokus (see below) and base a rating off that. I'm going to focus on a program called Sudoku Explainer 1.2.1, abbreviated to SE, available here: http://diuf.unifr.ch/people/juillera/Sudoku/Sudoku.html

Why Sudoku Explainer? Well, its main advantage is that it can solve everything. If a puzzle is very very hard, it just keeps nesting forcing chains inside each other until it finds a move, (i.e. take a guess, and if it goes nowhere take another guess inside and see that the second guess leads to a contradiction, go back to the situation from the first guess and repeat) which is extremely time-consuming, but at least it does what it does. It uses chain-based methods to solve puzzles, which is basically what most of you have been talking about in this thread, and they are intuitively what a human would do when faced with such a puzzle. It's also 'logical', in the same way that Reincarnate mentioned, i.e. algorithmically solved but intractable for humans. As a result, its final rating - although it seems sort of arbitrary to assign a numerical value to the length and type of a forcing chain and rate the puzzle according to the 'hardest' chain needed to solve it - agrees very closely with human intuition, so it is in fact the most commonly used method of rating. (Sort of like how FFR songs are rated by human judgement.) Other solvers like SudokuWiki, which Dark_Chrysalis linked to, can't solve anything above SE high-8 or low-9, which is basically pathetic - this doesn't even come remotely close to the 'unsolvables' defined earlier. That's because it was intended to be a demonstration of how humans use mainly pattern-based techniques to do puzzles, not how to 'logically' solve literally everything.

(Note: Don't use SE to rate easy sudokus. It is absolutely awful at the lower end of the rating scale. It tries to do it according to an approximation of human intuition and fails spectacularly. I'd recommend SudokuWiki, or literally everything else. The GUI is full of bugs and spelling errors too.)


Terminology

I'm going to number the rows from top to bottom and the columns from left to right. Little squares are called cells. To identify a cell write its row and column number in the forum rXcY, so r1c9 would be top-right. To identify multiple cells in a row/column, say, r1c789 would mean r1c7 and r1c8 and r1c9. The possibilities for each cell are called candidates. The solved numbers are called clues.


Different types of chains, according to SE

What's a chain? Loosely speaking it's a structure in a puzzle where you start somewhere and keep going around it until you get a contradiction. Some of the smaller ones are instantly recognisable as patterns, but as they get bigger they start to look like guess-and-check methods (but there is another way of viewing these things - see later).

The simplest kind (SE 6.5-7.5): You start with a number and move on. Each step depends only on the previous step. At the end you contradict what you started with.

Code:

*--------------------------------------------------------------------------------*
| 25      9      45      | 1      6      3        | 7      24      8        |
| 236    36      8        | 7      4      5        | 26      9      1        |
| 167    467    1467    | 8      2      9        | 3      46      5        |
|--------------------------+--------------------------+--------------------------|
| 9      346    346      | 5      1      8        | 24      7      23      |
| 17      8      147      | 3      9      2        | 14      5      6        |
| 135    2      135      | 6      7      4        | 18      138    9        |
|--------------------------+--------------------------+--------------------------|
| 367    3567    9        | 4      8      67      | 1256    1236    23      |
| 8      1      367      | 2      5      67      | 9      36      4        |
| 4      56      2        | 9      3      1        | 568    68      7        |
*--------------------------------------------------------------------------------*
if r7c8 is 2, then r7c9 isn't 2, so r4c9 is 2 and not 3, so r6c8 is 3 and not 1,
so r7c8 is 1, a contradiction.

I'll make all the diagrams pictures if necessary.

Nishio forcing chains (SE 7.6-8.1): Just as Dark_Chrysalis said - chains that can backtrack along themselves - but only involve one number. They're old-fashioned and have been subsumed by fish-type methods (read on).

Code:

+-------------------+-------------------+-------------------+
 | 1    467  27    | 24    9    246  | 8    3    5    |
 | 28    9    5    | 3    7    268  | 4    12    126  |
 | 248  468  3    | 1248  16    5    | 7    29    269  |
 |-------------------+-------------------+-------------------|
 | 347  5    78    | 6    234  9    | 1    248  234  |
 | 6    2    19    | 14    8    34    | 5    7    349  |
 | 34    148  189  | 5    1234  7    | 6    2489  2349  |
 |-------------------+-------------------+-------------------|
 | 278  178  1278  | 9    46    468  | 3    5    14    |
 | 9    3    4    | 7    5    1    | 2    6    8    |
 | 5    18    6    | 248  34    2348  | 9    14    7    |
 +-------------------+-------------------+-------------------+

if r9c6 is 4, then r9c8 and *r5c6 aren't 4, then r7c9 is 4, then r5c4 is 4
(using *), then r13c4 aren't 4, then r1c6 is 4, so r9c6 isn't 4, a contradiction.

(this does nothing but I can't be bothered with finding a better example) You can see where the chain goes back on itself to advance.

Region/Cell forcing chains (SE 8.2-8.7): With region forcing chains, you start from a row/column/block and consider all possibilities of a certain number to arrive at a common conclusion. With cell chains you start with all possibilities for a cell. Individual chains don't backtrack.
Code:

    1      2    59 |    3  4789  45678 |  4678    489  6789
    4    789    39 |  2689  2789    678 |    5  1389  16789
  3789    5789      6 |  589      1  4578 |  3478      2    789
----------------------+---------------------+---------------------
    5    149  12349 |  128      6  1348 |  238      7    128
  236    146      8 |    7    234  1345 |    9    135  1256
  2367    167    123 |  1258    238      9 |  2368  1358      4
----------------------+---------------------+---------------------
  289      3  1249 |  189      5    178 |  2478      6  2789
  2689    5689      7 |    4    389    368 |    1    589  2589
  689  145689  1459 |  1689    789      2 |  478  4589      3

if r1c6 is 5, then r1c3 isn't 5, then r9c3 is 5, so r9c8 isn't 5.
if r3c4 is 5, then r6c4 isn't 5, then r6c8 is 5, so r9c8 isn't 5.
if r3c6 is 5, then r3c7 is 4, then r1c8 isn't 4, then r9c8 is 4 and not 5.
Therefore r9c8 isn't 5 regardless of where 5 is in block 2.

Dynamic forcing chains (SE 8.7-9.5): Chains that go back on themselves. Like nishio, but not just restricted to one number.

Code:

45689      1  456789 |  689  3689      2 |  3479  3479    378
    3  2789  26789 |    4  1689    167 |  1279    279      5
  489  2789  24789 |    89      5    137 | 123479      6  12378
----------------------+---------------------+----------------------
    2    389    3689 |    7  3469      5 |    346      1    36
  569  3579      1 |  269  23469    346 |      8  23457  2367
    56      4    3567 |    1    236      8 |  23567  2357      9
----------------------+---------------------+----------------------
 14589      6  234589 |  258      7    14 |  12359  2359    123
    7  2358    2358 |  2568  1268      9 |  12356    235      4
  1459    259    2459 |    3  1246    146 | 125679      8  1267

if r8c7 is 2 or 3 or 5, then r8c5 is 1, then r7c6 and *r9c6 aren't 1, then r7c6
is 4, then r9c6 is 6 (using *), then r8c45 aren't 6, so r8c7 is 6, a contradiction.

(These can be very very long, I just picked a very very short example)

Dynamic forcing chains (+) (SE 9.3-10.1): Chains that require additional techniques inside the chain to advance it, like pairs and stuff. Again, can be very long.

Code:

+--------------------------------------------------------------------------------+
 |  6      4789    2      |  14789  5      479    |  1389    179    39      |
 |  1789    5789    15789  |  1789    169    3      |  1689    4      2      |
 |  13789  4789    13489  |  14789  1469    2      |  1689    15679  569    |
 |--------------------------+--------------------------+--------------------------|
 |  4      3      5679    |  1579    2      8      |  169    1569    569    |
 |  789    1      56789  |  34579  349    45679  |  2      3569    48      |
 |  289    25689  5689    |  13459  1349    4569    |  7      13569  48      |
 |--------------------------+--------------------------+--------------------------|
 |  5      4689    134689  |  2      7      149    |  3469    69      369    |
 |  279    24679  4679    |  3459    349    459    |  4569    8      1      |
 |  139    49      1349    |  6      8      1459    |  3459    2      7      |
 +--------------------------------------------------------------------------------+

if r1c6 is 7, then r1c8 isn't 7, then r3c8 is 7, then r3c9 is 5, then the 6 in
block 3 is locked to column 7, then the 6 in block 9 is locked to row 7, and
then you have a triple 489 in r379c2, so r1c2 is 7, so r1c6 isn't 7.

(The puzzle suddenly becomes very easy after this hard-to-find move.)

Nested forcing chains (SE 10.0-10.9): Where you have a chain nested inside another one. These puzzles correspond to the 'unsolvables' I mentioned earlier where you have to basically guess twice. These can be very very long and short ones only ever occur in fabricated puzzles like this one.

Code:

    8      7      5 |    6      9    134 |  1234  1234  1234
    6      2    34 |    5    134      7 |    9    134      8
    34      1      9 |    34      2      8 |    5      6      7
---------------------+---------------------+---------------------
    7      8    123 |    9    134  1234 |  1234      5      6
    9      4    123 |  123      5      6 |    7      8    123
  123      5      6 |    7      8  1234 |  1234  1234      9
---------------------+---------------------+---------------------
    5      6    124 |    8      7  1234 |  1234      9  1234
  124      9      8 |  1234    134      5 |    6      7  1234
  124      3      7 |  124      6      9 |    8    124      5

if r9c4 is 4, then r3c4 isn't 4, then r3c1 is 4, so r8c1 isn't 4.
if r9c4 is 1, then r5c4, r8c45 and r9c1 all aren't 1. this creates a nested
forcing chain (turbot fish) involving 1 in the cells r5c39, r7c3, r8c19 which
forces r8c9 to also not be 1 (left as an exercise for the reader), so r8c1 is 1.
if r9c4 is 2, then r8c1 is 2 by the same as above replacing 1 with 2.
Therefore regardless of the value of r9c4, r8c1 isn't 4.

(Aside note: Although this already has 50 clues, it is still not solvable with chains up to dynamic(+) making it harder than anything ever published before AI Escargot and it will kill almost all online solvers. This goes to show that the number of clues in a puzzle doesn't say anything about difficulty.)

Nested region/cell forcing chains (SE 10.9-11.4): Like the above but you need region/cell chains nested inside the main chain. So if you guess any number you will need at least 8.2 rate to get a contradiction. No point giving a real example because the code will drag on for pages and pages.

Nested dynamic forcing chains (SE 11.4-???): Like the above with dynamic forcing chains nested inside the main chain. So if you guess any number you will need at least 8.7 rate to get a contradiction.

(By the way the numbers are really not supposed to mean anything in absolute terms. They're just arbitrarily assigned to each chain. You only use them to compare puzzles to each other to see which one is harder.)


Relative difficulty of this puzzle vs others

What is the difficulty level of the puzzles in question? In 2005, before AI Escargot was discovered, the hardest puzzle was the so-called "top1465 #77"
Code:

7..|...|4..
.2.|.7.|.8.
..3|..8|..9
---+---+---
...|5..|3..
.6.|.2.|.9.
..1|..7|..6
---+---+---
...|3..|9..
.3.|.4.|.6.
..9|..1|..5
top1465 #77
SE 9.8

which is painful to solve by dynamic(+) but still can be done.

AI Escargot - the puzzle that got whats-his-face his initial (probably sort-of deserved) fame - is rated a 10.5. Puzzles around this region are plentiful enough by today's standards that if a hardest puzzle search came up with one of these it would go in the bin and not even be recorded. Arto Inkala's new puzzle is a 10.6 or 10.7 (I can't remember and I'm not bothered enough to rate it again). Still not necessary to use nested region/cell or dynamic chains. I'm surprised nobody in this thread has showed surprise as to whether this puzzle is in fact the end of the line for sudokus since you can brute force solve it in a few hours. Here is a selection of some harder puzzles hand-picked by myself for your enjoyment (if you are a masochist):

Code:

...|..1|.2.
3..|.4.|5..
...|6..|..7
---+---+---
..2|...|..1
.8.|.9.|.3.
4..|...|8..
---+---+---
5..|..2|...
.9.|.3.|4..
..6|7..|...
Ocean's New Year's present for RW
SE 11.4

1..|...|..2
.9.|4..|.5.
..6|...|7..
---+---+---
.5.|9.3|...
...|.7.|...
...|85.|.4.
---+---+---
7..|...|6..
.3.|..9|.8.
..2|...|..1
Easter Monster
SE 11.6 (not hardest by SE but a lot of other rating programs point to this
being the hardest known puzzle)

...|...|.39
...|..1|..5
..3|.5.|8..
---+---+---
..8|.9.|..6
.7.|..2|...
1..|4..|...
---+---+---
..9|.8.|.5.
.2.|...|6..
4..|7..|...
Golden Nugget
SE 11.9 (highest known)

1..|...|..7
.2.|4..|.6.
..3|...|5..
---+---+---
.9.|.4.|...
...|.62|.4.
...|9..|8..
---+---+---
..5|...|..3
.6.|2..|.8.
7..|..1|...
Silver Plate
SE 11.5

6..|..2|.59
52.|.4.|.1.
..3|5..|2..
---+---+---
3..|194|5..
.1.|658|.3.
..5|273|..1
---+---+---
..4|..5|1..
.3.|.2.|.45
75.|4..|..8
Mauricio's 37-clue
SE 11.2

12.|3..|...
4..|...|3..
..3|.5.|.2.
---+---+---
6..|.7.|.8.
..2|1..|4..
...|..2|..6
---+---+---
.7.|.8.|.9.
..4|7..|5..
...|..9|..7
a completely random non-special 11.2 discovered two days ago fresh off the frying pan
SE 11.2

So yeah, have fun with all those. I haven't had a go at most of them but if you can even brute-force these within a few hours I'd be impressed. (But not the 37-clue 11.2. That's brute-forceable if you're keen enough.) It's hard to stress enough that ArtoI's pile of rubbish pales in comparison to all these. Ok, I've said it enough times.

(By the way I have deliberately chosen not to include any puzzles named after different types of food because there are far too many of them and I'm not hungry.)


An alternative view of forcing chains

Ok, so some of you are probably thinking about whether doing all this forcing chain malarkey counts as logic or not because you're essentially guessing. Certainly if you're trying to prove that a puzzle has a unique solution you can just brute-force chains and stuff until you get a contradiction similarly to what SE is doing, but there is another way to think about chains which although is logically equivalent, it's a lot more ... how do I say this... aesthetically pleasing? I don't know. It makes chains not look like trial-and-error, let's say.

Define a sector to be a collection of candidates such that one - and only one - of them are true. Naturally, in a sudoku puzzle, you'll find 4 types of these: all candidates in a single cell; and all instances of a single number in a row, column, and block.

Call a collection of non-overlapping sectors in a puzzle the base, and each sector a base sector. Now suppose you got the same collection of candidates in the base, and found a different set of non-overlapping sectors to cover them all. That set of sectors is called the cover, and each sector a cover sector. Now here's the thing. If you had N non-overlapping base sectors, then you'd need exactly N candidates to be true in the base. If you had them all covered by N cover sectors, then you'd need exactly N candidates to be true in the cover. But you've already found N of them in the base. Therefore: Every candidate in each of the N cover sectors that is not in each of the N base sectors is a lie.

Here are some examples.
Code:

*-------------------------------------------------------------------------*
 | 134578  3478    1458  | 268    24678  26    | 4679  25    245679  |
 | 457    6      2      | 9      47      3      | 1      8      457    |
 | 478    9      48    | 5      24678  1      | 467    3      2467    |
 |------------------------+------------------------+-----------------------|
 | 59      1      7      | 3      569    8      | 2      4      69      |
 | 234589  348    4589  | 26      1      2569  | 69    7      3689    |
 | 2389    38      6      | 4      29      7      | 5      1      389    |
 |------------------------+------------------------+-----------------------|
 | 168    5      18    | 7      268    4      | 3      9      12      |
 | 479    2      3      | 1      59      59    | 8      6      457    |
 | 146789  478    1489  | 268    3      2569  | 47    25    12457  |
 *-------------------------------------------------------------------------*
2 base sectors: all of the 2s in rows 3 and 7
2 cover sectors: all of the 2s in columns 5 and 9
eliminations: r1c5, r6c5, r1c9, r9c9 aren't 2

This is the simplest possible example and you might know the pattern as an X-Wing.

Code:

*--------------------------------------------------------------------------------*
| 16      68      1569    | 25      3      7        | 4      2689    26      |
| 4      38      35      | 25      9      6        | 2378    1      237      |
| 7      2      369      | 1      4      8        | 369    69      5        |
|--------------------------+--------------------------+--------------------------|
| 8      4      13      | 6      5      9        | 23      7      123      |
| 169    369    7        | 38      2      4        | 3568    568    136      |
| 2      5      36      | 38      7      1        | 368    4      9        |
|--------------------------+--------------------------+--------------------------|
| 5      69      4        | 7      1      2        | 69      3      8        |
| 39      1      8        | 4      6      35      | 2579    259    27      |
| 36      7      2        | 9      8      35      | 1      56      4        |
*--------------------------------------------------------------------------------*
4 base sectors: 7s in block 3, 8s in block 3, 2s in column 8, and candidates in r8c9
4 cover sectors: candidates in r2c7 and r1c8, 7s in column 9, 2s in row 8
eliminations: r2c7 isn't 2 or 3, r8c7 isn't 2, r1c8 isn't 6 or 9

Slightly harder. Check that all the candidates in the base are covered by the cover. You can view each elimination as a simple forcing chain if you assume it's true and go round the base sectors one at a time.

Code:

    7    126        8 |  459  4569    4569 |    3  1456  1259
  469      36    3469 |    2  34569      1 |  4679  45678  5789
    5    1236  123469 |    78  3469      78 | 12469    146    129
------------------------+----------------------+---------------------
  189      4    1579 |  3579    59    3579 |  178      2      6
    3    1267    12679 |  479      8  24679 |  147  1457    157
  268    2567    2567 |    1  2456  24567 |  478      9      3
------------------------+----------------------+---------------------
    12      9    12357 |    6    125    2358 |  127  1378      4
  1246      8    12346 |  349      7    2349 |    5    136    129
  1246  123567  1234567 | 34589  12459  234589 | 12679  13678  12789

8 base sectors: all the candidates in r2c12357 and r7c157
8 cover sectors: 3469 in row 2, 12 in row 7, 5 in column 5, 7 in column 7
eliminations: 5r1c5, 5r4c5, 5r6c5, 5r9c5, 7r4c7, 7r5c7, 7r6c7, 7r9c7, 46r2c8,
9r2c9, 12r7c3, 2r7c6, 1r7c8

This one cannot be easily written as a chain, but it's easily written as base/cover format. And it kills the puzzle. You just have to step back and admire. (This pattern is also known as the almost-locked-set doubly-linked rule.)

Code:

+----------------------+----------------------+----------------------+
 | 1      478    3458-7 | 3567  3689  5678  | 3489  369    2      |
 | 238    9      378    | 4      126-38 1267-8 | 138    5      368    |
 | 3458-2 248    6      | 1235  12389  1258  | 7      139    3489  |
 +----------------------+----------------------+----------------------+
 | 2468  5      1478  | 9      1246  3      | 128    1267  678    |
 | 234689 126-48 13489  | 126    7      1246  | 123589 126-39 35689  |
 | 2369  1267  1379  | 8      5      126    | 1239  4      3679  |
 +----------------------+----------------------+----------------------+
 | 7      148    4589-1 | 1235  12348  12458  | 6      239    3459  |
 | 456    3      145    | 1267-5 126-4  9      | 245    8      457    |
 | 4589-6 468    2      | 3567  3468  45678  | 3459  379    1      |
 +----------------------+----------------------+----------------------+
16 base sectors: all the candidates in r1c28, r2c1379, r3c28, r7c28,
r8c1379, r9c28
16 cover sectors: 48 in column 2, 27 in block 1, 38 in row 2, 16 in block 3
and I can't be bothered typing out the others
eliminations: everything after the minus signs

This is the classic. The one that started it all. And yes, that is the Easter Monster puzzle. This particular pattern of 16 cells in 4 blocks is known as the SK loop. SK stands for the username of the guy who popularised it. It's surprisingly more common than you might think, but I've never had to use it all that often.
After the loop the puzzle drops to SE 10.7, which is actually sort of doable; but then again, SE doesn't have this sort of stuff encoded because it's a very old solver.


Fin cells and crap like that

You can extend this sort of logic in a rather powerful way to the following: Suppose your cover sectors don't quite cover your base, but leave just a few base candidates outstanding. Then you can still do the eliminations, but only on all the candidates in the cover-not-base that can see (i.e. make false) all the extra base candidates. This gives you a lot more freedom. Since I can't be bothered to find new examples I'll just re-use old ones.

The extra base candidates are usually called fins, but everyone calls them whatever the hell they want to.
Code:

    9      3      8 |    2    15      4 |    67    15    67
    4      2      6 |    35      7  1359 |  1359    135      8
    7      1      5 |    6    39      8 |  349      2    349
---------------------+---------------------+---------------------
    6      7      4 |    1    359    359 |    39      8      2
    1      8    39 |    7      6      2 |  3459    345    349
    2      5    39 |    4      8    39 |    16      7    16
---------------------+---------------------+---------------------
    8      9      2 |    35    135      6 |  1347    134  1347
    3      6      1 |    8      4      7 |    2      9      5
    5      4      7 |    9      2    13 |    8      6    13
2 base sectors: 9s in rows 2 and 4
2 cover sectors: 9s in columns 6 and 7
fin: r4c5
elimination: 9r6c6

That's called a finned X-wing. Once upon a time it was called a Filet-O-Fish, but they changed the name after McDonald's sued them for copyright. One-half of the last sentence is false.

The whole "fish" malarkey refers to the fact that it's a lot easier to find base/cover sectors and understand what is going on if all the sectors only have one number in them. That's why Nishio is out of date. Why "fish"? It's an extension of the fact that the guy who discovered the 3x3 closed circuit way back when (like the X-Wing but with three rows/columns) called it a swordfish. Nobody knows what he was thinking. But this spawned a whole genre of different types of single-number techniques named after aquatic creatures which quickly stopped being funny.

Here's an example (the same as the nishio one above)
Code:

+-------------------+-------------------+-------------------+
 | 1    467  27    | 24    9    246  | 8    3    5    |
 | 28    9    5    | 3    7    268  | 4    12    126  |
 | 248  468  3    | 1248  16    5    | 7    29    269  |
 |-------------------+-------------------+-------------------|
 | 347  5    78    | 6    234  9    | 1    248  234  |
 | 6    2    19    | 14    8    34    | 5    7    349  |
 | 34    148  189  | 5    1234  7    | 6    2489  2349  |
 |-------------------+-------------------+-------------------|
 | 278  178  1278  | 9    46    468  | 3    5    14    |
 | 9    3    4    | 7    5    1    | 2    6    8    |
 | 5    18    6    | 248  34    2348  | 9    14    7    |
 +-------------------+-------------------+-------------------+
3 base sectors: 4 in row 5 and blocks 2 and 9
3 cover sectors: 4 in columns 4, 6 and 9
fin: r9c8
elimination: r9c46 aren't 4

"Finned Mutant Swordfish" (don't ask)

And most other chains can easily be written like this too. Here's the first example rewritten
Code:

*--------------------------------------------------------------------------------*
| 25      9      45      | 1      6      3        | 7      24      8        |
| 236    36      8        | 7      4      5        | 26      9      1        |
| 167    467    1467    | 8      2      9        | 3      46      5        |
|--------------------------+--------------------------+--------------------------|
| 9      346    346      | 5      1      8        | 24      7      23      |
| 17      8      147      | 3      9      2        | 14      5      6        |
| 135    2      135      | 6      7      4        | 18      138    9        |
|--------------------------+--------------------------+--------------------------|
| 367    3567    9        | 4      8      67      | 1256    1236    23      |
| 8      1      367      | 2      5      67      | 9      36      4        |
| 4      56      2        | 9      3      1        | 568    68      7        |
*--------------------------------------------------------------------------------*
3 base sectors: 1 in column 8, 3 in block 6, 2 in column 9
3 cover sectors: cells r4c9, r6c8, r7c8
fin: 2r7c9
elimination: 2r7c8

and here's one of the harder ones
Code:

+--------------------------------------------------------------------------------+
 |  6      4789    2      |  14789  5      479    |  1389    179    39      |
 |  1789    5789    15789  |  1789    169    3      |  1689    4      2      |
 |  13789  4789    13489  |  14789  1469    2      |  1689    15679  569    |
 |--------------------------+--------------------------+--------------------------|
 |  4      3      5679    |  1579    2      8      |  169    1569    569    |
 |  789    1      56789  |  34579  349    45679  |  2      3569    48      |
 |  289    25689  5689    |  13459  1349    4569    |  7      13569  48      |
 |--------------------------+--------------------------+--------------------------|
 |  5      4689    134689  |  2      7      149    |  3469    69      369    |
 |  279    24679  4679    |  3459    349    459    |  4569    8      1      |
 |  139    49      1349    |  6      8      1459    |  3459    2      7      |
 +--------------------------------------------------------------------------------+
9 base sectors: cells r1c6 and r1379c2, 567 in block 3, 6 in block 9
9 cover sectors: 489 in column 2, 7 in rows 1 and 3, cells r3c89, 6 in column 7
and row 7
(ok these two overlap but you can check that it doesn't matter)
fins: 4 and 9 in r1c6
elimination: 7r1c6



Relevance to human solving

As you can see, this is a powerful extension of chain techniques that makes them look less trial-and-error-flavoured and more versatile. In fact, it has more extensions, like you can consider exactly what happens when two sectors overlap and what happens when you have more cover sectors than base ones, but this gets very, very, VERY technical and complicated extremely quickly and has little relevance to manual solving. Also, nobody in their right mind will mentally look for base and cover sectors. (exception: with nishio it isn't in fact too tedious) As a human player, it is far, far easier to visualise as a chain: just start somewhere and keep going until you find a contradiction. Yet these two methods amount to the same thing. In fact, when you get to the really hard SE 10+ puzzles, there are in fact some people who can do this. No idea how, but I sort of envy them. There are other strategies to doing ultra-hard stuff like the Exocet and multi-fish pattern which I don't really understand but can provide some gateway in a future post if you're interested and I have far too much time on my hands.

Can every long chain be described in terms of base/cover sectors? To be honest, I don't know, but I'm pretty sure the answer's no, but you can easily add extensions to all this theory to make it universal, but that is mind-numbingly boring.

Conclusion: Happy solving, and remember every time you find a long chain, you don't need to feel guilty that you're doing trial-and-error. You probably aren't. (Though "trial-and-error" isn't well-defined. But let's not go there.)


How much spare time did I have this afternoon?

Far too much. By the way, I sort of quit sudoku around when this technical stuff was being developed, so I know this sort of sounds vague in places but precision is not what I care about anymore.

Tidus810 12-10-2012 03:22 PM

Re: The World's Hardest Sudoku (June 2012)
 
Quote:

Originally Posted by Zapmeister (Post 3816021)
How much spare time did I have this afternoon?

lmfao

Dynam0 12-10-2012 04:54 PM

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

LongGone 12-12-2012 07:14 AM

Re: The World's Hardest Sudoku (June 2012)
 
Quote:

Originally Posted by Izzy (Post 3724969)
Quote:

Originally Posted by SKG_Scintill (Post 3724889)

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


popsicle_3000 12-12-2012 08:15 AM

Re: The World's Hardest Sudoku (June 2012)
 
no idea that sudoku could get this involved!!


Quote:

Originally Posted by Dynam0 (Post 3816086)
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.[/color]

i'd probably agree with this

Choofers 12-19-2012 03:41 AM

Re: The World's Hardest Sudoku (June 2012)
 
Quote:

Originally Posted by Choofers (Post 3725107)
Put a number in a square, if it doesn't work, it's the wrong number kpCE

yep

SKG_Scintill 12-19-2012 04:38 AM

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.

Zapmeister 12-19-2012 03:41 PM

Re: The World's Hardest Sudoku (June 2012)
 
Quote:

Originally Posted by SKG_Scintill (Post 3821348)
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.

Or you could just redraw the grid out.

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:

Originally Posted by Choofers (Post 3725107)
Put a number in a square, if it doesn't work, it's the wrong number kpCE

You're assuming that you can get anywhere. With some of the hardest puzzles, like the one presented in the OP, there comes a point at which wherever you guess you will not be able to progress anywhere so you won't be able to prove or disprove any possible candidates.

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..
...|9.1|.6.
...|...|..5
---+---+---
2..|..8|.16
...|...|.2.
.3.|...|4.7
---+---+---
.7.|.4.|...
..8|2.9|...
9.6|8..|...

SE 11.7

in other news katy perry is bad at sudoku
http://www.youtube.com/watch?v=KlyXNRrsk4A#t=86s

gold stinger 12-19-2012 03:51 PM

Re: The World's Hardest Sudoku (June 2012)
 


lol

Choofers 09-11-2013 02:50 PM

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)

mi40 09-11-2013 03:23 PM

Re: The World's Hardest Sudoku (June 2012)
 
sudoku is rly fun

Zapmeister 09-11-2013 03:45 PM

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

mi40 09-11-2013 03:59 PM

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?

igotrhythm 09-11-2013 04:32 PM

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.

Zapmeister 09-11-2013 04:52 PM

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

Choofers 09-11-2013 04:59 PM

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

igotrhythm 09-11-2013 05:06 PM

Re: The World's Hardest Sudoku (June 2012)
 
Quote:

Originally Posted by Zapmeister (Post 3973661)
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

Not sure, but it was at least a few years ago back when there was a Borders a ways south of me on Woodward. I've only managed to solve 2 of the 200 puzzles contained therein. :(

I think there are 12x12 sudoku now, those are really fun.

Zapmeister 09-11-2013 05:24 PM

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

ReikonKeiri 09-12-2013 07:04 PM

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

qqwref 09-12-2013 07:20 PM

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.

Zapmeister 09-12-2013 07:23 PM

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..
81.|.95|.76
.46|.87|.95
---+---+---
67.|8.9|.5.
92.|56.|78.
.58|.7.|6.9
---+---+---
56.|7..|9.8
.37|9.8|56.
.89|.56|..7

SE 10.4


ReikonKeiri 09-16-2013 03:42 PM

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

Zapmeister 09-16-2013 05:19 PM

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.


Step 0: Why this puzzle is really not that hard. (you can skip this bit)


So over the last few years, it turns out that developments have been made to facilitate manual solving of ultra hard puzzles that don't rely on chain based methods. I'm still reading up on three years worth of material so don't take my words 100% for granted, but this'll do. These are called "exotic patterns". The idea behind this is that when people start doing sudokus they look for patterns in the candidate grid that will instantly give eliminations, for instance, when you see a naked pair, you'll think "oh that's going to kill all the other candidates that see the cells in the pair" and eliminate them without thinking. When you run out of patterns you start doing this whole chain business where you assume this number is true and see where it goes from there, which is human intuitive and USUALLY the best way to go about doing these things. The idea behind exotic patterns is to go back to the more "global" ideas of spotting big patterns and abandon the "local" chain-based approach. That's fine if you're a computer, but if you're a carbon-based lifeform it's hard to see big patterns, so we reduce everything to a bunch of patterns that a human player could reasonably find. We haven't found everything yet - this is still cutting edge stuff.

It turns out that at the highest level (SE rating) ~80-85% of puzzles have some big pattern that makes them easier to human players (this % goes down as the rating goes down). The thing is, we have no bloody idea what the hell to do with the ones that don't. Maybe there's some pattern that hasn't yet been found, or maybe they're just hard. Either way, throwing toilet paper at a tree is a more productive use of your time than doing them.

This puzzle does have such a pattern, whereas Arto Inkala's other 7-year-old Escargot, surprisingly, does not. This guy should stick to things he's good at, unlike publishing hard sudokus - that are easier than the ones he published 7 years ago, haha.


Step 1: the "multi-fish" pattern

Code:

8      1246  24569 |2347  12357  1234  |13569 4579  1345679
12459  124  3    |6    12578  1248  |1589  45789 14579 
1456  7    456  |348  9      1348  |2    458  13456 
-------------------+-------------------+-------------------
123469 5    2469  |2389  2368  7    |1689  2489  12469 
12369  12368 269  |2389  4      5    |7    289  1269 
24679  2468  24679 |1    268    2689  |5689  3    24569 
-------------------+-------------------+-------------------
23457  234  1    |23479 237    2349  |359  6    8     
23467  2346  8    |5    2367  23469 |39    1    2379 
23567  9    2567  |2378  123678 12368 |4    257  2357

This puzzle contains a pattern known as a "multi-fish" (I think) or a "big rank-0 logic". The idea is to look for the base/cover sector approach I outlined in my other post and you might like to look over that, or not, if you like to live dangerously. Have a look at the clue grid


See how the numbers 2, 4, 5, 7, 9 all line themselves up in nice neat columns and rows? And the other numbers 1, 3, 6, 8 do the same in the other columns/rows? If you've actually tried your hand at this puzzle you probably have. I'm pretty sure that is, in fact, a coincidence - it turns out that loads of hard puzzles have this property and we can exploit it. I don't know why they do though!

Have a look at the columns where the 2, 4, 5, 7, 9 numbers are, and look in particular at where the other numbers 1, 3, 6, 8 appear as pencilmarks in these columns.

Code:

column  2    5    6    7
--------------------------
row 1  16  13  13  136
row 2  1    18  18  18
row 3            138
row 4        368      168
row 5  1368
row 6  68  68  68  68
row 7  3    3    3    3
row 8  36  36  36  3
row 9        1368 1368

... as expected, the numbers all line up nicely(ish) within these rows! So if we took the numbers 1, 3, 6, 8 in these columns to use as our base sectors, we'd get 4 numbers in each of 4 columns, that's 16 sectors. Let's try to find 16 cover sectors:

Code:

column  2    5    6    7      cover
--------------------------
row 1  16  13  13  136  < 136 in row (3)
row 2  1    18  18  18  < 18 in row (2)
row 3            138      < this cell (1)
row 4        368      168  < these two cells (2)
row 5  1368                < this cell (1)
row 6  68  68  68  68  < 68 in row (2)
row 7  3    3    3    3    < 3 in row (1)
row 8  36  36  36  3    < 36 in row (2)
row 9        1368 1368      < these two cells (2)
                      total:  16

voila!

By the principle of base/cover elimination (apparently nobody calls them base or cover sectors anymore except me but I don't care), that means we can kill everything in the cover except for the numbers in the table!

So all of these are lies:
6r1c3 3r1c4 1r1c9 3r1c9 6r1c9 1r2c1 8r2c8 1r2c9 4r3c6 2r4c5 9r4c7 2r5c2 6r6c1 6r6c3 6r6c9 3r7c1 3r7c4 3r8c1 6r8c1 3r8c9 2r9c5 7r9c5 2r9c6

and our candidate grid looks a lot less intimidating!

Code:

8      1246  2459  |247  12357  1234  |13569 4579  4579
2459  124  3    |6    12578  1248  |1589  4579  4579 
1456  7    456  |348  9      138  |2    458  13456 
-------------------+-------------------+-------------------
123469 5    2469  |2389  368    7    |168  2489  12469 
12369  1368  269  |2389  4      5    |7    289  1269 
2479  2468  2479  |1    268    2689  |5689  3    2459 
-------------------+-------------------+-------------------
2457  234  1    |2479  237    2349  |359  6    8     
247    2346  8    |5    2367  23469 |39    1    279 
23567  9    2567  |2378  1368  1368  |4    257  2357

Ok I admit, I did need a bit of external assistance to find this thing, but it's certainly visible with some patience especially if you know it's there, then the pattern should come naturally. The rest of this solution is my own doing.


Step 2: some easy moves

Now we can make progress:

Code:

8      1246  2459  |247  12357  1234  |13569 4579  4579
2459  124  3    |6    12578  1248  |1589  4579  4579 
1456  7    456  |348  9      138  |2    458  13456 
-------------------+-------------------+-------------------
123469 5    2469  |2389  368    7    |168  2489  12469 
12369  1368  269  |2389  4      5    |7    289  1269 
2479  2468  2479  |1    268    2689  |5689  3    2459 
-------------------+-------------------+-------------------
2457  234  1    |2479  237    2349  |359  6    8     
247    2346  8    |5    2367  23469 |39    1    279 
23567  9    2567  |2378  1368  1368  |4    257  2357

hidden pair 36 in block 3
singles --> r2c7=1, r3c8=8
line-box 5 in row 3 and block 1
naked triple 249 in block 1
single --> r3c4=4

Code:

8      16    249  |27    12357  123  |36    4579  4579
249    24    3    |6    2578  28    |1    4579  4579 
156    7    56    |4    9      13    |2    8    36 
-------------------+-------------------+-------------------
123469 5    2469  |2389  368    7    |68    249  12469 
12369  1368  269  |2389  4      5    |7    29    1269 
2479  2468  2479  |1    268    2689  |5689  3    2459 
-------------------+-------------------+-------------------
2457  234  1    |279  237    2349  |359  6    8     
247    2346  8    |5    2367  23469 |39    1    279 
23567  9    2567  |2378  1368  1368  |4    257  2357

We also get another easy-ish step: a short loop that gets you r4c7:

if r4c7=6, then r6c7=8, then r5c2=8, then r1c2=1, then r1c7=6, then r4c7=/=6, contradiction

So r4c7=8. This chain doesn't backtrack anywhere on itself, so it's pretty simple to follow.

Code:

8      16    249  |27    12357  123  |36    4579  4579
249    24    3    |6    2578  28    |1    4579  4579 
156    7    56    |4    9      13    |2    8    36 
-------------------+-------------------+-------------------
123469 5    2469  |239  36    7    |8    249  12469 
12369  1368  269  |2389  4      5    |7    29    1269 
2479  2468  2479  |1    268    2689  |569  3    2459 
-------------------+-------------------+-------------------
2457  234  1    |279  237    2349  |359  6    8     
247    2346  8    |5    2367  23469 |39    1    279 
23567  9    2567  |2378  1368  1368  |4    257  2357



Step 3: an elimination that gets a few more numbers

The multi-fish is actually the least useful one of the known "exotic patterns" in that it tells you nothing about what to do after you've found it. You're left on your own. This puzzle is still hard, but attackable with chain-based "local" approaches without too much hassle.

Code:

8      16    249  |27    12357  123  |36    4579  4579
249    24    3    |6    2578  28    |1    4579  4579 
156    7    56    |4    9      13    |2    8    36 
-------------------+-------------------+-------------------
123469 5    2469  |239  36    7    |8    249  12469 
12369  1368  269  |2389  4      5    |7    29    1269 
2479  2468  2479  |1    268    2689  |569  3    2459 
-------------------+-------------------+-------------------
2457  234  1    |279  237    2349  |359  6    8     
247    2346  8    |5    2367  23469 |39    1    279 
23567  9    2567  |2378  1368  1368  |4    257  2357

It's not hard to resolve the 36 pair in block 3, like this

Assume r3c9=6 and r1c7=3.
Then in column 7, r6c7=6 and r7c7=5.
In block 1, r3c3=5, r3c1=1 and r1c2=6.
The two 5s mean that 5 in block 7 must be in r9c1, and then the 6 must be in r9c3.
So in row 5, r5c1=6, which gives you a 38 pair in r5c24, but then you can't put a 1 in block 4...

... contradiction. So r1c7=6 and r3c9=3. We get to put a few more numbers in! We have r1c2=1, r9c5=1, r3c6=1, and a hidden pair of 16 in block 6. Not that hard after all :P

Code:

8      1    249  |27    2357  23    |6    4579  4579
249    24    3    |6    2578  28    |1    4579  4579 
56    7    56    |4    9      1    |2    8    3 
-------------------+-------------------+-------------------
123469 5    2469  |239  36    7    |8    249  16 
12369  1368  269  |2389  4      5    |7    29    16 
2479  2468  2479  |1    268    2689  |59    3    2459 
-------------------+-------------------+-------------------
2457  234  1    |279  237    2349  |359  6    8     
247    2346  8    |5    2367  23469 |39    1    279 
23567  9    2567  |2378  1      368  |4    257  257



Step 4: another chain thingy

In fact this puzzle is still pretty hard and I've got nothing to do apart from throw chain-based things at it, so I might as well.

Code:

8      1    249  |27    2357  23    |6    4579  4579
249    24    3    |6    2578  28    |1    4579  4579 
56    7    56    |4    9      1    |2    8    3 
-------------------+-------------------+-------------------
123469 5    2469  |239  36    7    |8    249  16 
12369  1368  269  |2389  4      5    |7    29    16 
2479  2468  2479  |1    268    2689  |59    3    2459 
-------------------+-------------------+-------------------
2457  234  1    |279  237    2349  |359  6    8     
247    2346  8    |5    2367  23469 |39    1    279 
23567  9    2567  |2378  1      368  |4    257  257

Suppose r2c6=8.
Then r6c5=8 (in column 5), so r9c4=8 (in column 4). That locks the 3 in column 4 of block 5, so r4c5=6.
Then r6c2=6 (in row 6), so r8c6=6 (in row 8). That leaves 3 as the only value for r9c6, so r1c6=2.
That's not a contradiction, but it tells us that r1c6 or r2c6 must be 2. So we can kill 2 from elsewhere in the column and block.

Also if you put the last cell (r1c6) in the chain at the beginning and do the same thing, you get that r1c6 or r9c6 must be 3, so kill 3 from elsewhere in column 6.

Another number done: r1c4=7.

Code:

8      1    249  |7    35    23    |6    459  459
249    24    3    |6    58    28    |1    4579  4579 
56    7    56    |4    9      1    |2    8    3 
-------------------+-------------------+-------------------
123469 5    2469  |239  36    7    |8    249  16 
12369  1368  269  |2389  4      5    |7    29    16 
2479  2468  2479  |1    268    689  |59    3    2459 
-------------------+-------------------+-------------------
2457  234  1    |29    237    49    |359  6    8     
247    2346  8    |5    2367  469  |39    1    279 
23567  9    2567  |238  1      368  |4    257  257



Step 5: This puzzle is surprisingly resilient to being broken apart

Code:

8      1    249  |7    35    23    |6    459  459
249    24    3    |6    58    28    |1    4579  4579 
56    7    56    |4    9      1    |2    8    3 
-------------------+-------------------+-------------------
123469 5    2469  |239  36    7    |8    249  16 
12369  1368  269  |2389  4      5    |7    29    16 
2479  2468  2479  |1    268    689  |59    3    2459 
-------------------+-------------------+-------------------
2457  234  1    |29    237    49    |359  6    8     
247    2346  8    |5    2367  469  |39    1    279 
23567  9    2567  |238  1      368  |4    257  257

Quote:

Originally Posted by awein999 (Post 3724841)
after you get a couple numbers filled in correctly it's not that hard.

You're such a liar.

Yep, it's still pretty hard now. If I could have found a faster way to throw it open, I would, but this is putting up a lot of resistance. There are loads of cells with 2 values but no obvious starting point of attack. Eventually I got 2 out of r2c2:

Assume r2c2=2. Then r2c6=8, then r6c5=8, which locks the 2 in block 8 in column 5, which then makes r7c4=9 and r7c6=4.
Then in block 6, r6c6=9, which means r6c7=5, and then r7c7=3.
The 3 and the 4 make r7c2 a 2, which means r2c2 isn't 2, contradiction.

We get r2c2=4 and a box-line of 4 in block 7 and column 1.

Code:

8      1    29    |7    35    23    |6    459  459
29    4    3    |6    58    28    |1    579  579 
56    7    56    |4    9      1    |2    8    3 
-------------------+-------------------+-------------------
12369  5    2469  |239  36    7    |8    249  16 
12369  1368  269  |2389  4      5    |7    29    16 
279    268  2479  |1    268    689  |59    3    2459 
-------------------+-------------------+-------------------
2457  23    1    |29    237    49    |359  6    8     
247    236  8    |5    2367  469  |39    1    279 
23567  9    2567  |238  1      368  |4    257  257



Step 6: Fun with almost-locked sets

Code:

8      1    29    |7    35    23    |6    459  459
29    4    3    |6    58    28    |1    579  579 
56    7    56    |4    9      1    |2    8    3 
-------------------+-------------------+-------------------
12369  5    2469  |239  36    7    |8    249  16 
12369  1368  269  |2389  4      5    |7    29    16 
279    268  2479  |1    268    689  |59    3    2459 
-------------------+-------------------+-------------------
2457  23A  1    |29    237    49    |359  6    8     
247    236A  8    |5    2367  469  |39    1    279 
23567B 9    2567B |238  1      368  |4    257B  257B

This step isn't that critical in the path but I liked the feel of it so I left it in while writing up. The idea behind almost-locked-set theory is that an almost-locked set has N+1 candidates in N cells and if you have 2 of these things interacting in various ways they can do stuff.

Here the almost-locked sets are 236 in r78c2 and 23567r9c1389, marked A and B. They are doubly-linked to each other by 3 and 6, in that both of them have 3s and 6s in them, and all the 3s see each other and all the 6s see each other.

They also have a 2 in both of them. Now get this: because of this interaction, we can kill any other common candidate (in this case 2) from any cell that sees one of the almost-locked sets. Work it out yourself if you don't trust me. (Why wouldn't you trust me?)

r6c2, r789c1, r9c34 aren't 2. Then there's a line-box: 2 in row 9 and block 9. So r8c9 isn't 2.

Code:

8      1    29    |7    35    23    |6    459  459
29    4    3    |6    58    28    |1    579  579 
56    7    56    |4    9      1    |2    8    3 
-------------------+-------------------+-------------------
12369  5    2469  |239  36    7    |8    249  16 
12369  1368  269  |2389  4      5    |7    29    16 
279    68    2479  |1    268    689  |59    3    2459 
-------------------+-------------------+-------------------
457    23    1    |29    237    49    |359  6    8     
47    236  8    |5    2367  469  |39    1    79 
3567  9    567  |38    1      368  |4    257  257



Step 7: This puzzle STILL doesn't die!

Code:

8      1    29    |7    35    23    |6    459  459
29    4    3    |6    58    28    |1    579  579 
56    7    56    |4    9      1    |2    8    3 
-------------------+-------------------+-------------------
12369  5    2469  |239  36    7    |8    249  16 
12369  1368  269  |2389  4      5    |7    29    16 
279    68    2479  |1    268    689  |59    3    2459 
-------------------+-------------------+-------------------
457    23    1    |29    237    49    |359  6    8     
47    236  8    |5    2367  469  |39    1    79 
3567  9    567  |38    1      368  |4    257  257


It's actually getting annoying now how damn resilient this sudoku is. Sometimes they're like that, you've got to do a slog. I guess Arto Inkala did that on purpose, heh. Well, that's the way things are.

Chain to get rid of 9 from r6c7:

if r6c7=9, then r6c9=5, then r6c3=4, then r9c3=7, then r8c9=7, then the 9 in block 9 is locked to column 7, then r6c7 isn't 9, a contradiction. This chain doesn't backtrack so it's straightforward. It gives you a bunch of numbers.

Code:

8      1    29    |7    35    23    |6    459  459
29    4    3    |6    58    28    |1    579  579 
6      7    5    |4    9      1    |2    8    3 
-------------------+-------------------+-------------------
1239  5    2469  |239  36    7    |8    249  16 
1239  1368  269  |2389  4      5    |7    29    16 
279    68    2479  |1    268    689  |5    3    249 
-------------------+-------------------+-------------------
5      23    1    |29    7      4    |39    6    8     
4      236  8    |5    236    69    |39    1    7 
37    9    67    |38    1      368  |4    25    25

This thing STILL needs work... ugh.


Step 8: This puzzle is REALLY IRRITATING NOW

Code:

8      1    29    |7    35    23    |6    459  459
29    4    3    |6    58    28    |1    579  579 
6      7    5    |4    9      1    |2    8    3 
-------------------+-------------------+-------------------
1239  5    2469  |239  36    7    |8    249  16 
1239  1368  269  |2389  4      5    |7    29    16 
279    68    2479  |1    268    689  |5    3    249 
-------------------+-------------------+-------------------
5      23*  1    |29*  7      4    |39*  6    8     
4      236  8    |5    236    69*  |39*  1    7 
37*    9    67*  |38    1      368  |4    25    25

Here's an XY-chain, which means that the only thing you care about at each step is that the cell you're going to has 2 numbers in it. Pretty easy to follow.

Start at r9c3 and follow the starred cells round: r9c3, r9c1, r7c2, r7c4, r7c7, r8c7, r8c6. You have that 6 must be true at one end or the other of the chain.

Result: r8c2 and r9c6 aren't 6.

Singles and locked candidates and pairs get you to the ... oh wait.

Code:

8      1    29    |7    35    23    |6    4    59
29    4    3    |6    58    28    |1    7    59 
6      7    5    |4    9      1    |2    8    3 
-------------------+-------------------+-------------------
13    5    4    |29    36    7    |8    29    16 
13    68    29    |38    4      5    |7    29    16 
29    68    7    |1    268    69    |5    3    4 
-------------------+-------------------+-------------------
5      23    1    |29    7      4    |39    6    8     
4      23    8    |5    26    69    |39    1    7 
7      9    6    |38    1      38    |4    5    2

AAAAGHGHGHRGHGHRGHGHGHGHFDKJGSKLHSDFKH


Step 9: WHY WON'T THIS GODDAMN SUDOKU JUST FUCKING DIE. OH MY GOD. SERIOUSLY.

Code:

8      1    29    |7    35*    23    |6    4    59*
29*    4    3    |6    58    28    |1    7    59 
6      7    5    |4    9      1    |2    8    3 
-------------------+-------------------+-------------------
13    5    4    |29    36*    7    |8    29    16 
13    68    29    |38    4      5    |7    29    16 
29*    68    7    |1    268    69*  |5    3    4 
-------------------+-------------------+-------------------
5      23    1    |29    7      4    |39    6    8     
4      23    8    |5    26    69    |39    1    7 
7      9    6    |38    1      38    |4    5    2

6-cell XY-chain. Follow the starred cells: r2c1, r6c1, r6c6, r4c5, r1c5, r1c9. 9 must be the solution at either end. r1c3 and r2c9 aren't 9.

Code:

8      1    2    |7    5      3    |6    4    9
9      4    3    |6    8      2    |1    7    5 
6      7    5    |4    9      1    |2    8    3 
-------------------+-------------------+-------------------
1      5    4    |2    3      7    |8    9    6 
3      6    9    |8    4      5    |7    2    1 
2      8    7    |1    6      9    |5    3    4 
-------------------+-------------------+-------------------
5      2    1    |9    7      4    |3    6    8     
4      3    8    |5    2      6    |9    1    7 
7      9    6    |3    1      8    |4    5    2

FUCKING FINALLY.


Step 10: mash some FFR songs

200th mashed FC get!



That's it. Thread over. You can all go home now.

Tim Allen 09-20-2013 05:11 PM

Re: The World's Hardest Sudoku (June 2012)
 
wow zap nice one minute waltz

igotrhythm 09-22-2013 09:20 PM

Re: The World's Hardest Sudoku (June 2012)
 
Quote:

Originally Posted by Zapmeister (Post 3973686)
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

the 12x12s I mentioned are by Will Shortz, or at least he collected them. As for the Wayne Gould book, it's copyright 2006, so it's very possible that all I'd need to do is learn the X-Wing.


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