The New Sudoku Players' Forum

[Wepwawet]

Hi again.

I have a couple of questions, about the Sue De Coq algorithm. Is there a final definition of the algorithm that defines every type of Sue de Coq, I find bits here and there, but, none explain all of the examples I come across, particularly, those supplied on Hodoku. Speaking of which, can anyone explain what the significance is, of the appearance of a lime-green candidate, in occasional examples found in the Sue de Coq's on Hodoku. The bit that is not well documented/explained is when the numbers of candidates is more than n+2. Hodoku has thrown at me, an ALS variant consisting of only a single cell, that has more than 2 candidates, does that mean a single cell ALS can have more than 3 candidates?

Thanks in advance
Wept

[eleven]

Some see Sue de Coq's as special double linked ALS's (restricted to a box and a line), but if you are not familiar with that, the "two-sector disjoint subsets" point of view might be easier to understand:
The pattern consists of n cells in the line and the box, containing n different digits, where k are restricted to the line and n-k to the box. So all digits have to be in the pattern, and those restricted to the box cannot be elsewhere in the box, and those restricted to the line cannot be elsewhere in the line.

[Leren]

Perhaps you can find something in the, arguably famous, discovery thread of this topic, here. Leren

[Wepwawet]

The reason for wanting a concrete definition of the SDC, is that I am updating an old bit of coding of mine, now, I do not profess to be a good coder, but, nevertheless, it is an interest of mine. To that end, I need to be sure I understand things correctly, in case I am missing something from the algorithms. I do not intend to discuss the programming side of things, as that is off-topic here, but, I do need to be sure on the algorithm's criteria first.

Yes, Leren, I was aware of those early posts, on the SDC, thanks. It appears that some of the data has been lost over time, and it is possible that, unaware to me, that the goalposts on SDC's have been moved over time, and that I am unaware of that. FYI, I am familiar with what I call the traditional SDC, inasmuch, as it being, a set of intersection cells, having 2 supplementary bi-value cells (the smallest ALS), one of them sharing the same 3x3 block, the t'other, being aligned within a house (row/column), with a criteria that their candidates were subsets of the intersection cells, and that the 2 peripheral ALS candidates were not identical. All echoing from the original posts of yesteryear. So you see, I am not totally green on SDC's.

This is how I see it, at some point, the model of the SDC has evolved, the Sudoku community, found that the SDC was not to be limited to the smallest ALS's (bivalue cells), and that, other variants were feasible, e.g. multi-cell ALS's and almost ALS's, etc. Additionally, it was found that candidates in those supplementary ALS's were not restricted to being subsets of the intersection cells, just that 2 common candidates from the intersection cells, were needed by each ALS. It is these deviations from the traditional model that I need clarification on, as I have looked around the net, but I am not convinced that I have found a 'one hat fits all' SDC definition, unfortunately, that is compounded by, that I am not even sure that one is needed, as Eleven pointed out to me, that there is common ground with double-linked ALS's.

So, Eleven, can I definitely say then, that there will always exist 2 candidates from each individual ALS, that are common to the intersection cells, but, never appear in each other's ALS. Am I correct on this? (for SDC's only)

As you have mentioned that SDC's fall under the ALS banner, then, I gather that Almost Locked Set theory should cover SDC's anyway.

If this has all been covered before, then I apologize for regurgitating it.

Regards

[Wepwawet]

The pattern consists of n cells in the line and the box, containing n different digits, where k are restricted to the line and n-k to the box. So all digits have to be in the pattern, and those restricted to the box cannot be elsewhere in the box, and those restricted to the line cannot be elsewhere in the line.

Up to the point I came across this example of an Extended SDC, Type 1 on the net, I thought I had managed to get my head around SDC's. Hodoku confirms it is an SDC: Sue de Coq: r6c78 - {3569} (r6c126 - {4679}, r4c89 - {357}) => r5c7<>3, r6c4<>4, r6c4<>9

.---------------.----------------.--------------.
| 8 6 4 | 39 379 2 | 1 79 5 |
| 1 9 7 | 6 8 5 | 2 3 4 |
| 5 3 2 | 1 479 479 | 8 679 67 |
:---------------+----------------+--------------:
| 2 1 39 | 359 6 8 | 4 57 37 |
| 46 5 39 | 7 349 1 | 369 8 2 |
| 467 47 8 | 3459 2 49 | 369 56 1 |
:---------------+----------------+--------------:
| 47 2478 5 | 249 479 6 | 37 1 38 |
| 9 78 1 | 24 5 3 | 67 24 68 |
| 3 247 6 | 8 1 47 | 5 24 9 |
'---------------'----------------'--------------'

