The New Sudoku Players' Forum

[Sue De Coq]

Consider the following somewhat attractive puzzle:

Code: Select all

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


It's very difficult to make a single move and, prior to the arrival of Sherlock, I had to guess albeit after a few logical eliminations.

Code: Select all

The value 2 in Box 9 must lie in Row 8.
- The move r9c8:=2 has been eliminated.
The value 2 in Box 1 must lie in Column 2.
- The move r2c1:=2 has been eliminated.
The value 5 in Box 9 must lie in Row 8.
- The move r7c9:=5 has been eliminated.
The value 9 in Box 1 must lie in Row 2.
- The move r1c2:=9 has been eliminated.
The value 9 in Box 9 must lie in Column 8.
- The move r8c9:=9 has been eliminated.
The values 4 and 5 occupy the cells r3c2 and r3c9 in some order.
- The moves r3c2:=3 and r3c9:=8 have been eliminated.
Consider the chain r3c6-1-r2c5~1~r2c3-1-r9c3~1~r9c7-1-r6c7~1~r6c6.
When the cell r6c6 contains the value 1, so does the cell r3c6 - a contradiction.
Therefore, the cell r6c6 cannot contain the value 1.
- The move r6c6:=1 has been eliminated.


The critical point is the following:

Code: Select all

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


I can't find any Forced Chain here but, after Sherlock has helped out twice in short order:

Code: Select all

The 12 permutations of Column 7 and 6 permutations of Column 9 combine legally in 11 different ways.
Column 7:
3-5-9-6-2-1-8-4-7
3-6-9-7-2-1-8-5-4
3-7-9-6-2-1-8-5-4
4-5-9-6-2-1-8-3-7
7-5-9-6-2-1-8-3-4
4-6-9-7-2-1-8-5-3
4-7-9-6-2-1-8-5-3
7-5-9-6-2-1-8-4-3
3-5-9-6-2-7-8-4-1
3-5-9-7-2-6-8-4-1
4-5-9-6-2-7-8-3-1
4-5-9-7-2-6-8-3-1
Column 9:
1-2-4-8-3-9-7-5-6
1-2-5-8-3-9-7-4-6
1-5-4-8-3-9-7-2-6
1-7-5-8-3-9-4-2-6
1-8-5-7-3-9-4-2-6
1-8-5-9-3-7-4-2-6
No combination has the value 7 as a candidate for the cell r9c7.
- The move r9c7:=7 has been eliminated.
The values 7 and 9 occupy the cells r9c2 and r9c8 in some order.
- The moves r9c2:=3, r9c2:=4, r9c8:=1 and r9c8:=3 have been eliminated.
Consider the chain r9c3-1-r9c7-1-r6c7-1-r6c5-4-r6c6~4~r9c6-2-r9c4~3~r9c3.
When the cell r9c3 contains the value 3, it likewise contains the value 1 - a contradiction.
Therefore, the cell r9c3 cannot contain the value 3.
- The move r9c3:=3 has been eliminated.
The 18 permutations of Column 1 and 18 permutations of Column 2 combine legally in 44 different ways.
Column 1:
6-1-8-2-4-3-7-9-5
6-1-8-2-4-7-3-9-5
6-1-8-3-4-2-7-9-5
6-1-8-7-4-2-3-9-5
6-8-1-2-4-3-7-9-5
6-9-1-2-4-3-7-8-5
6-8-1-2-4-7-3-9-5
6-9-1-2-4-7-3-8-5
6-8-1-3-4-2-7-9-5
6-9-1-3-4-2-7-8-5
6-8-1-7-4-2-3-9-5
6-9-1-7-4-2-3-8-5
6-8-3-2-4-7-1-9-5
6-9-3-2-4-7-1-8-5
6-9-8-2-4-7-1-3-5
6-8-3-7-4-2-1-9-5
6-9-3-7-4-2-1-8-5
6-9-8-7-4-2-1-3-5
Column 2:
2-5-4-1-6-8-3-9-7
2-5-4-1-7-8-3-6-9
2-9-4-1-5-8-3-6-7
2-9-5-1-6-8-3-4-7
2-5-4-1-6-8-7-3-9
2-5-4-1-7-8-6-3-9
2-9-4-1-5-8-6-3-7
2-9-5-1-6-8-4-3-7
3-2-4-1-5-8-6-9-7
3-2-4-1-5-8-7-6-9
3-2-5-1-6-8-4-9-7
3-2-5-1-7-8-4-6-9
3-2-5-1-6-8-7-4-9
3-2-5-1-7-8-6-4-9
4-2-5-1-6-8-3-9-7
4-2-5-1-7-8-3-6-9
4-2-5-1-6-8-7-3-9
4-2-5-1-7-8-6-3-9
No combination has the value 1 as a candidate for the cell r2c1.
- The move r2c1:=1 has been eliminated.


