The Almost Sue De Coq -Part 2 (ASI#2b)

Advanced methods and approaches for solving Sudoku puzzles

The Almost Sue De Coq -Part 2 (ASI#2b)

Postby DonM » Fri Nov 14, 2008 8:21 pm

This is a continuation of the original Almost Sue De Coq subject here:
http://forum.enjoysudoku.com/viewtopic.php?t=6411

In that thread, I stated to the effect that even if turned out that eliminations using the almost Sue De Coq (SDC) pattern could be replicated by other means, since I am always looking for the complete SDC anyway, the finding of an almost SDC will still be useful because it both provides a relatively obvious menu of weak links and yet, it is no more assumptive than a simple ALS and just as easy to apply.

After further experience looking for and applying the almost SDC, it is becoming clearer to me that this is more than just an occasionally useful pattern in advanced solving. First, it turns out that the almost SDC is actually relatively common in puzzles. Typically, during a puzzle almost SDC patterns often present themselves and then are almost just as often destroyed as the solving process continues, but likewise, as candidates are removed in certain cells, new almost SDC patterns present themselves. (However, few almost SDCs go on to be full SDCs.) Second, by the very nature of the SDC pattern, it turns out that sometimes more than the ‘usual’ weak link exit points are immediately available in a way that you wouldn’t ordinarily find with other patterns. Third, as the example below indicates, more than one elimination is sometimes possible with one almost SDC pattern.

Finally, is the fact that it no longer matters to me (if it ever did) whether the eliminations possible from a full SDC or an almost SDC can be replicated by other means, mainly because while it may be easy enough to backtrack from a presented SDC or almost SDC based elimination and produce a comparable elimination by other means, it is not necessarily as easy to do so if presented with the puzzle and the SDC or almost SDC not identified. For instance, a SDC can often be replicated by a doubly-linked ALS pattern, but even though I have reasonable experience finding basic doubly-linked ALSs (the examples of those patterns in The ALS Chains Tutorial are mine), while I can find a SDC fairly quickly, I can’t nearly as easily find the associated doubly-linked ALS. Furthermore, I would probably miss it altogether unless I had already found the associated SDC.

Overall, the usefulness of the almost SDC depends upon two main factors: One is the use of the simplified directions for finding a basic SDC:

In a row or column within the same box, look for a core of 4 digit values in 2 cells or 5 digit values in 3 cells. Now, on that same row or column, look for a bivalue cell where the digits are the same as 2 of those in the core. Then, in the same box as the core, look for a bivalue cell with 2 digits from the core, but not the same digits as in the other bivalue cell. If the above are present, then on that row or column, you can eliminate all the digits equal to the digits in the bivalue cell on the same row or column and in the box that contains the core, you can eliminate all the digits equal to the bivalue cell there. You can also eliminate all digits in the row or column or in the box equal to any digit still remaining in the core but not present in the two bivalue cells.

(Please see
http://forum.enjoysudoku.com/viewtopic.php?t=6410&postdays=0&postorder=asc&start=0 for descriptions of the more advanced SDC patterns.)

The other factor is that the almost SDC pattern presents an immediate menu of weak link exits without any further search necessary. Since, considering the power of the pattern, IMO, one should be looking for SDC anyway, the finding of almost SDC patterns is just a straightforward natural progression.

The following examples from a single puzzle illustrate points made above:

Original Puzzle:
Code: Select all
. 3 .|1 . 9|. 6 .
. . 1|. . .|9 2 .
6 . .|. . .|. 4 1
-----+-----+-----
. . .|7 3 .|. . .
7 . .|. 2 .|. . 8
. . .|. 9 6|. . .
-----+-----+-----
8 5 .|. . .|. . 4
. 6 2|. . .|5 . .
. 4 .|2 . 7|. 8 .


Puzzle as presented in examples (this is very close to the SSTS position):
Code: Select all
.---------------------.---------------------.---------------------.
| 2      3      458   | 1      478    9     | 78     6      57    |
| 45     78     1     | 34568  4678   458   | 9      2      357   |
| 6      789    589   | 358    78     2     | 38     4      1     |
:---------------------+---------------------+---------------------:
| 459    1289   45689 | 7      3      1458  | 146    159    269   |
| 7      19     34569 | 45     2      145   | 1346   1359   8     |
| 345    128    3458  | 458    9      6     | 1347   1357   237   |
:---------------------+---------------------+---------------------:
| 8      5      7     | 69     16     3     | 2      19     4     |
| 139    6      2     | 489    148    48    | 5      1379   379   |
| 139    4      39    | 2      5      7     | 136    8      369   |
'---------------------'---------------------'---------------------'



Image

But for the 2 in r6c9, the basic Sue De Coq pattern is present: the core blue cells (an aals with 1,3,5,7,9 in 3 cells, r456c8), the brown cell A, r6c9, with 3,7 and the green cell C, r7c8, with 1,9. The logic is straightforward: If not 2 in r6c9 then the Sue De Coq is true and any of the circled green cells are valid weak link ‘targets’. However, some additional targets are immediately available (though indirectly): Since the 3s in r56c7 and the 7 in r6c7 are all targets, due to the aals pattern in r456c7, 1 and 6 can be used individually or as a block in r9c7: aals(37=146)r456c7 - (16)r9c7. Of course, they are available indirectly and that has to be indicated in any notation, but the point is that these targets are almost as obvious and as available for use as the regular targets are and due to the very construct of a SDC and the possible eliminations, these extra ‘obvious’ targets likely occur frequently enough to make it worthwhile to be on the watch for them. They may also help simplify chains as shown later on below.


Image

This is the same grid at the same point as the previous example. The blue lines indicate strong links, the green lines, weak links. The path to the eliminations should be relatively easy to figure out. The 9 in r4c2 is eliminated first and then the chain is continued from r3c2 to r5c2 as indicated by the interrupted lines leading to the elimination of the 1 in r4c2. Needless to say, the removal of 2 candidates in one cell leaving available strong links in r4c2 and for the 1 and 9 in c2 is a very helpful way to start the solution of this puzzle.


Image

This is the same set of eliminations as in the previous example, but instead using the additional ‘indirect’ targets as described in the first example. The simpler chain path as compared to the previous one should be obvious. Just to be clear, it is not inferred that the aals pattern in r456c7 is some sort of previously unrecognized pattern. On the contrary, the pattern itself would be obvious to experienced solvers. What is of interest is the fact that it is so easy to pick out as a possible part of an almost SDC pattern and that since it may occur as part of some almost SDC patterns, it adds to the potentially available ‘menu’ of weak link targets.


Image

Finally, is a third elimination at the same point in the puzzle used in the previous examples, but using a totally different pathway. The chain should be self-explanatory. Note that this elimination must come after the first two eliminations since it destroys the almost SDC pattern.

Therefore, in these examples a single almost SDC produces 3 potentially useful eliminations near the beginning of a difficult puzzle. All of them were picked out fairly quickly once the almost SDC was identified. The real point here is not that there are no other ways to achieve these eliminations, but that once one is familiar with the SDC pattern itself, this may well be the easiest way to find these particular eliminations. (FWIW: one particular alternative chain to achieve the above elimination does not require the almost SDC, but does require the previous two eliminations.)


(Puzzle credit: This is the UK forum Weekly Extreme #112. Of possible interest: it has already been discussed on this forum close to this point of the puzzle (almost the SSTS position) with some early solving already shown ( http://forum.enjoysudoku.com/viewtopic.php?t=6453&start=0 ))
Last edited by DonM on Sun Nov 16, 2008 1:48 pm, edited 4 times in total.
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby re'born » Fri Nov 14, 2008 8:46 pm

Don,

As usual, a fantastic job of breaking down a strategy with excellent visuals. Would you post the grids in text format as well so that I can follow along in Simple Sudoku?

A correction:
DonM wrote:If not 3 in r6c9 then the Sue De Coq is true and any of the circled green cells are valid weak link ‘targets’.

Presumably, this should say "If not 2 in r6c9..."
re'born
 
Posts: 551
Joined: 31 May 2007

Postby DonM » Sat Nov 15, 2008 11:17 am

re'born wrote:Don,

As usual, a fantastic job of breaking down a strategy with excellent visuals. Would you post the grids in text format as well so that I can follow along in Simple Sudoku?


Thanks Adam. It does take some work. Grids in text format have been added. And thanks for the typo heads-up.
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby eleven » Thu Nov 20, 2008 5:54 am

I had posted this in the other thread, but then found this one. It was my fist try to use an almost SdC and i did not have to search long to find an application.

eleven wrote:... maybe i will try almost SdC's now ...

To give an example, how this could be done. A puzzle by JPF from the current Pattern Game:
Code: Select all
 1 . . | . . . | . . 2
 . 3 . | . 4 . | . 5 .
 . . 4 | 6 . 2 | 3 . .
-------+-------+-------
 . . 7 | 8 . 5 | 9 . .
 . . . | . . . | . . .
 . . 1 | 4 . 7 | 6 . .
-------+-------+-------
 . . 8 | 3 . 4 | 5 . .
 . 5 . | . 8 . | . 9 .
 6 . . | . . . | . . 7
+-------------------------+-------------------------+-------------------------+
| 1       6789    569     | 579     3579    389     | 478     4678    2       |
| 2789    3       269     | 179     4       189     | 178     5       1689    |
| 5789    789     4       | 6       1579    2       | 3       178     189     |
+-------------------------+-------------------------+-------------------------+
| 234     246     7       | 8       1236    5       | 9       1234    134     |
| 234589  24689   23569   | 129     12369   1369    | 12478   123478  13458   |
| 23589   289     1       | 4       239     7       | 6       238     358     |
+-------------------------+-------------------------+-------------------------+
| 79+2    179+2   8       | 3       12679   4       | 5       126     16      |
| 47+23   5      *23      | 127     8       16      | 124     9       1346    |
| 6      #1249   #239     | 25+19   25+19  @19      | 1+248   1+2348  7       |
+-------------------------+-------------------------+-------------------------+

Without the 4 in r9c2 there would be a SdC (23)(1239)(19):

r9c2<>4 -> SdC (r7c12|r8c2<>23 & r9c45=25) -> r8c3=2
r9c2=4 -> r7c2=1 -> r7c9=6 -> r7c8=2
so we can eliminate 2 from r7c12 and r8c7
eleven
 
Posts: 1581
Joined: 10 February 2008

Postby DonM » Thu Nov 20, 2008 7:20 am

eleven wrote:I had posted this in the other thread, but then found this one. It was my first try to use an almost SdC and i did not have to search long to find an application.


Very nice eleven. I'm finding the almost SdC far more frequently than I expected. I'm hoping to eventually find some examples where the elimination can't be found any other reasonable way, but if it ends up only that I can use it to quickly to find one or more eliminations as my example above, then I'll be quite comfortable using the aSDC (if I find it first) instead of going an extra step to find & use the underlying ALSs.
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby 999_Springs » Fri Dec 19, 2008 8:30 am

Would you consider this as a sort of almost Sue de Coq?
Code: Select all
#12 from the top95

  3478 |     6 |   3478 ||      5 |   238 |     1 ||    478 |     9 |    24
     1 |     2 |     78 ||     46 |     9 |    46 ||     78 |     5 |     3
     9 |    35 |   3458 ||     23 |   238 |     7 ||   1468 | 12468 |  1246
========================||========================||========================
  2356 |     4 |   2359 ||      8 |  1236 |  2369 ||     16 |     7 |   126
  2367 |    39 |   2379 || 123469 | 12346 | 23469 ||      5 |  1246 |     8
    26 |     8 |      1 ||      7 |   246 |     5 ||    469 |     3 |  2469
========================||========================||========================
   348 |   139 |   3489 ||  13469 |     5 |  3469 ||      2 |  1468 |     7
 23458 |  1359 | 234589 || 123469 |     7 | 23469 || 134689 |  1468 | 14569
  2345 |     7 |      6 ||  12349 |  1234 |     8 ||   1349 |    14 |  1459

core: r123c7; plus r4c7 and r1c9
almost sue de coq: if r1c9<>2 then you have a degenerate sue de coq => r6c7<>6; if r1c9=2 then naked pair r4c79 => r6c7<>6
Hidden Text: Show
Once upon a time I was a teenager who was active on here 2007-2011
999_Springs
 
Posts: 367
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Postby aran » Fri Dec 19, 2008 9:26 am

999_Springs wrote:Would you consider this as a sort of almost Sue de Coq?
Code: Select all
#12 from the top95

  3478 |     6 |   3478 ||      5 |   238 |     1 ||    478 |     9 |    24
     1 |     2 |     78 ||     46 |     9 |    46 ||     78 |     5 |     3
     9 |    35 |   3458 ||     23 |   238 |     7 ||   1468 | 12468 |  1246
========================||========================||========================
  2356 |     4 |   2359 ||      8 |  1236 |  2369 ||     16 |     7 |   126
  2367 |    39 |   2379 || 123469 | 12346 | 23469 ||      5 |  1246 |     8
    26 |     8 |      1 ||      7 |   246 |     5 ||    469 |     3 |  2469
========================||========================||========================
   348 |   139 |   3489 ||  13469 |     5 |  3469 ||      2 |  1468 |     7
 23458 |  1359 | 234589 || 123469 |     7 | 23469 || 134689 |  1468 | 14569
  2345 |     7 |      6 ||  12349 |  1234 |     8 ||   1349 |    14 |  1459

core: r123c7; plus r4c7 and r1c9
almost sue de coq: if r1c9<>2 then you have a degenerate sue de coq => r6c7<>6; if r1c9=2 then naked pair r4c79 => r6c7<>6


I'll give you my view : yes.
An SdC in general form is N candidates for N cells spread over two units (aka two disjoint subsets).
An almost SdC will have N+1 candidates for N cells over two units.
Applying that here, we have :
6 candidates [124678} for the 5 cells r1234c7+r1c9 over the two units c7 and b3.
The SdC at work is this :
z can be eliminated if it reduces the number of candidates below the number of cells (aka subset counting or multiplicity reduction).
ie N-1 candidates (or less) for the N cells (a contradiction).
The almost SdC principle is exactly the same : however to work it must reduce the N+1 candidates to N-1 candidates (or less) ie remove at least two contenders.
In your example :
6r6c7 removes 6 immediately so N+1 is down to N, and then through 6r6c7=>1r4c7=>2r4c9 also removes 2r1c9, so N is now reduced to N-1.
Hence <6>r6c7
aran
 
Posts: 334
Joined: 02 March 2007

Postby ronk » Fri Dec 19, 2008 12:02 pm

999_Springs wrote:Would you consider this as a sort of almost Sue de Coq?
[...]
core: r123c7; plus r4c7 and r1c9
almost sue de coq: if r1c9<>2 then you have a degenerate sue de coq => r6c7<>6; if r1c9=2 then naked pair r4c79 => r6c7<>6

No, because that would make it an almost degenerate Sue De Coq.:)

Seriously, without a candidate 7 or 8 in r1c9, calling that an almost Sue De Coq is a stretch.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby aran » Fri Dec 19, 2008 9:46 pm

ronk wrote:
999_Springs wrote:Would you consider this as a sort of almost Sue de Coq?
[...]
core: r123c7; plus r4c7 and r1c9
almost sue de coq: if r1c9<>2 then you have a degenerate sue de coq => r6c7<>6; if r1c9=2 then naked pair r4c79 => r6c7<>6

No, because that would make it an almost degenerate Sue De Coq.:)

Seriously, without a candidate 7 or 8 in r1c9, calling that an almost Sue De Coq is a stretch.


The perfect SdC would have 2 from {478} in r1c9.
Let's say 47.
To "almost that" : it can't be reduced => placement=>no SdC to begin with
So :
- either there is an extra candidate as Ronk is suggesting {472}
- or a candidate is replaced as in the example {42}.
As to which is more "almost" than the other...
aran
 
Posts: 334
Joined: 02 March 2007


Return to Advanced solving techniques