Need help with this...

Post the puzzle or solving technique that's causing you trouble and someone will help

Postby RW » Wed May 24, 2006 7:31 pm

Viggo wrote:In general I'think the two ways, the puzzle is solved, are very different. Except for the first finned X-wing and step 2, all the error nets are different. When other equal candidates are eliminated, the premis are different too. However some of the later simpler reductions are the same.

I cannot quite agree on this point. Both our solutions are actually very similar. In your grid where you colored our similar reductions yellow, you should actually also color candidates 6 and 8 in r5c1 yellow, I removed them with a "hard" elimination when I showed r5c1=3 with a forcing chain. If you do so, then it is enough to eliminate the yellow candidates, the rest of the puzzle can be solved with the XY-wing and the ERs we both included in our solutions. So the essential candidate eliminations are exactly the same, we just used different paths to eliminate them, eliminating different candidates on the way to allow us to get to the important reductions. I think this is very interesting, seems this is in some way the most visible path to break the puzzle, as we both followed it.:)

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

Postby Viggo » Fri May 26, 2006 1:49 am

ronk wrote:Let's say we have two almost identical cases. In the first case, digit 2 is a candidate in cell r5c8. In the second case, it is not. I certainly don't think the error net expression for the deduction r5c8<>3 should be identical for the two cases.

That said, I don't claim to know the "right way" to show that "preparation of a strong link." Perhaps Carcul will weight in on this point.


I have tried to look at Carsuls reductions on the "The youghest known Sudoku puzzle", Vidars no. 77:

Carsul wrote:After the basic logic is applied to this puzzle we arrive at the following grid:

Code: Select all
*---------------------------------------------------------------*
| 7       1589  568   | 1269  13569  23569 | 4      125   123   |
| 14569   2     456   | 1469  7      34569 | 156    8     13    |
| 1456    145   3     | 1246  156    8     | 12567  1257  9     |
|---------------------+--------------------+--------------------|
| 2489    4789  2478  | 5     1689   469   | 3      1247  12478 |
| 3458    6     4578  | 148   2      34    | 1578   9     1478  |
| 234589  4589  1     | 489   389    7     | 258    245   6     |
|---------------------+--------------------+--------------------|
| 12568   1578  25678 | 3     568    256   | 9      1247  12478 |
| 1258    3     2578  | 2789  4      259   | 1278   6     1278  |
| 2468    478   9     | 2678  68     1     | 278    3     5     |
*---------------------------------------------------------------*



From here, I have solved the puzzle through the following steps:

1. [r3c78](-1-[r3c1245])=6=[r2c7]-6-[r2c3]=6=[r3c1](-6-[r3c4|r7c1])-6-[r3c5](-5-[r79c5]-6,8-[r89c4| r7c6])-5-[r3c2]{(-4-[r6c2])-4-[r9c2]=4=[r9c1]-4-[r5c1]}-4-[r3c4](-2-[r8c4])-2-[r9c4]{-7-[r8c4](-9-[r8c6])-9-[r6c4]}(-7-[r9c7])-7-[r9c2](-8-[r9c7]-2-[r6c7])(-8-[r6c2])-8-[r78c1]=(Almost Unique Rectangle: r78c16)=8|1=[r78c1]-1-[r2c1]=1=[r1c2]-1-[r1c45]=1=[r2c4](-1-[r56c4]-8-[r6c5])=4=[r2c6]-4-[r5c6](-3-[r5c1])-3-[r6c5]-9-[r6c2](-5-[r6c7]-8-[r6c4])-5-[r5c1]-8-[r5c4]-4-[r6c4], => r3c7/r3c8<>1.


If you look at "[r3c78](-1-[r3c1245])", Carsul removes "1" from some cells and prepare two strong interference links later on, "[r2c1]=1=[r1c2]" and "[r1c45]=1=[r2c4]". Again "[r3c2]{(-4-[r6c2])-4-[r9c2]=4=[r9c1]-4-[r5c1]}-4-[r3c4]" removes 4 in r3c4, which prepare the link, "[r2c4](-1-[r56c4]-8-[r6c5])=4=[r2c6]".