.... yet the SDC construct above, ruffles my feathers, and it seems to fly in the face of what you cited, namely, that the pattern of n cells has n digits in. This example has 7 cells with 6 digits in ...

Cells: r6c12678 and r4c89
Candidate set: {3,4,5,6,7,9}.

Am I missing something here?

... and what does k represent?

Regards

[yzfwsf]

Sue de Coq(Cannibalized) example:

Code: Select all

.------------------.----------------------.-------------------.
| 458   1      9   | 258    458     6     | 3     2478   247  |
| 458   7      2   | 589    34589   34589 | 168   14689  469  |
| 348   348    6   | 289    1       7     | 28    2489   5    |
:------------------+----------------------+-------------------:
| 1     245    457 | 3      5678    258   | 9     2467   2467 |
| 2347  23459  457 | 15679  5679    1259  | 2567  23467  8    |
| 6     2359   8   | 4      579     259   | 257   237    1    |
:------------------+----------------------+-------------------:
| 2478  6      457 | 5789   345789  34589 | 1278  12789  2379 |
| 478   458    1   | 56789  2       34589 | 678   6789   3679 |
| 9     28     3   | 1678   678     18    | 4     5      267  |
'------------------'----------------------'-------------------'

Sue de Coq(Cannibalized): r78c4 - {56789} (r9c456 - {1678}, r123c4 -{2589}) => r5c4<>5 r7c5<>7 r1c5<>8 r2c5<>8 r2c6<>8 r7c4<>8 r7c5<>8 r7c6<>8 r8c4<>8 r8c6<>8 r9c2<>8 r9c4<>8 r5c4<>9

[Leren]

Code: Select all

*--------------------------------------------------------------------------------*
| 8       6       4        | 39      379     2        | 1       79      5        |
| 1       9       7        | 6       8       5        | 2       3       4        |
| 5       3       2        | 1       479     479      | 8       679     67       |
|--------------------------+--------------------------+--------------------------|
| 2       1       39       | 359     6       8        | 4      B57     B37       |
| 46      5       39       | 7       349     1        | 69-3    8       2        |
|C467    C47      8        | 35-49   2      C49       |A369    A56      1        |
|--------------------------+--------------------------+--------------------------|
| 479     2478    5        | 249     479     6        | 37      1       38       |
| 479     2478    1        | 249     5       3        | 67      24      68       |
| 3       247     6        | 8       1       47       | 5       24      9        |
*--------------------------------------------------------------------------------*

This appears to be an "Extended" SDC Type 2 with non Intersection Set additional candidate 7 in the row and block cells. Hodoku says (inter alia) :

Code: Select all

Sue de Coq can be enhanced in two possible ways:

1. The intersection cells can contain additional candidates. For every additional candidate an additional cell in the row/column or in the block must be found.

2. The row cells (column cells) and the block cells can contain candidates not drawn from the intersection set. For any such additional candidate one additional cell is necessary.

Leren

[StrmCkr]

depends on what you are looking at it to define:

mine works off this one currently...

there is/was a relaxed definition of

a)N cells with N+2 digits {Aals)
that sees
B) N cells N+1 digits {Als}
c) N cells N+1 digits {Als}

where
1 Digits is locked into a sector that is either in A or B
&
1 Digits is locked into a sector that is either in A or C
and
the Restricted common of AB is not the same as AC

then Digit x of abc is restricted to cells of abc, any x that see all copies of abc x is there by eliminated.

http://forum.enjoysudoku.com/almost-locked-rules-for-now-t2510-15.html

Code: Select all

2 ALS 2 restricted common rule
------------------------------
If A have degrees of freedom of 2
and B and C are ALS
with
x restricted common to A and B
y restricted common to A and C
and z common to A B C
then you cant have z in a cell that can see all the z candidates in A B C

doubly linked rule : {see 2nd example}
with
 w,x  restricted common to A & B
 y,z   restricted common to A & C
all Restricted commons cannot be in A  as it can only occupy 2 of the 4 thus B,C must contain  at least 1 of each of the RC's
digits w x of  A & B are restricted to A & B
digits y z of A & C are restricted to A & C
Digis not equal to wxyz  of ABC are restricted to  ABC 


