The World's Hardest Sudoku (June 2012)

[igotrhythm]

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]

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.

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]

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]

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]

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]

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

I quit.

[Dark_Chrysalis]

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]

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]

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.

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

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

     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.

 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.

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

     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"

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

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

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

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

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

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

     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)

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

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

+--------------------------------------------------------------------------------+
 |  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]

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

How much spare time did I have this afternoon?

lmfao

[Dynam0]

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]

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

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

[popsicle_3000]

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

no idea that sudoku could get this involved!!

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]

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

yep

[SKG_Scintill]

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.