... a chain turns up. The solution is still far from straightforward and requires Tables but at least it's obtained logically:

Code: Select all

Consider the chain r2c5-1-r2c3-1-r9c3-1-r9c7-1-r6c7-1-r6c5.
The cell r6c5 must contain the value 1 if the cell r2c5 doesn't.
Therefore, these two cells are the only candidates for the value 1 in Column 5.
- The move r5c5:=1 has been eliminated.
Consider the chains r1c4-7-r2c5-1-r6c5-4-r6c6 and r1c4-9-r1c6~9~r6c6.
When the cell r6c6 contains the value 9, one chain states that the cell r1c4 contains the value 7 while the other says it doesn't - a contradiction.
Therefore, the cell r6c6 cannot contain the value 9.
- The move r6c6:=9 has been eliminated.
Consider the chains r1c7~7~r1c4-7-r2c5-1-r2c3-1-r9c3~4~r9c7, r1c7-4-r3c9-4-r3c2-5-r3c9-4-r1c7 and r1c7~7~r1c4-7-r2c5-1-r6c5-4-r8c5~4~r8c7.
Whichever of the 3 candidates in Column 7 contains the value 4, the cell r1c7 does not contain the value 7.
- The move r1c7:=7 has been eliminated.
Consider the chains r3c2-5-r3c9-4-r1c7~3~r8c7 and r3c9~5~r8c9-5-r8c7.
Whichever of the 2 candidates in Row 3 contains the value 5, the cell r8c7 does not contain the value 3.
- The move r8c7:=3 has been eliminated.
Consider the chains r1c8~3~r1c7-3-r9c7-1-r6c7-1-r6c5 and r1c8~3~r3c8-3-r3c1-1-r2c3-1-r2c5.
Whichever of the 2 candidates in Column 5 contains the value 1, the cell r1c8 does not contain the value 3.
- The move r1c8:=3 has been eliminated.
Consider the chains r7c6~4~r6c6-4-r6c5-1-r6c7-1-r9c7, r7c2~4~r9c3-1-r9c7 and r7c9~4~r3c9-4-r1c7-3-r9c7.
Whichever of the 3 candidates in Row 7 contains the value 4, the cell r9c7 does not contain the value 1.
- The move r9c7:=1 has been eliminated.
The cell r9c3 is the only candidate for the value 1 in Row 9.


... and that's the first move in place - I won't bore you with the rest of it. I'd be interested to here from anyone who could solve this puzzle without assistance from Sherlock.

I'm about to upgrade my Sherlock implementation to consider pairs of rows (or columns) that don't lie in the same block. I see that r.e.s. has had some success with this method.

[Brendan]

Fascinating, and I am glad that it seems a genuine alternative.

Have you attempted using Sherlock in a similtaneous manner? i.e.

Sherlock R1 with R2 -> Resultant Compatible Rows (RCR1),

Sherlock R1 with R3 -> RCR2,