Code: Select all

 
        +-----------------+---------+--------------+
        | .     .      .  | .  .  . | .     .   .  |
        | .     (123)  .  | .  .  . | (14)  -2  -2 |
        | (34)  -2     -2 | .  .  . | (24)  .   .  |
        +-----------------+---------+--------------+
        | .     .      .  | .  .  . | .     .   .  |
        | .     .      .  | .  .  . | .     .   .  |
        | .     .      .  | .  .  . | .     .   .  |
        +-----------------+---------+--------------+
        | .     .      .  | .  .  . | .     .   .  |
        | .     .      .  | .  .  . | .     .   .  |
        | .     .      .  | .  .  . | .     .   .  |
        +-----------------+---------+--------------+

AaLS - 2RC

Set a) [123] @ R2C2
Set b) [234] @ R3C17
Set C) [124] @ R23C7
X:3,Y:1
Z:2 => R2C89, R3C23 <> 2

another more complicated example:

Code: Select all

+----------------------+------------------------+----------------------+
| 12789  3      1489-7 | 5         (278)  (78)  | 6       147    1248  |
| 1278   128    6      | (2378)    4      9     | 1237    5      1238  |
| 5      28     478    | (2367-8)  1      36-78 | 2347    347    9     |
+----------------------+------------------------+----------------------+
| 169    7      159    | 29-36     2356   356   | 123459  8      12345 |
| 1689   1589   2      | 4         35678  35678 | 13579   1379   135   |
| 3      4      589    | 2789      2578   1     | 2579    79     6     |
+----------------------+------------------------+----------------------+
| 4      (159)  (1579) | (367)     356-7  2     | 8       136-9  135   |
| 278-9  28-59  3      | 1         5678   45678 | 459     469    45    |
| (18)   6      (158)  | (38)      9      345-8 | 1345    2      7     |
+----------------------+------------------------+----------------------+

Code: Select all

Aals -2rc
a) 3 6 7 8 @ 57 75
b) 2 3 6 7 8 @ 4 5 12 21
c) 1 5 7 8 9 @ 55 56 72 74
rc: 3 6 7 8
z: 1 2 3 5 6 7 8 9

potential eliminations:
 54 63 64 65 73 <> 1,5
3 13 14 22 23 <> 2
3 30 39 48 66 <> 3,6
54 58 59 60 61 62 <> 7
73 76 77 78 79 80 <> 8
54 58 59 60 61 62 63 64 65 73 <> 9

but this has limitations:

similar to an old argument that sue de coqs are actually just als-xz double linked rule

this was recently reproved false {again and reaffirmed by me..}
my original sue de coq code was an als-xz dobule linked rule

my als-xz code wouldn't find the ALs 2RC versions that showed up as cogs.

why?
there is sectors where the initial als cannot successfully scale down a size{cell count} for N cells with N+1 digits

this is where the AAls takes over and forms valid patterns.
however, some N+2 sizes cant scale down repeat till we have 1 cell with 9 digits.

which i have seen function in 2 sectors a*als where * can expand to (+1 -> max size digit counts)

two sectors being the main defining feature of a sue du coq.
instead of the "almost" count of an als...

then all you have to do is go back to the first rules i outline for the Aals 2RC
make sure both have at least n RC to the sets AB, & AC and sometimes CB} so that 1 digit is always "locked" to 1 of 3 als.

[eleven]

Hi Wept,
what i gave you, was a definition of the "classical" sudoku.
n is the number of cells (in line and box) and is equal to the number of candidates. There are 2 or 3 common cells. So n must be at least 4 (2 common cells, 1 extra in line and box), and (trivially) at most 9.
If k is the number of digits restricted to the line, then the others (n-k) must be restricted to the box here (0<k<n). [edited]
You can eliminate the line restricted numbers from the rest of the line, and the box restricted ones from the rest of the box, because all numbers have to be in the n cells.
This corresponds to, what Leren cited as first enhancement of hodoku.

The second extension is, that you can have n-1 digits in n cells. This means, that one digit must be twice in the set of cells. So this digit, let's call it x, must occur outside of the common cells both in the line and in the box - and must be here and there in the solution.
As yzfwsf showed in his nice example, in this case you can have additional eliminations from all cells, which see all occurances of x in the line only cells, and all, which see all occurances of x in the box only cells..

Theoretically you could also have n-2 or n-3 candidates in the n cells, e.g.
12356 12356 12356 12356 (123456 123456) 3456 3456 3456. I don't know, if there are real world examples.

PS: Note, that the m digits in n cells property, where m<=n and the cells are connected, can be generally used, e.g. to find all eliminations of wzyz-wings (where n,m=4).

[marek stefanik]

n is the number of cells [...] and (trivially) at most 9.

