Solutions to The hardest sudokus

Advanced methods and approaches for solving Sudoku puzzles

Solutions to The hardest sudokus

Postby RW » Sun Oct 29, 2006 10:12 am

Lots of people seem to like the challenge of taking on the puzzles from ravels list of The hardest sudokus. At the moment the solutions are scattered around the forum in separate threads. I thought that maybe we should try to keep them together in one thread for easier access, even though ravel has done a good job by linking to the solutions from his list. This thread can also be used for general discussion about the techniques required to tackle these horrible beasts.

I'm going to start this thread modestly, with a solution to the puzzle that at the moment is last on ravels list, my own contribution, the toughest 21-clue puzzle in the Pt-grid:
Code: Select all
 +-------+-------+-------+
 | 1 . . | . . . | . . 9 |
 | . . 7 | . 8 . | . . 6 |
 | . . . | 3 . . | . 5 . |
 +-------+-------+-------+
 | . . . | . 4 . | 8 . . |
 | 7 . . | . . 1 | . . . |
 | . 9 6 | . . . | . . . |
 +-------+-------+-------+
 | . . 8 | 2 . . | . . . |
 | 5 . . | . . . | . 6 3 |
 | . 6 . | . 7 . | 4 . . |
 +-------+-------+-------+

I did eliminations where I saw that I could. When I did some elimination, I tried to follow with other eliminations that would either benefit from the last, or continue the path of the last elimination. I tried to solve bivalue cells and values with only two possibilities in an unit whenever I could.

After the basics:
Code: Select all
 *-----------------------------------------------------------------------------*
 | 1       23458   2345    | 4567    256     24567   | 237     23478   9       |
 | 2349    2345    7       | 159     8       2459    | 123     1234    6       |
 | 6       248     249     | 3       129     2479    | 127     5       12478   |
 |-------------------------+-------------------------+-------------------------|
 | 23      1235    1235    | 5679    4       235679  | 8       2379    257     |
 | 7       2345    2345    | 8       2359    1       | 6       239     25      |
 | 8       9       6       | 57      235     2357    | 12357   12347   12457   |
 |-------------------------+-------------------------+-------------------------|
 | 349     1347    8       | 2       13569   34569   | 1579    17      157     |
 | 5       1247    1249    | 149     19      8       | 1279    6       3       |
 | 239     6       1239    | 159     7       359     | 4       128     1258    |
 *-----------------------------------------------------------------------------*


1. r7c5<>9:
[r7c5](-9-[r89c4])-9-[r8c5]-1-[r89c4]-45-[r1c4]
                                     -5-[r6c4]-7-[r1c4]-6-[r1c5]=6=[r7c5]
                                     
2. r7c6<>9:
[r7c6]-9-[r7c7]=9=[r8c7]-9-[r8c3]
      -9-[r8c45]-14-[r8c3]-2-[r9c1]
      =6=[r7c5]=3=[r9c6]-3-[r9c1]
      -9-[r8c5]-1-[r89c4]=1=[r2c4]=9=[r2c1]-9-[r9c1]
     
3. r7c1<>9:
[r7c1]-9-[r2c1]=9=[r3c3]-9-[r3c5]
      -9-[r7c7]=9=[r8c7]-9-[r8c5]=9=[r5c5]-9-[r5c8]
                                 -1-[r89c4]=1=[r2c4]-1-[r2c89]
                                 -1-[r3c5]-2-[r3c2]
      =4=[r2c1]-4-[r2c8]
               -4-[r3c2]-8-[r3c9]=8=[r9c9]=2=[r9c8]-2-[r2c8]
                                                   -2-[r5c8]-3-[r2c8]

Solves a single and progresses the puzzle here:
Code: Select all
 *--------------------------------------------------------------------*
 | 1      23458  2345   | 456    256    24567  | 237    2478   9      |
 | 2349   2345   7      | 159    8      2459   | 123    124    6      |
 | 6      248    249    | 3      129    2479   | 127    5      148    |
 |----------------------+----------------------+----------------------|
 | 23     1235   1235   | 569    4      569    | 8      39     7      |
 | 7      345    345    | 8      59     1      | 6      39     2      |
 | 8      9      6      | 7      23     23     | 5      14     14     |
 |----------------------+----------------------+----------------------|
 | 34     1347   8      | 2      1356   3456   | 9      17     15     |
 | 5      1247   1249   | 149    19     8      | 127    6      3      |
 | 239    6      1239   | 159    7      359    | 4      128    158    |
 *--------------------------------------------------------------------*

4. r7c8<>1:
[r7c8](-1-[r29c8])-1-[r7c9]-5-[r9c9]-8-[r9c8]-2-[r2c8]-4-[r6c8]-1-[r7c8]

5. r6c5<>2:
[r6c5]=3=[r7c5]=6=[r7c6]-6-[r4c6]=6=[r4c4]-6-[r1c4]
                        =4=[r8c4]-4-[r1c4]-5-[r1c23]=5=[r2c2]-5-[r45c2]
                        =5=[r7c9]=1=[r7c2]-1-[r4c2]=1=[r4c3]=5=[r5c3]-5-
                             [r5c5](-9-[r3c5])-9-[r8c5]-1-[r3c5]-2-[r6c5]

Some more singles solved, current state:
Code: Select all
 *--------------------------------------------------------------------*
 | 1      23458  2345   | 456    256    4567   | 237    248    9      |
 | 2349   2345   7      | 159    8      459    | 123    124    6      |
 | 6      248    249    | 3      129    479    | 127    5      148    |
 |----------------------+----------------------+----------------------|
 | 23     1235   1235   | 569    4      569    | 8      39     7      |
 | 7      345    345    | 8      59     1      | 6      39     2      |
 | 8      9      6      | 7      3      2      | 5      14     14     |
 |----------------------+----------------------+----------------------|
 | 34     134    8      | 2      156    3456   | 9      7      15     |
 | 5      7      1249   | 149    19     8      | 12     6      3      |
 | 239    6      1239   | 159    7      359    | 4      128    158    |
 *--------------------------------------------------------------------*

