The World's Hardest Sudoku (June 2012)

[Zapmeister]

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]

considering the number of clues there and this video

the "hardest puzzle" claim is fucking laughable hahaha

[qqwref]

"Hardest" doesn't have much to do with the number of clues. Some of the 17-clue puzzles are quite straightforward.

[Zapmeister]

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

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]

thats interesting as fuck and i didnt know that. thank you for bringing to light my ignorance

[Zapmeister]

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

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.

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:

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!

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:

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

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.

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.

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

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.

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.

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

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

Originally Posted by awein999

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.

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

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.

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!

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.

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

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.

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.

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.

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]

wow zap nice one minute waltz

[igotrhythm]

Originally Posted by Zapmeister

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.