Note that this assumes that you also check for inverted SDCs. If you do not (as most solvers), than you can find SDCs with more than 9 cells, such as this one:

Code: Select all

....6....7..1..3...89....4.3..7..8...2..1..5...48....25.......9.....4.2..6.9....1
.-----------------.-------------------.---------------------.
|#124 #1345 #1235 |#245  6      789-25|#1279–5#1789  #78–5  |
| 7    45    256  | 1    24589  2589  | 3     #689   #568   |
| 126  8     9    | 235  2357   2357  | 12–567 4     #567   |
:-----------------+-------------------+---------------------:
| 3    159   156  | 7    2459   2569  | 8      169    46    |
| 689  2     678  | 34   1      369   | 679    5      3467  |
| 169  1579  4    | 8    359    3569  | 1679   13679  2     |
:-----------------+-------------------+---------------------:
| 5    347   2378 | 236  2378   1     | 467    3678   9     |
| 189  1379  1378 | 356  3578   4     | 567    2      35678 |
| 248  6     2378 | 9    23578  23578 | 457    378    1     |
'-----------------'-------------------'---------------------'

r1c1234789, b3p569 \ 12345r1, 56789b3
The inverse: 789r1, 12b3 \ r1c6789, b3p7

I think that the easiest way to understand SDCs is via MSLSs (Multi-Sector Locked Sets; or more specifically MSNSs (N stands for naked)).
The idea of MSNS is to cover a set of cells using a set of digit-house combinations of the same size (if a digit appears as a candidate outside the intersection both in the line and the box, such as 8 in yzfwsf's example and 5 in mine, it can appear twice in the set, so it must be double-counted).
This gets rid of the inconsistency of sometimes having more cells than digits (with more cells than digit-house combinations, there is no solution).
In this POV, regular eliminations are candidates outside the set of cells, that are covered by the digit-house combinations used, while cannibalistic eliminations are candidates inside the set of cells, covered twice (in general, eliminations are candidates that are covered more times than they appear in the cells).

Marek

[StrmCkr]

yzfwsf example is also a als-xz doubly linked following the rules described by Eleven above.

Code: Select all

+------------------+---------------------------+-------------------+
| 458   1      9   | (258)     45-8     6      | 3     2478   247  |
| 458   7      2   | (589)     3459-8   3459-8 | 168   14689  469  |
| 348   348    6   | (289)     1        7      | 28    2489   5    |
+------------------+---------------------------+-------------------+
| 1     245    457 | 3         5678     258    | 9     2467   2467 |
| 2347  23459  457 | 167-59    5679     1259   | 2567  23467  8    |
| 6     2359   8   | 4         579      259    | 257   237    1    |
+------------------+---------------------------+-------------------+
| 2478  6      457 | (579-8)   3459-78  3459-8 | 1278  12789  2379 |
| 478   458    1   | (5679-8)  2        3459-8 | 678   6789   3679 |
| 9     2-8    3   | (167-8)   (678)    (18)   | 4     5      267  |
+------------------+---------------------------+-------------------+

hodoku never had full doubly linked eliminations implemented: as his code finds only

Code: Select all

Almost Locked Set XZ-Rule: A=r123c4 {2589}, B=r789c4,r9c56 {156789}, X=5,9 => r5c4<>9, r5c4<>5, r127c5,r278c6<>8, r7c5<>7

ie
the 8 in set A was locked to A -> eliminate peers cells visible to all 8's in A
and 8 in set B was locked to B -> eliminate peers cells visible to all 8's in B

which gives 3 missing eliminations @ R789C4
and clean up takes the R9C2
or we could consider the effect of A on B or vice versa and apply it with in the eliminations {making it complicated )

or simply skip these eliminations and let BLR clean up as this is the option hodoku follows.

for example this alternative view of the same cells/sets could do...

Code: Select all

Almost Locked Set XZ-Rule: A=r9c456 {1678}, B=r12378c4 {256789}, X=6,7 => r7c5<>7, r7c56,r8c6,r9c2<>8, r5c4<>5, r5c4<>9

set a removes 8 @ R78C4 {B cells}
set b remove 8 @ nothing
apply a to b
set b removes 8@ R9C4, R12C56
apply B to A
no change.

mayhaps i made it more maddening

[Wepwawet]

I will look at all these posts in detail this following weekend. I may have some more questions then.

or simply skip these eliminations and let BLR clean up as this is the option hodoku follows.

What is BLR?

[StrmCkr]

Box/Line reduction aka 1-fish (cyclope)