6. r4c1<>3:
[r4c1]-3-[r7c1]-4-[r8c3]
      -3-[r4c8]=3=[r5c8]=9=[r5c5]-9-[r3c5]
                                 -9-[r8c5]-1-[r8c7]=1=[r23c7]-1-[r3c9]
                                                             -2-[r8c3]
                                          -1-[r3c5]-2-[r3c23]
                                          -1-[r8c3]-9-[r3c3]-4-[r3c9]
                                                            -4-[r3c2]-8-[r3c9]

7. r7c5<>5:
=5=[r7c5]{BUG-lite:[r147c456]-5-[r1c456]}
         =6=[r1c5]-6-[r1c6]
                  -6-[1c4]-4-[r8c4]
                          -4-[r1c6]-7-[r3c6]
                          -4-[r3c6]-9-[r3c3]-4-[r8c3]
                         
8. r7c5<>1:
[r7c5]-1-(-1-[r89c4])[r8c5]-9-[r89c4]-45-[r1c4]-6-[r1c5]=6=[r7c5]

Still no solution, current state of the puzzle:
Code: Select all
 *--------------------------------------------------------------------*
 | 1      23458  345    | 456    25     4567   | 237    248    9      |
 | 349    2345   7      | 159    8      459    | 123    124    6      |
 | 6      248    49     | 3      129    479    | 127    5      148    |
 |----------------------+----------------------+----------------------|
 | 2      135    135    | 569    4      569    | 8      39     7      |
 | 7      345    345    | 8      59     1      | 6      39     2      |
 | 8      9      6      | 7      3      2      | 5      14     14     |
 |----------------------+----------------------+----------------------|
 | 34     134    8      | 2      6      345    | 9      7      15     |
 | 5      7      1249   | 149    19     8      | 12     6      3      |
 | 39     6      1239   | 159    7      359    | 4      128    158    |
 *--------------------------------------------------------------------*

Finned X-wing: r3c9<>1
Finned X-wing: r5c2<>5

9. r1c7<>2:
[r1c7]-2-[r1c5]-5-[r5c5]-9-[r8c5]-1-[r8c7]-2-[r1c7]

10. r9c3<>1:
[r9c3]-1-[r7c2]=1=[r7c9]-1-[r8c7]-2-[r8c3]=2=[r9c3]

11. r8c3<>2:
=2=[r8c3]=1=[r7c2]=4=[r7c1]-4-[r2c1]
         -2-[r8c7]-1-[r9c9]=1=[r6c9]=4=[r3c9]-4-[r3c3]-9-[r2c1]
                                                      -9-[r3c6]
                                             -4-[r3c6]-7-[r3c7]-2-[r2c7]-3-[r2c1]
 
12. r8c3<>1:
[r8c3]-1-[r4c3]=1=[r4c2]
      =9=[r3c3]-9-[r3c6]
      -1-[r8c5]=1=[r3c5]-1-[r3c7]-7-[r3c6]
                                 -7-[r1c7]-3-[r1c3]
               -9-[r5c5]-5-[r5c23]=5=[r4c3]-5-[r1c3]-4-[r1c8]
                        -5-[r1c5]-2-[r1c8]-8-[r3c9]-4-[r3c6]

Now lots of SSTS techniques bring us here:
Code: Select all
 *--------------------------------------------------*
 | 1    28   35   | 46   25   67   | 37   48   9    |
 | 49   35   7    | 159  8    459  | 13   2    6    |
 | 6    28   49   | 3    129  79   | 17   5    48   |
 |----------------+----------------+----------------|
 | 2    35   1    | 569  4    569  | 8    39   7    |
 | 7    4    35   | 8    59   1    | 6    39   2    |
 | 8    9    6    | 7    3    2    | 5    14   14   |
 |----------------+----------------+----------------|
 | 34   1    8    | 2    6    34   | 9    7    5    |
 | 5    7    49   | 149  19   8    | 2    6    3    |
 | 39   6    2    | 59   7    359  | 4    18   18   |
 *--------------------------------------------------*
 
13. r1c7=7:
[r1c7]=7=[r1c6]=6=[r1c4]=4=[r8c4]=1=[r2c4]-1-[r2c7]-3-[r1c7]

Singles remain. It's funny how the fact that it's last on the list can give a false impression that it would be easy...

This is probably not the best solution, but it's one way of doing it. Afterwards when I look at it, I can see that step 8 is actually exactly the same as step 1, feel completely stupid for not noticing that when I did the first step... It could perhaps have shortened the solution a bit.

I apologize in advance for all possible typos and mistakes in the notation.

RW
RW
2010 Supporter
 
Posts: 1010
Joined: 16 March 2006

Postby ravel » Sun Oct 29, 2006 12:15 pm

Nice solution, RW, showing how the tactic to concentrate on bivalue/bilocation cells can save a lot of redundant steps (the SE solution has 54 chains).

I quickly followed the solution in the SE (where i combined step 1 and 8 with ER 7.1) and got this step ratings (which about correlate with the length of your deductions):

7.1, 9.1, 9.4, 7.1, 9.1, 9.0, 8.4, 7.1, 7.1, 9.2, 9.1, 7.3 (sum 99).

The sum here is not very meaningful, because steps with rating under 8 can be done in the head easily (therefore the rating is too high), whereas it is very hard to do this for steps with ER > 9.
ravel
 
Posts: 998
Joined: 21 February 2006


Return to Advanced solving techniques