Sherlock RCR1 with RCR2 -> Result

Brendan

[stuartn]

I'd be interested to here from anyone who could solve this puzzle without assistance from Sherlock

or can find the chain that forces R1C2 = 3.... it's stumping me at the moment - but that cell holds they key to the grid.

stuartn

[Sue De Coq]

As soon as Sherlock comparison of R1 & R2 allows me to eliminate, I revert to the easier methods. Of course, should they fail, I return to Sherlock whereupon, as soon as R3 comes into play, I've effectively compared R1, R2 & R3. But no, I don't compare R3 with the output of R1 & R2 (or any other arrangement of these) straight away.

It should be possible to compare three rows simultaneously, though this would be very expensive and might not provide much more information than consecutive comparison of pairs.

Another extension of the idea would be to list all of the possible positions of the value 1 on the grid, then compare that with the possible positions of the value 2. Not one for the purists!

[dgmp]

Very impressive. However when you did the combinations on column 1 and 2, why did you not include the combination 294158637 for column 2? This seems to match with 618247395 in column 1 and prevents you from excluding any candidates at all. Am I missing something ?

[DanO]

Code: Select all

C1: 618|247|395
C2: 294|158|637
C3: ...|...|...


Box 7 is invalid because it contains 2 3's.

Sherlock is however very difficult to verify so mistakes don't get caught. One way to apply it would be to use sherlock to identify possible reductions then look for the implication chains that verify the reductions.

[Brendan]