So inside the error net Carsul do prepare strong links without making special notes about that.

However I have no example from Carsul for the case, when the errornet is started, and the start asignment excludes a candidate value preparing the strong interference link.

Here is an illustration of Carsuls first step:
Image

/Viggo
Viggo
 
Posts: 60
Joined: 21 April 2006

Postby ronk » Fri May 26, 2006 10:27 am

Viggo wrote:
Carcul wrote:From here, I have solved the puzzle through the following steps:

1. [r3c78](-1-[r3c1245])=6=[r2c7]-6-[r2c3]=6=[r3c1](-6-[r3c4|r7c1])-6-[r3c5](-5-[r79c5]-6,8-[r89c4| r7c6])-5-[r3c2]{(-4-[r6c2])-4-[r9c2]=4=[r9c1]-4-[r5c1]}-4-[r3c4](-2-[r8c4])-2-[r9c4]{-7-[r8c4](-9-[r8c6])-9-[r6c4]}(-7-[r9c7])-7-[r9c2](-8-[r9c7]-2-[r6c7])(-8-[r6c2])-8-[r78c1]=(Almost Unique Rectangle: r78c16)=8|1=[r78c1]-1-[r2c1]=1=[r1c2]-1-[r1c45]=1=[r2c4](-1-[r56c4]-8-[r6c5])=4=[r2c6]-4-[r5c6](-3-[r5c1])-3-[r6c5]-9-[r6c2](-5-[r6c7]-8-[r6c4])-5-[r5c1]-8-[r5c4]-4-[r6c4], => r3c7/r3c8<>1.
(...)
So inside the error net Carcul do prepare strong links without making special notes about that.

I'm not about to analyze anything that complex, so I'll take your word on that ... and not consider an error net expression to be "complete" again without also checking the puzzle:)
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby daj95376 » Fri May 26, 2006 3:58 pm

Using only naked/hidden singles in my chains, I get this -- without the fancy notation.

Code: Select all
EmilyS Puzzle:

....793..1...3......8.26..94.1.....6.59.....7......15.2..3..6.....2....5.4...5.8.

r2c2    =  9     Hidden Single
r7c3    =  5     Hidden Single
r4c5    =  5     Hidden Single
    b6  -  9     Locked Candidate (1)
    b2  -  1     Locked Candidate (1)
r9c9    <> 2     [r9c9]=2 => [r9]=INVALID
r9c7    =  2     Hidden Single
r4c7    =  9     [r4c7]=8 => [r9c9]=EMPTY
r5c7    =  8     [r5c7]=4 => [r7c5]=EMPTY
r5c4    =  6     [r5c4]=4 => [r3c4]=EMPTY
r5c1    =  3     Naked  Single
r3c2    =  3     Hidden Single
r9c4    =  9     [r9c4]=7 => [r8c7]=EMPTY
r6c5    =  9     Hidden Single
r7c8    =  9     Hidden Single
r8c1    =  9     Hidden Single
r6c1    =  8     Hidden Single
  c2    -  267   Naked  Triple
r7c6    =  7     Hidden Single
    b9  -  7     Locked Candidate (1)
  c2    -  7     Locked Candidate (2)
  c5    -  8     Locked Candidate (2)
r9c9    =  1     [r9c9]=3 => [r7]=INVALID
Naked  Singles from here on.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby Viggo » Fri May 26, 2006 10:04 pm

RW wrote:So the essential candidate eliminations are exactly the same, we just used different paths to eliminate them, eliminating different candidates on the way to allow us to get to the important reductions. I think this is very interesting, seems this is in some way the most visible path to break the puzzle, as we both followed it.


Yes, you are right. Most of the eliminated candidates are the same. But most of the error nets were different. I tend to solve some more candidates than you did and it may have made some error nets smaller.

ravel wrote:As i said, this program tries to find a good order to minimize the number of brute force steps (which mostly only can be written as monster chains) needed to solve the puzzle. It therefore is not qualified for finding an elegant solution, but the number of steps it needs is a rather good measure for extremely hard puzzles...

