The New Sudoku Players' Forum

[DanO]

Sudoku Susser gets stuck at this position in Menneske.no Super Hard #6753298 and must resort to advanced techniques.

Code: Select all

+-------------------+-------------------+-------------------+
| 235   359   2359  | 7     14    59    | 8     14    6     |
| 57    6     8     | 3     14    59    | 149   2     17    |
| 4     79    1     | 8     6     2     | 39    379   5     |
+-------------------+-------------------+-------------------+
| 1235  1359  2359  | 6     7     8     | 124   145   123   |
| 13    4     6     | 5     2     13    | 7     8     9     |
| 8     1357  2357  | 4     9     13    | 6     15    123   |
+-------------------+-------------------+-------------------+
| 6     135   4     | 29    38    7     | 12359 39<   128   |
| 9     2     357   | 1     38    4     |>35    6    >78    |
| 137   8     37    | 29    5     6     | 129  <379>  4     |
+-------------------+-------------------+-------------------+

But I noticed that in block 9 the posibilities <379> at R9C8 could all be eliminated if the cells at R8C7, R7C8 and R8C9 had the right values. The forcing chain R8C7=3 -> R7C8=9, R8C5=8 -> R8C9=7 provides those values therefore R8C7=5.

This may be a different class of simple forcing chains (at least Sudoku Susser doesn't spot it). I don't know yet if they happen often enough to be worth searching for but it's certainly easier than tabling.

The basic algorithm is to pick a target with 2 or 3 possibilities and see if there is a buddy set with only 2 possibilities each that can eliminate all the possibilities of the target. Then look for the forcing chains that will set those buddys and if they start from the same initial value of some cell then that value can be eliminated from that cell.

Here is another example from Menneske.no Very Hard #3394786

Code: Select all

+----------------+----------------+----------------+
| 379  479  8    | 36   137  167  | 2    5    1479 |
| 367  2467 1    | 5    237  9    | 8    34   47   |
| 5    279  29   | 238  4    1278 | 13*  39   6    |
+----------------+----------------+----------------+
| 69   269  5    | 1    8    3    | 7  <249>  249  |
| 4    8    7    | 269  29   26   | 5    1    3    |
| 1    3    29   | 4    57   57   | 6    8    29   |
+----------------+----------------+----------------+
| 2    19   4    | 389  6    18   | 13   7    5    |
| 8    15   6    | 7    135  4    | 9    23   12   |
| 79   1579 3    | 29   1259 125  | 4    6    8    |
+----------------+----------------+----------------+

The possibilities <249> are all removed from R4C8 if R3C7=3.

[Shazbot]

I'm not sure how you got to the point you're at in box 6 (in your first puzzle). I could get this close to your candidate list:

Code: Select all

 *--------------------------------------------------------------------*
 | 235    359    2359   | 7      14     59     | 8      14     6      |
 | 57     6      8      | 3      14     59     | 149    2      17     |
 | 4      79     1      | 8      6      2      | 39     379    5      |
 |----------------------+----------------------+----------------------|
 | 1235   1359   2359   | 6      7      8      | 12345  1345   123    |
 | 13     4      6      | 5      2      13     | 7      8      9      |
 | 8      1357   2357   | 4      9      13     | 6      135    123    |
 |----------------------+----------------------+----------------------|
 | 6      135    4      | 29     38     7      | 12359  1359   1238   |
 | 9      2      357    | 1      38     4      | 35     6      378    |
 | 137    8      37     | 29     5      6      | 1239   1379   4      |
 *--------------------------------------------------------------------*


From this point, Simple Sudoku eliminates 7s from a number of cells using colours, leaving you with

Code: Select all

 *--------------------------------------------------------------------*
 | 235    359    2359   | 7      14     59     | 8      14     6      |
 | 57     6      8      | 3      14     59     | 149    2      1      |
 | 4      9      1      | 8      6      2      | 39     379    5      |
 |----------------------+----------------------+----------------------|
 | 1235   1359   2359   | 6      7      8      | 12345  1345   123    |
 | 13     4      6      | 5      2      13     | 7      8      9      |
 | 8      1357   235    | 4      9      13     | 6      135    123    |
 |----------------------+----------------------+----------------------|
 | 6      135    4      | 29     38     7      | 12359  1359   1238   |
 | 9      2      35     | 1      38     4      | 35     6      378    |
 | 13     8      37     | 29     5      6      | 1239   139    4      |
 *--------------------------------------------------------------------*


at which point the puzzle can be solved with naked singles.

[MCC]

...
Here is another example from Menneske.no Very Hard #3394786

Code: Select all

+----------------+----------------+----------------+
| 379  479  8    | 36   137  167  | 2    5    1479 |
| 367  2467 1    | 5    237  9    | 8    34   47   |
| 5    279  29   | 238  4    1278 | 13*  39   6    |
+----------------+----------------+----------------+
| 69   269  5    | 1    8    3    | 7  <249>  249  |
| 4    8    7    | 269  29   26   | 5    1    3    |
| 1    3    29   | 4    57   57   | 6    8    29   |
+----------------+----------------+----------------+
| 2    19   4    | 389  6    18   | 13   7    5    |
| 8    15   6    | 7    135  4    | 9    23   12   |
| 79   1579 3    | 29   1259 125  | 4    6    8    |
+----------------+----------------+----------------+

The possibilities <249> are all removed from R4C8 if R3C7=3.

They are not all removed.

If r3c7=3 then r7c7=1=>r8c9=2=>r8c8=3=>r4c8=2

If r3c7=1 then r2c8 or r3c8=3=>r4c8=4 or 9

[Brendan]

Sudoku Susser gets stuck at this position in Menneske.no Super Hard #6753298 and must resort to advanced techniques.

Code: Select all

+-------------------+-------------------+-------------------+
| 235   359   2359  | 7     14    59    | 8     14    6     |
| 57    6     8     | 3     14    59    | 149   2     17    |
| 4     79    1     | 8     6     2     | 39    379   5     |
+-------------------+-------------------+-------------------+
| 1235  1359  2359  | 6     7     8     | 124   145   123   |
| 13    4     6     | 5     2     13    | 7     8     9     |
| 8     1357  2357  | 4     9     13    | 6     15    123   |
+-------------------+-------------------+-------------------+
| 6     135   4     | 29    38    7     | 12359 39<   128   |
| 9     2     357   | 1     38    4     |>35    6    >78    |
| 137   8     37    | 29    5     6     | 129  <379>  4     |
+-------------------+-------------------+-------------------+

But I noticed that in block 9 the posibilities <379> at R9C8 could all be eliminated if the cells at R8C7, R7C8 and R8C9 had the right values. The forcing chain R8C7=3 -> R7C8=9, R8C5=8 -> R8C9=7 provides those values therefore R8C7=5.

Did you notice that the uniqueness loop at R1C5, R2C5, R1C8 and R2C7 would also advance the puzzle?

Brendan

[Brendan]

Forget the above, I have over generalised the uniqueness test. Sorry. I should pay more attention when I'm tired.

Brendan

[rubylips]

Some observations:

i. The chain r8c3-7-r8c9-7-r2c9-7-r2c1-7-r9c1 cracks the problem as it tells us that there can't be a 7 at r8c3 or r9c1.

ii. Brendan's Uniqueness Cycle would be valid if it were extended to include r4c7 and r4 c8 - however, the fact that three of the cells in this cycle have candidates other than 1 and 4 means that it wouldn't lead to an elimination.

iii. I feel that DanO's problem could be expressed as a more general form of the Two-Sector Disjoint Subsets pattern - though I'm not sure how. The cells r8c7 and r8c9 lie at the intersection of Row 8, which introduces the constraint that 3 AND 8 can't be chosen for the cells, and Box 9 (cells r7c8 and r9c8), which introduces the constraint that 3 AND 7 can't be chosen. Since neither 3 & 7 nor 3 & 8 are legitimate choices, 3 can't be chosen. I shall ponder awhile and attempt to generalize this principle.

[bennys]

Code: Select all

+----------------------+----------------------+----------------------+
| 4569   479    567    | 2578   178    1257   | 18     3      49     |
| 1      2      8      | 4      3      9      | 7      6      5      |
| 3459   479    357    | 578    6      157    | 18     49     2      |
+----------------------+----------------------+----------------------+
| 2358   178    2357   | 236789 1789   12367  | 4      1289   13689  |
| 48     6      23     | 89     5      14     | 23     7      189    |
| 2348   1478   9      | 23678  178    123467 | 5      128    1368   |
+----------------------+----------------------+----------------------+
| 7      89     14     | 3569   2      356    | 36     148    1348   |
| 26     3      26     | 1      4      8      | 9      5      7      |
| 89     5      14     | 3679   79     367    | 236    1248   1348   |
+----------------------+----------------------+----------------------+

because of R5C1 we cant have R5C4 = 8 and R5C6 = 4
but if R5C4 = 8 and R5C6 = 1 R1C5 needs to be both 1 and 8.
So R5C4 = 9

[DanO]

I'm not sure how you got to the point you're at in box 6 (in your first puzzle).

That part was discussed in a different thread. There is a Type-4 Unique Rectangle that can be used to remove the 3's from R7C9, R8C9.

I started this thread to discuss the process of spotting specific forms of logic chains that can be used to progress the puzzle. Coloring, Tabling and other advanced techniques can be used to solve these puzzles. But what I am looking for is a method that doesn't require extra reams of paper.

Potential bases of these forms are easy enough to spot and it's not difficult to follow the chains back to locate a common origin.

[Jeff]

Sudoku Susser gets stuck at this position in Menneske.no Super Hard #6753298 and must resort to advanced techniques.

Code: Select all

+-------------------+-------------------+-------------------+
| 235   359   2359  | 7     14    59    | 8     14    6     |
| 57    6     8     | 3     14    59    | 149   2     17    |
| 4     79    1     | 8     6     2     | 39    379   5     |
+-------------------+-------------------+-------------------+
| 1235  1359  2359  | 6     7     8     | 124   145   123   |
| 13    4     6     | 5     2     13    | 7     8     9     |
| 8     1357  2357  | 4     9     13    | 6     15    123   |
+-------------------+-------------------+-------------------+
| 6     135   4     | 29    38    7     | 12359 39<   128   |
| 9     2     357   | 1     38    4     |>35    6    >78    |
| 137   8     37    | 29    5     6     | 129  <379>  4     |
+-------------------+-------------------+-------------------+

But I noticed that in block 9 the posibilities <379> at R9C8 could all be eliminated if the cells at R8C7, R7C8 and R8C9 had the right values. The forcing chain R8C7=3 -> R7C8=9, R8C5=8 -> R8C9=7 provides those values therefore R8C7=5.

This may be a different class of simple forcing chains (at least Sudoku Susser doesn't spot it). I don't know yet if they happen often enough to be worth searching for but it's certainly easier than tabling.

What you got there is a forcing net, not a forcing chain as defined in Susser where a node implies only the next node downstream. In your description, the node r8c7=3 implies both r7c8=9 and r8c5=8; therefore it's a forcing net rather than chain.

However, if you choose to start the implications from node r9c8, then you would get a triple implication chain, ie. one chain with 3 implications where each node implies just the next node downstream. Thus:

r9c8=3 => r8c7=5
r9c8=7 => r8c9=8 => r8c5=3 => r8c7=5
r9c8=9 => r7c6=3 => r8c7=5
Therefor r8c7=5

Both forcing net and triple implication chain have yet to be incorporated in Susser. Triple implication chain is not a new technique but it is not easy to spot manually sometimes. One way to spot triple implication chain is via the bilocation/bivalue plot where the labelled edges of a node with 3 candidates are drawn as a trivalue tripod.

[DanO]

But how would you find the triple implication chain short of testing every potential starting cell and mapping all the chains then comparing the results looking for a common node. The key is being able to spot a potential pattern manually.

What I probably need to do at this point is a short statistical sample to see how often these patterns can be spotted in puzzles that don't succumb to easier techniques.

[DanO]

Menneske.no Super Hard #3232658

Code: Select all

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

+-------------------+-------------------+-------------------+
| 2     34    35    | 7     456   56    | 8     9     1     |
|>17<  <147>  59    | 3     8     59    | 6     2    >47<   |
|*78    6     89    | 14    1249  129   | 3    >47<   5     |
+-------------------+-------------------+-------------------+
| 4     127   17    | 8     127   3     | 9     5     6     |
| 9     1237  36    | 156   12567 1257  | 147   1347  8     |
| 178   5     368   | 9     167   4     | 17    137   2     |
+-------------------+-------------------+-------------------+
| 3     9     2     | 145   1457  8     | 1457  6     47    |
| 5     178   17    | 146   3     167   | 2     1478  9     |
| 6     178   4     | 2     1579  1579  | 157   178   3     |
+-------------------+-------------------+-------------------+

Target R2C2 == <147>
T<>1 <- R2C1=1 <- R3C1=7*
T<>7 <- R3C1=7*
T<>4 <- R2C9=4 <- R3C8=7 <- R3C1=7*

Therefore R3C1 != 7
Which leads to a complete solution.
Score: Eliminator 1, Sudoku 0.

Menneske.no Super Hard #165055
No candidates for elimination
Score: Eliminator 1, Sudoku 1

Menneske.no Super Hard #4620791
Target R7C7 == <239>
T<>3 <- R8C7=3 <- R9C8=9! <- R2C8=3*
T<>9 <- R9C8=9!
T<>2 <- R9C9=2 <- (R4C9=9 | R2C9=6*)
* <- R2C1=9 or R3C7=9
Solved! Score: Eliminator 2, Sudoku 1

Menneske.no Super Hard #4880614
Possible targets but no eliminator found
Score: Eliminator 2, Sudoku 2

Menneske.no Super Hard #4871517"
I was about to give up on this one but realized that most of the chains were even cycles so I needed to find an odd cycle to make it work.

Code: Select all

+----------------------+----------------------+----------------------+
| 469    8      5      | 7      24     3      | 2469   1      469    |
| 7      1      49     | 8      6      24     | 239    5      349    |
| 3      2      46     | 9      1      5      | 467    467    8      |
+----------------------+----------------------+----------------------+
| 8      5      3      | 6      49     1      | 49     2      7      |
| 169    4      169    | 2      5      7      | 369    8      369    |
| 2      69     7      | 3      489    48     | 5      469    1      |
+----------------------+----------------------+----------------------+
| 5      69     4689   | 1      3      68     | 46789  4679   2      |
| 1469   3      124689 | 5      7      268    | 14689  469    469    |
| 16     7      1268   | 4      28     9      | 168    3      5      |
+----------------------+----------------------+----------------------+

Target R1C1 == <469>
T<>4 <- R3C3=4!
T<>9 <- R2C3=9 <- R3C3=4!
and block 6 provides the odd chain
T<>6 <- R5C1=1 <- (R6C2=9 <- ) R5C3=6
and R3C3=4 <- R5C3=6
therefore R5C3<>6
It's a little more involved that the first description of the eliminator but since I found it without resorting to extra tables or marking I'm still going to count it. Deducing that there cannot be a 6 in C3B7 solves this puzzle. Maybe there is an easier way to solve this but I need to move on. Since the eliminator didn't completely solve the puzzle I'll call this one a partial.
Score: Score: Eliminator 2, Sudoku 2, Partial 1

Menneske.no Super Hard #5017926
not quite enough pairs
Score: Score: Eliminator 2, Sudoku 3, Partial 1

Menneske.no Super Hard #4010174
The 3 cycle with <467> in B2,B5 might indicate a possibility here but the outside chains are limited.
R4C3=8 eliminates <135> from R8C8
Progress was made but not solved
Score: Eliminator 2, Sudoku 3, Partial 2

Menneske.no Super Hard #6678464
I'm sure there is one in here but I just can't find it.
I did however find a new variety of unique rectangle.
Score: Eliminator 2, Sudoku 4, Partial 2

========================================================================

Summary:
25 puzzles were tested from the Menneske.no difficulty level 5. Out of 8 puzzles that were unsolved with existing rules, The Eliminator found reductions in 4 and half of those led to a complete solution.

Obviously this is too small of a sample to make a definite conclusion but it does show that the Eliminator is promising.

[bennys]

Why?

[DanO]

Oops, I made a mistake on the first one and R3C7=8 just happens to be a lucky guess that easily solves the puzzle. Since I'm looking for a technique that avoids guessing I can't count that one.

[DanO]

Some observations:

iii. I feel that DanO's problem could be expressed as a more general form of the Two-Sector Disjoint Subsets pattern.

Your comment got me to think about looking for these patterns in a different way. Instead of looking for the potential target and eliminator cells, Try to map out the closed chains and look for the constraints between them. This puzzle is a nice example

Code: Select all

Puzzle: Menneske.no Super Hard #6507115
+-------+-------+-------+
| . . . | . . 9 | . . . |
| . 8 . | . . . | . 9 . |
| 7 5 9 | 1 3 2 | 6 4 8 |
+-------+-------+-------+
| . 6 2 | . 9 1 | 3 7 . |
| 1 3 . | 7 . 6 | . 2 9 |
| 5 9 7 | 2 4 3 | 8 6 1 |
+-------+-------+-------+
| 3 4 . | 9 . 8 | . 5 2 |
| . 7 . | . . . | . 8 . |
| . . . | . . . | . . . |
+-------+-------+-------+

+----------------+----------------+----------------+
| 246  12   346  | 4568 5678 9    | 257  13   357  |
| 246  8    1346 | 456  567  457  | 1257 9    357  |
| 7    5    9    | 1    3    2    | 6    4    8    |
+----------------+----------------+----------------+
| 48   6    2    | 58   9    1    | 3    7    45   |
| 1    3    48   | 7    58   6    | 45   2    9    |
| 5    9    7    | 2    4    3    | 8    6    1    |
+----------------+----------------+----------------+
| 3    4    16   | 9    167  8    | 17   5    2    |
| 269  7    156  | 3456 1256 45   | 149  8    346  |
| 2689 12   568  | 3456 2567 457  | 479  13   3467 |
+----------------+----------------+----------------+

The <48><58><45> in R4 is a closed loop with odd length. The <1>'s in R1 (and R9) form a closed loop with even length. I haven't worked out why but it appears the odd/even pairing is somehow important.

The <246>'s in R1C1,R2C2 form the constraint that R4C1!=4 or R1C2!=2. The <357>'s in R1C9,R2C9 form the constraint that R4C9!=5 or R1C8!=3. These constraints force R4C1=8

[rubylips]

Here's some chat based upon the previous post. Since it essentially restates the post in my preferred vocabulary, it could be of limited interest!

I'd like to ignore DanO's candidate grid for a moment and consider the initial problem, which features two classic Two Sector Disjoint Subsets patterns, one in the cells r1c1, r1c2, r1c3, r1c8 and r2c1, the other in r1c2, r1c7, r1c8, r1c9 and r2c9. Between them, they allow eight eliminations:

Code: Select all

The cells r1c1, r1c2 and r1c3 contain 1 value from {1,3} and 2 values from {2,4,6}.
The values 1 and 3 occupy 2 of the cells r1c1, r1c2, r1c3 and r1c8 in some order.
The values 2, 4 and 6 occupy 3 of the cells r1c1, r1c2, r1c3 and r2c1 in some order.
The cells r1c7, r1c8 and r1c9 contain 1 value from {1,2} and 2 values from {3,5,7}.
The values 1 and 2 occupy 2 of the cells r1c7, r1c8, r1c9 and r1c2 in some order.
The values 3, 5 and 7 occupy 3 of the cells r1c7, r1c8, r1c9 and r2c9 in some order.
- The moves r1c7:=1, r1c9:=3, r2c3:=4, r2c3:=6, r1c1:=2, r1c3:=1, r2c7:=5 and r2c7:=7 have been eliminated.


Once the following X-Wings and Turbot Fish have been spotted (DanO spots these before his candidate grid is quoted),

Code: Select all

Consider the chain r9c2-1-r1c2-1-r1c8-1-r9c8.
The cell r9c8 must contain the value 1 if the cell r9c2 doesn't.
Therefore, these two cells are the only candidates for the value 1 in Row 9.
- The moves r9c3:=1, r9c5:=1 and r9c7:=1 have been eliminated.
Consider the chain r1c4~5~r1c7-5-r5c7-5-r4c9-5-r4c4.
When the cell r1c4 contains the value 5, so does the cell r4c4 - a contradiction.
Therefore, the cell r1c4 cannot contain the value 5.
- The move r1c4:=5 has been eliminated.
Consider the chain r1c3-4-r5c3-4-r4c1-8-r4c4-8-r1c4.
When the cell r1c4 contains the value 4, some other value must occupy the cell r1c3, which means that the value 8 must occupy the cell r1c4 - a contradiction.
Therefore, the cell r1c4 cannot contain the value 4.
- The move r1c4:=4 has been eliminated.
The value 4 in Box 1 must lie in Row 1.
- The move r2c1:=4 has been eliminated.


the candidate grid is as follows:

Code: Select all

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


It's possible to solve the puzzle from here with a forced chain that uses strong links only:

Code: Select all

Consider the chain r1c7-2-r1c2-1-r1c8-3-r1c3-4-r5c3-4-r5c7-5-r1c7.
When the cell r1c7 contains the value 5, it likewise contains the value 2 - a contradiction.
Therefore, the cell r1c7 cannot contain the value 5.
- The move r1c7:=5 has been eliminated.
The cell r5c7 is the only candidate for the value 5 in Column 7.


after which the puzzle is straightforward.
However, DanO proposes a hybrid Disjoint Subsets/Chain approach that uses Disjoint Subsets analysis to create links more abstract than strong or weak links such as r4c1=4 => r1c2<>2 (and r1c3<>6, r2c3<>6) or r1c8=3 => r4c9<>5 (and r9c9<>7). With these links in place, the crucial chain is:
r4c1=4 => r1c2=1 => r1c8=3 => r4c8=4 - a contradiction.
This chain is three links shorter than the pure strong-link alternative but, given that most people prefer not to seek anything more complicated than bivalue/bilocation chains, some might not see that as an advance. However, the idea of the hybrid Disjoint Subsets/Chain approach is interesting and certainly worthy of further study.