[quote="]DanO
Sherlock is however very difficult to verify so mistakes don't get caught. One way to apply it would be to use sherlock to identify possible reductions then look for the implication chains that verify the reductions.[/quote]

It can be prone to errors if done manually. Sue de Coq programmed the method in to her susser, so it is highly unlikely that that made a mistake. The key point that Sue was making was that the method can produce a reduction in the candidates where chains did not. I think, at this stage, that their domains for solution may overlap if the end point of the force is found within the boxes that are covered by the Sherlock. Outside that, I would be supprised, but it would be interesting to find out. The two methods are fundamentally different - chains wander around the whole of the grid in a 2D but linear fashion, while Sherlock looks at at least 9 equations simultaneously, searching for partial solutions. I would therefore expect the two methods to have some outcomes that dont overlap.

Brendan

[DanO]

If sherlock finds a reduction then we know there is a chain of logic involving only cells from those sherlocked that will show that reduction. And the converse, if their is a logic chain* involving any set of cells that leads to a reduction then sherlock will find the reduction if all of those cells are included.

[*Except that sherlock does not handle the uniqueness property. Is there a back door using conventional logic that will always arrive at the same reductions as the uniqueness rules? The first step to answering this might be to run sherlock on a set of bands that have unique rectangles and no other simple reductions.]

[Jando]

Consider the following somewhat attractive puzzle:

Code: Select all

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


... I'd be interested to here from anyone who could solve this puzzle without assistance from Sherlock. ...

Well, I haven't yet solved the puzzle and I'm far from sure whether my technique is any good but I could exclude a few more candidates from this puzzle using this technique.

Basically it's similar to an XY-wing (it "only" needs a few more steps than a basic XY-wing however) and like an XY-wing it eliminates candidates. Is this a valid technique or is it trial & error? I wouldn't know. Anyway, it starts like this:



Consider the field r3c2 (marked blue), If this field would be a 4 then the pink marked fields could not legally be a 4 too. So far that's easy. Now imagine that we can prove that some of these pink-marked fields could not be a 4 too if r3c2 would be 5 (the only other candidate). Then we could exclude the candidate 4 from the fields that couldn't be 4 no matter whether r3c2 is a 4 or a 5.

And in the above puzzle it's actually rather easy to show that if the blue field r3c2 would be a 5 then r7c2 must be a 4. That means that 4 can be excluded as candidates for r1c2, r8c2 and r9c2 because they cannot be a 4 no matter whether r3c2 is a 4 or a 5.

(Here's the path to determine that r7c2 must be a 4 if r3c2 is a 5:
If r3c2 = 5 then r3c9 = 4 (only candidate left)
If r3c9 = 4 then r7c9 = 7 (only candidate left)
If r7c9 = 7 then r9c2 = 7 (only 7 left in row 9)
If r3c2 = 5 and r9c2 = 7 then r5cs = 6 (only candidate left)
If r7c9 = 7 then r7c2 <> 3 (naked pair 13 in row 7)

These 5 steps leave only 4 as candidate for r7c2 if r3c2 is 5. )

These eliminations lead me to a 2nd "extended" XY-wing followed by an X-wing and at that point I'm stuck at the moment. ;)

[Carcul]

I'd be interested to here from anyone who could solve this puzzle without assistance from Sherlock.

I have solved this puzzle in four steps without the assistance from Sherlock or T&E. However, my solution uses two complicated multiple implication nice loops and might not be very elegant, but it is logical and short.

Carcul

[Myth Jellies]

Vidarino's POM Analyzer got it in 72 steps. Here is the tail part of the output (so no one else has to analyze it):

Code: Select all

Legend:
1d  -  2j  -  3c  -  4h  -  5d  -  6k  -  7u  -  8b  -  9h

   C1  C2  C3  C4  C5  C6  C7  C8  C9
R1 6   3c  8b  7u  5   9h  4h  2j  1
R2 9h  2j  5d  4   1d  3   6k  8b  7u 
R3 1d  4h  7   6k  2   8b  9   3c  5d 
R4 2j  1   3c  9h  6k  5d  7u  4   8b 
R5 4   5d  9   8b  7u  1d  2   6k  3
R6 7u  8   6k  3c  4h  2j  1d  5   9h 
R7 3c  7u  2   5d  9   6k  8   1d  4h 
R8 8b  6k  4h  1   3c  7   5d  9h  2j 
R9 5   9h  1d  2j  8   4h  3c  7u  6

Step 73.

Done!

Stats:
- Time spent: 417.554 seconds
- Vulnerable pairs: 30
- Substitution reduction (level 0): 43
- Substitution reduction (level 1): 26
- Single candidate left: 23
- All-pattern cells: 32


On the other hand...417.554 seconds. Vidar's ISP is going to be pleased as punch with him

[tarek]

My solver ALMOST can provide a simple logical solution, as my solver is still in development, an explanation is not provided for one of the vital steps needed. So this may not be a valid walkthrough, but I couldn't resist posting it.

Code: Select all

*-----------------------------------------------------------------------------------*
| 6        234      348     | 789      5        89      | 347      2378     1       |
| 189      259      158     | 4        167      3       | 567      2678     2578    |
| 138      45       7       | 68       2        168     | 9        368      45      |
|---------------------------+---------------------------+---------------------------|
| 237      1        356     | 2356789  367      25689   | 67       4        789     |
| 4        567      9       | 5678     167      1568    | 2        1678     3       |
| 237      8        36      | 23679    13467    12469   | 167      5        79      |
|---------------------------+---------------------------+---------------------------|
| 137      3467     2       | 356      9        456     | 8        137      47      |
| 389      3469     3468    | 1        346      7       | 345      239      245     |
| 5        3479     134     | 23       8        24      | 1347     1379     6       |
*-----------------------------------------------------------------------------------*
Candidates in r2c7 will force r9c7 to have only 134 as valid Candidates
r2c7=5: r2c7=5 => r3c9=4 => r7c9=7 => r9c7<>7 => r9c7=134
r2c7=6: r2c7=6 => r4c7=7 => r9c7<>7 => r9c7=134
r2c7=7: r2c7=7 => r9c7<>7 => r9c7=134
Threfore r9c7=134
*-----------------------------------------------------------------------------------*
| 6        234      348     | 789      5        89      | 347      2378     1       |
| 189      259      158     | 4        167      3       | 567      2678     2578    |
| 138      45       7       | 68       2        168     | 9        368      45      |
|---------------------------+---------------------------+---------------------------|
| 237      1        356     | 2356789  367      25689   | 67       4        789     |
| 4        567      9       | 5678     167      1568    | 2        1678     3       |
| 237      8        36      | 23679    13467    12469   | 167      5        79      |
|---------------------------+---------------------------+---------------------------|
| 137      3467     2       | 356      9        456     | 8        137      47      |
| 389      3469     3468    | 1        346      7       | 345      239      245     |
| 5        3479     134     | 23       8        24      | 134      1379     6       |
*-----------------------------------------------------------------------------------*
r9c2 Must only have 79 as valid Candidates (79 is a Hidden Double in Row 9)
r9c8 Must only have 79 as valid Candidates (79 is a Hidden Double in Row 9)
*-----------------------------------------------------------------------------------*
| 6        234      348     | 789      5        89      | 347      2378     1       |
| 189      259      158     | 4        167      3       | 567      2678     2578    |
| 138      45       7       | 68       2        168     | 9        368      45      |
|---------------------------+---------------------------+---------------------------|
| 237      1        356     | 2356789  367      25689   | 67       4        789     |
| 4        567      9       | 5678     167      1568    | 2        1678     3       |
| 237      8        36      | 23679    13467    12469   | 167      5        79      |
|---------------------------+---------------------------+---------------------------|
| 137      3467     2       | 356      9        456     | 8        137      47      |
| 389      3469     3468    | 1        346      7       | 345      239      245     |
| 5        79       134     | 23       8        24      | 134      79       6       |
*-----------------------------------------------------------------------------------*
Candidates in r7c1 will force r3c2 to have only 4 as valid Candidates
This would be a triple implication chain involving only naked/hidden singles
*-----------------------------------------------------------------*
| 6      23     38    | 7      5      9     | 4      28     1     |
| 9      25     58    | 4      1      3     | 67     268    78    |
| 1      4      7     | 68     2      68    | 9      3      5     |
|---------------------+---------------------+---------------------|
| 237    1      356   | 35689  367    2568  | 67     4      789   |
| 4      567    9     | 568    67     1     | 2      68     3     |
| 237    8      36    | 369    4      26    | 1      5      79    |
|---------------------+---------------------+---------------------|
| 37     367    2     | 356    9      56    | 8      1      4     |
| 8      36     4     | 1      36     7     | 5      9      2     |
| 5      9      1     | 2      8      4     | 3      7      6     |
*-----------------------------------------------------------------*
Eliminating 6 From r5c2 (Column 3 & Box 4 Box-line interaction)
*-----------------------------------------------------------------*
| 6      23     38    | 7      5      9     | 4      28     1     |
| 9      25     58    | 4      1      3     | 67     268    78    |
| 1      4      7     | 68     2      68    | 9      3      5     |
|---------------------+---------------------+---------------------|
| 237    1      356   | 35689  367    2568  | 67     4      789   |
| 4      57     9     | 568    67     1     | 2      68     3     |
| 237    8      36    | 369    4      26    | 1      5      79    |
|---------------------+---------------------+---------------------|
| 37     367    2     | 356    9      56    | 8      1      4     |
| 8      36     4     | 1      36     7     | 5      9      2     |
| 5      9      1     | 2      8      4     | 3      7      6     |
*-----------------------------------------------------------------*
Candidates in r4c5 will force r6c6 to have only 2 as valid Candidates
r4c5=3: r4c5=3 => r8c5=6 => r8c2=3 => r1c2=2 => r1c8=8 => r1c3=3 => r6c3=6 => r6c6=2
r4c5=6: r4c5=6 => r6c6=2
r4c5=7: r4c5=7 => r5c5=6 => r6c6=2
Threfore r6c6=2


and then singles