The 4-steppers are:
Code: Select all
 
r1c9<>1, r8c3<>3, r5c6<>1, r4c4<>7
r2c9<>4, r6c9<>4, r2c6<>4, r4c4<>7
r4c2<>8, r8c3<>3, r7c9<>1, r7c5<>9
r5c4<>8, r5c4<>4, r5c6<>1, r4c4<>7
r6c9<>4, r2c6<>4, r5c4<>8, r4c4<>7
r8c8<>1, r8c3<>3, r5c6<>1, r4c4<>7
r9c9<>2, r7c9<>1, r2c6<>4, r4c4<>7


According to ravel, only 4 error nets are needed, so it is possible to solve the puzzle by 4 (possibly very hard) steps. But RW and I did not choose any of these candidate eliminations. By using other and more candidates to be eliminated, I suppose that each step is made by a smaller error net. At a first glance of the solvers error nets, the first line seems to be complex, but not "monster chains". And alle these possibilities seems all right.

daj95376, thank you for your solvers information. It seems that the solver from daj95376 finds 6 error nets to solve the puzzle. Two of these candidate eliminations is the same as RW's and mine.

/Viggo
Viggo
 
Posts: 60
Joined: 21 April 2006

Postby Viggo » Sat May 27, 2006 3:46 pm

I have tried to follow the proposal of Ravels solver first line. I think it solves the puzzle in a simpler way than both RW and myself have done:

Code: Select all
1. [r1c9]{=8=[r1c4](-8-[r5c4])
                   -8-[r2c6]-4-[r8c6]}
         (-1-[r9c9]=1=[r9c5])
         -1-[r7c9](-4-[r6c9])
                  -4-[r7c56]=4=[r8c5]=6=[r9c4]-6-[r5c4]-4-[r5c78]

   => Nowhere to place 4 in box 6 => r1c9<>1


Image

=> Pointing pair column 8, r78c8<>1
=> Simple nice loop: [r8c2]-3-[r8c8]=3=[r9c9]=1=[r7c9]-1-[r7c2]=1=[r8c2] => r8c2<>3

Image
I think this Nice Loop is optional for solving the puzzle.

Code: Select all
2. [r8c3]-3-[r8c8]=3=[r9c9](-3-[r6c9])
                           (=1=[r7c9]-1-[r7c256])
                           {=1=[r9c5](-1-[r8c6])
                                     -1-[r5c5]=1=[r5c6]}
                           =2=[r9c7]-2-[r5c7]=2=[r5c8](-2-[r6c9])
                                                      =3=[r4c8](=9=[r4c7])
                                                               -3-[r4c6]
      =3=[r6c6](-3-[r6c12]=3=[r5c1]=6=[r6c123]-6-[r6c5])
               =2=[r4c6]=7=[box line: r78c6]-7-[r9c4]=7=[r9c13]-7-[r7c2](-8-[r7c5])
                                                                        -8-[r46c2]
      =8=[r6c1](-8-[r6c458])
               -8-[r6c9](-4-[r6c5]-9-[r7c5])
                        =8=[r5c7]-8-[r5c45]=8=[r4c4]-8-[r12c4]
      =8=[r2c6]-8-[Naked pair: r78c6]-4-[r7c5]

   => empty cell r7c5 => r8c3<>3


Image

=> X-wing r69c39, r9c1<>3, r6c126<>3

Using the same error net, it also is possible to eliminate 3 from r8c1 and r8c2. However this is not done here because a solver may not see that in this way. This could have maked the solving easier.

Code: Select all
3. [r5c6]=3=[r4c6]=2=[r6c6](-2-[r6c9])
                           -2-[r6c23]=2=[r4c2]{=7=[r4c4](-7-[r9c4])
                                                        =8=[r4c7](-8-[r5c7])
                                                                 -8-[r6c9]-4-[r5c7]-2-[r9c7]}
                                              (=3=[r3c2]-3-[r3c1])
                                              -2-[r1c2](-6-[r1c8]=6=[r2c8])
                                                       -6-[r1c1]
      -5-[r3c1](-7-[r9c1])
               -7-[r3c78]=7=[r2c7]-7-[r9c7]=7=[r9c3]=3=[r8c1]=9=[r9c1]-9-[r9c7]

   => Empty cell r9c7 => r5c6<>1


Image

=> Singles r5c5=1, r9c9=1, r7c9=4, r9c7=2, r8c8=3, r9c3=3, r6c9=3
=> Pointing pair: r12c8<>2, r5c46<>4, r2c7<>8
=> Simple Nice Loop: [r8c5]-6-[r8c3]-7-[r8c7]-9-[r7c8]=9=[r7c5]-9-[r9c5]-6-[r8c5]
=> r8c5<>6

Image

=> Pointing pair: r9c1<>6
=> Simple Nice Loop: [r9c7]-9-[r8c1]=9=[r9c1]=7=[r9c4]-7-[r4c4]-8-[r4c7]-9-[r8c7]
=> r9c7<>9

Image

=> Singles and one empty rechtangle solves the puzzle.

Step 2 and 3 are complex steps, but no more complex than the most complex steps RW and I did. I don't consider them "monster steps".

If you counts only error nets as a step, then 3 steps is sufficient. And then 2 or 3 additional Simple Nice Loops must be used too.

/Viggo
Viggo
 
Posts: 60
Joined: 21 April 2006

Re: Need help with this...

Postby Alain David » Sun May 28, 2006 2:56 am

Well the solution is not that all difficult !
I reached this one:
624 579 318
197 438 562
538 126 479

471 853 926
359 612 847
862 794 153

215 387 694
986 241 735
743 965 281

I don't use any specific method.
Just a spreadsheet (in OpenOffice) to help registring moves.
In this sudoku the problem is that you have to make some choices because the solution is not obvious. I din't tried all the choices, it's means that others solutions are possible.
Alain David
 
Posts: 2
Joined: 27 May 2006

Postby Viggo » Sun May 28, 2006 5:34 pm

Hi Alain David

You have got the right solution!

Well, I think this puzzle is difficult. On this unofficial list it is among the most difficult normal sudokus found. So you are an excelent sudoku solver, when you find it "not so difficult". On this link you can find other hard puzzles.

All the expressions here seems difficult. It is in general simple. You explain guesses you make while you are solving the puzzle, and then you have to argue why you can do every step in the solving from there on until the puzzle "colapses" and becommes very simple. All the drawings of links and the code is doing exsactly that. When you are doing a puzzle it might seem simple just to progress the puzzle, but when you have to write down an argue exsactly why you can do every step, then it becomes a bit more difficult just to express those "simple" steps.

In this puzzle you have to guess at least 3 or 4 times along the way. It is a kind of "try and error". Which cell shall you choose for the guess and to what value - thats the good question to discuss and the priciples for that. Or you may not have to guess at all if you have found a very good direct technique.

/Viggo
Viggo
 
Posts: 60
Joined: 21 April 2006

Postby Viggo » Mon May 29, 2006 4:00 pm

Regarding the previously referenced solution by Ravels solver, I have discovered, that the second step could be improved by selecting r9c9=3 as a start. This will make an almost identical error net. But the result will be much better, because 3 singles are fixed as a result of this error net. And it will reduce the size of the later error nets.

So maybe even Ravels solver can be improved...

/Viggo
Viggo
 
Posts: 60
Joined: 21 April 2006

Postby ravel » Mon May 29, 2006 4:22 pm

Viggo wrote:So maybe even Ravels solver can be improved...

No doubt, e.g. by bug fixing:)
After that it came up with 3 steps:
r4c2<>8, r9c9<>3, r4c7<>8
So the puzzle did not make it anymore for the ultrahard list.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Viggo » Mon May 29, 2006 6:02 pm

Ravel, do you count Simple Nice Loops as a step, or is it only an error net, that qualify for a count?

/Viggo
Viggo
 
Posts: 60
Joined: 21 April 2006

Previous

Return to Help with puzzles and solving techniques