## T&E(2) patterns and puzzles

Everything about Sudoku that doesn't fit in one of the other sections

### T&E(2) patterns and puzzles

.
T&E(2) patterns and puzzles

Following the discovery of puzzles in T&E(3), mith has opened a thread for T&E(3) puzzles (http://forum.enjoysudoku.com/t-e-3-puzzles-split-from-hardest-sudokus-thread-t40514.html) - and I guess he will accept the study of related associated T&E(3) patterns in it.
(Part of the old "hardest" thread should be moved to it, but there's currently no admin to do it.)

I think we need something similar for T&E(2) puzzles and T&E(2) patterns.
Until the discovery of Loki, the search for the "hardest" puzzles had concentrated mainly on the search for the highest SERs (and, very occasionally, other ratings).
Setting up another criterion (being in T&E(3) has led to a great leap forward in the number of "hard" puzzles found.

However, it has also shown that we have a very restricted structural knowledge of the T&E(2) land (contrary to T&E(1), where a full sub-classification is available, the B rating.) Sure, there's the BpB sub-classification of T&E(2), but what I mean in this thread is about non-chain-like T&E(2) patterns - regardless to their SER.
What are the non-chain-like patterns that require T&E(2) to be proven contradictory?
A good starting point would be eleven's list http://forum.enjoysudoku.com/chromatic-patterns-t39885-41.html - minus the only pattern in T&E(3): http://forum.enjoysudoku.com/chromatic-patterns-t39885-50.html
Can one generate "hard" puzzles based on these patterns?
Can one systematise eleven's approach to find a complete list of 2-digit, 3-digit... mixed-digit patterns?
(By mixed-digits, I mean some cells have e.g. 3-digits and other cells may have 4, as totuan's E1 pattern in this example: http://forum.enjoysudoku.com/44951-in-63137-t-e-3-min-expands-t40581.html)

I'm aware that this is a very difficult topic and I doubt we can ever have a full list.
The particular case of T&E(2) patterns that could be defined as impossible patterns shows that some of them will appear as degenerate forms of T&E(3) contradictory patterns - and much harder to spot than the T&E(3) pattern itself.
.
denis_berthier
2010 Supporter

Posts: 3536
Joined: 19 June 2007
Location: Paris

### Re: T&E(2) patterns and puzzles

.
Someone told by PM that I should recall the definition of T&E(n).
The classical pseudo-definition of T&E was "suppose candidate Z is true; if this leads to a contradiction, delete Z".
This is totally meaningless if you don't say HOW it may lead to a contradiction: in particular, any candidate that is not in the solution does lead to a contradiction in First Order Logic [FOL] - not a very useful definition.

I'll recall my formal definition, first introduced here http://forum.enjoysudoku.com/fully-supersymmetric-chains-t5591-151.html and here http://forum.enjoysudoku.com/abominable-trial-and-error-and-lovely-braids-t6390.html. These were the first formalisations of what was intended in the previously vague definition.
I'll take the form present in [PBCS], including all the details necessary for writing a non-ambiguous program.

©PBCS, section 5.6 wrote:Definition: given a resolution theory T with the confluence property, a resolution state RS and a candidate Z in RS, T&E(T, Z, RS) or Trial-and-Error based on T for Z in RS, is the following procedure (notice: a procedure, not a resolution rule):
- make a copy RS’ of RS; in RS’, delete Z as a candidate and assert it as a value;
- in RS’, apply repeatedly all the rules in T until quiescence;
- if RS’ has become a contradictory state, then delete Z from RS (sic: RS, not RS’); else do nothing (in particular if a solution is obtained in RS’, merely forget it);
- (discard RS’ and) return the (possibly) modified RS state.

Notice that this definition is meaningful only if T has the confluence property: otherwise, the result of “applying repeatedly in RS’ all the rules in T until quiescence” may not be uniquely defined.

Definition: given a resolution theory T with the confluence property and a resolution state RS, we define the T&E(T, RS) procedure as follows:
a) in RS, apply the rules in T until quiescence; if the resulting RS is a solution or a contradictory state, then return it and stop;
b) mark all the candidates remaining in RS as “not-tried”;
c) choose some “not-tried” candidate Z, un-mark it and apply T&E(T, Z, RS);
d) if Z has been eliminated from RS by step c, then goto a else if there remains at least one “not-tried” candidate in RS then goto c else return RS and stop.

Definition: given a resolution theory T with the confluence property and an instance P with initial resolution state RSP , we define T&E(T, P) as T&E(T, RSP ).

Notice that this procedure always stays at depth 1 (i.e. only one candidate is tested at a time) but that a candidate Z may be tried several times for T&E(T, Z, RSi ) in different resolution states RSi. This is normal, because the result may be different if other candidates have been eliminated in the meanwhile. This also guarantees that the result of this procedure does not depend on the order in which remaining candidates are “tried”.

We say that P can be solved by T&E(T), or that P is in T&E(T), if T&E(T, P) produces a solution for P.
When T is the Basic Resolution Theory (BRT) of a CSP (which is known to always have the confluence property), we simply write T&E instead of T&E(BRT(CSP))).

©PBCS, section 11.3.2 wrote:Definition: given a resolution theory T with the confluence property, a resolution state RS and an integer n, the two procedures Trial-and-Error based on T at depth n for Z in RS and Trial-and-Error based on T at depth n in RS [respectively T&E(T, Z, RS, n) and T&E(T, RS, n)] are defined by mutual recursion as follows:

T&E(T, Z, RS, 1) = T&E(T, Z, RS) and T&E(T, RS, 1) = T&E(T, RS), where the right-hand sides have been defined in section 5.6.1.

For n>1, T&E(T, Z, RS, n) is defined as follows:
- make a copy RS1 of RS; in RS1 , delete Z as a candidate and assert it as a value;
- apply T&E(T, RS1, n-1);
- if RS1 has become a contradictory state (detected by CD), then delete Z from RS (sic: RS, not RS1 ); otherwise, do nothing (in particular if a solution is obtained in RS1, merely forget it);
- return the (possibly) modified RS state.

For n>1, T&E(T, RS, n) is defined as follows:
a) in RS, apply the rules in T until quiescence; if the resulting RS is a solution or a contradictory state, then return it and stop;
b) mark all the candidates remaining in RS as “not-tried”;
c) choose some “not-tried” candidate Z, un-mark it and apply T&E(T, Z, RS, n);
d) if Z has been eliminated from RS by this procedure,
then goto a
else if there remains at least one “not-tried” candidate in RS then goto c else return RS and stop.

Notice that every time a candidate is eliminated by step d of T&E(T, RS, n), all the other candidates (remaining after step a) are re-marked as “not-tried” by step b. Thus, the same candidate can be tried several times in different resolution states. Even with T having the confluence property, this is necessary to guarantee that the result does not depend on the order used to try the candidates (in step c).

Definition: given a resolution theory T with the confluence property and an instance P with initial resolution state RSP , we define T&E(T, P, n) as T&E(T, RSP , n).

Definition: for an instance P, the T&E-depth of P, d(P), is the smallest n≥0 such that P can be solved by T&E(n), with the convention that T&E(0) = BRT(CSP).

: T&E(T, n) is coded in CSP-Rules for n≤3. T can be selected in the config file
denis_berthier
2010 Supporter

Posts: 3536
Joined: 19 June 2007
Location: Paris

### Re: T&E(2) patterns and puzzles

IMO, I’m not sure but just checked some on “min_expand_20221106_basics_special_only_full” then many puzzles need other impossible pattern beside TH (trivalue oddagon) to downgrade…
Hidden Text: Show
Code: Select all
`.23....894.6......78............5.9....92..51...3.12.83..5...1....89..23....13..5;37;269;13;3;n467;b5p168+b6p348+b8p267+b9p348    line 228 *--------------------------------------------------------------------* | 15     2      3      | 1467   4567   467    | 14567  8      9      | | 4      159    6      | 127    3578   2789   | 157    37     27     | | 7      8      159    | 1246   3456   2469   | 1456   346    246    | |----------------------+----------------------+----------------------| | 1268   13467  12478  |*467    4678   5      |#3467   9     #467    | | 68   A#3467   478    | 9      2     *4678   | 467-3  5      1      | A => r4c7=3 | 569    45679  4579   | 3     *467    1      | 2     #467    8      | |----------------------+----------------------+----------------------| | 3     #4679   24789  | 5     *467    2467   | 89     1     *467    | | 156    14567  1457   | 8      9     *467    |*467    2      3      | | 2689  #4679   24789  |*2467   1      3      | 89    *467    5      | *--------------------------------------------------------------------*1...567.9.....9.36...37..5........71..6...9.5.7....36.......5..58..93....42.15...;52;604;13;4;n248;b2p159+b3p249+b5p348+b6p159   line 285 *--------------------------------------------------------------------* | 1      23     348    |*248    5      6      | 7     *248    9      | |#248A   5      7      | 1     *248    9      |*248    3      6      | | 24689  269    489    | 3      7     *248    | 1      5     *248    | |----------------------+----------------------+----------------------| | 23489  239    34589  | 59     6     #248    |*248    7      1      | |#248    1      6      | 7      3     #248    | 9     *248    5      | A=2 => no 2’s on R5 |#2489   7      4589   | 59    #248    1      | 3      6     *248    | => r6c1=9 |----------------------+----------------------+----------------------| | 369    369    39     | 248    248    7      | 5      1      248    | | 5      8      1      | 246    9      3      | 246    24     7      | | 7      4      2      | 68     1      5      | 68     9      3      | *--------------------------------------------------------------------*1.3.....9.5.....3696..7.15......13.53..5..69........716...94...79.2.8.........9..;54;601;13;4;n248;b1p249+b3p249+b4p168+b6p267    line 333 *--------------------------------------------------------------------* | 1     *248    3      | 468    24568  256    | 7     *248    9      | |*248    5      7      | 1489   1248   29     |*248    3      6      | | 9      6     *248    | 348    7      23     | 1      5     *248    | |----------------------+----------------------+----------------------| |#248    7      69     | 4689   2468   1      | 3     *248    5      | | 3     #248    1      | 5      248    7      | 6      9     *248    | | 5     #248    69     | 34689  23468  2369   |*248    7      1      | |----------------------+----------------------+----------------------| | 6      13     258    | 137    9      4      | 258    128    278    | | 7      9      45     | 2      16     8      | 45     16     3      | |#248A   13    #248    | 1367   1356   356    | 9      12468 #2478   | => r9c9=7 *--------------------------------------------------------------------* *--------------------------------------------------------------------* | 1      248    3      | 468    24568  256    | 7      248    9      | | 248    5      7      | 1    A#248    9      | 248    3      6      | A=2 = no 2’s on R4 | 9      6      248    | 348    7      23     | 1      5      248    | |----------------------+----------------------+----------------------| => r4c5=6 |#248    7      69     | 4689  #2468   1      | 3      248    5      | | 3     #248    1      | 5     #248    7      | 6      9      248    | | 5     #248    69     | 34689  23468  236    | 248    7      1      | |----------------------+----------------------+----------------------| | 6      3      258    | 7      9      4      | 258    1      28     | | 7      9      45     | 2      1      8      | 45     6      3      | | 248    1      248    | 36     356    356    | 9      248    7      | *--------------------------------------------------------------------*...4.6.89....891.2.8..1.64.2.4...8.18.1.4296........243.76.....5...9......8...2..;55;500;12;2;n357;b2p249+b3p159+b5p348+b6p267   line 373 *--------------------------------------------------------------------* | 1     #2357   35-2   | 4     *357    6      |*357    8      9      | | 46     3457   356    |*357    8      9      | 1     *357    2      | | 79     8      359    | 2      1     *357    | 6      4     *357    | |----------------------+----------------------+----------------------| | 2      6      4      | 9     #357   #357    | 8     *357    1      | | 8    A#357    1      |#357    4      2      | 9      6     *357    | A => r1c2=2 | 79    #357    359    | 18     6      18     |*357    2      4      | |----------------------+----------------------+----------------------| | 3      149    7      | 6      2      1458   | 45     159    58     | | 5      124    26     | 1378   9      13478  | 347    137    3678   | | 46     149    8      | 1357   357    13457  | 2      13579  3567   | *--------------------------------------------------------------------* *--------------------------------------------------------------------* | 1      2      35     | 4     *357    6      |*357    8      9      | | 4      357    6      |*357    8      9      | 1     *357    2      | | 79     8      359    | 2      1     *357    | 6      4     *357    | |----------------------+----------------------+----------------------| | 2      6      4      | 9     #357   #357    | 8     *357    1      | | 8      357    1      |#357    4      2      | 9      6     *357    | | 79     357    359    | 18     6      18     |*357    2      4      | |----------------------+----------------------+----------------------| | 3      149    7      | 6      2      145    | 45     159    8      | | 5      14     2      | 1378   9      13478  | 347    137    6      | | 6      149    8      |#1357A #357    13457  | 2      13579 #357    | A => r9c4=1 *--------------------------------------------------------------------*12......9.56..9....89....46.7.39.6.553.....94....4537...79.4.......7..6...5.63...;64;969;12;2;n128;b5p357+b6p249+b8p267+b9p168   line 444 *--------------------------------------------------------------------* | 1      2      34     | 468    358    68     | 7      358    9      | | 47     5      6      | 47   A#1238   9      |#128   #1238   1238   | A => r7c8<>3 | 37     8      9      | 127    1235   127    | 125    4      6      | |----------------------+----------------------+----------------------| | 248    7      1248   | 3      9     *128    | 6     *128    5      | | 5      3      128    | 67    *128    67     |*128    9      4      | | 6      9      128    |*128    4      5      | 3      7     *128    | |----------------------+----------------------+----------------------| | 238    6      7      | 9     *128    4      | 1258   1258-3#1238   | | 289    14     238    | 5      7     *128    | 49     6     #1238   | | 289    14     5      |*128    6      3      | 49    #128    7      | *--------------------------------------------------------------------* *-----------------------------------------------------------* | 1     2     34    | 468   358   68    | 7     358   9     | | 47    5     6     | 47  A#1238  9     |#128   1238 #128   | A => r7c8=5 => TH r8c9=3 | 37    8     9     | 127   1235  127   | 125   4     6     | |-------------------+-------------------+-------------------| | 248   7     1248  | 3     9    *128   | 6    *128   5     | | 5     3     128   | 67   *128   67    |*128   9     4     | | 6     9     128   |*128   4     5     | 3     7    *128   | |-------------------+-------------------+-------------------| | 238   6     7     | 9    *128   4     | 1258 #1258  1238  | | 289   14    238   | 5     7    *128   | 49    6    #1238  | | 289   14    5     |*128   6     3     | 49   #128   7     | *-----------------------------------------------------------*`

It’s not hard to prove those impossible patterns (some cases that needs to use RT in puzzles).

totuan
totuan

Posts: 169
Joined: 25 May 2010
Location: vietnam

### Re: T&E(2) patterns and puzzles

totuan wrote:IMO, I’m not sure but just checked some on “min_expand_20221106_basics_special_only_full” then many puzzles need other impossible pattern beside TH (trivalue oddagon) to downgrade…
Code: Select all
`.23....894.6......78............5.9....92..51...3.12.83..5...1....89..23....13..5;37;269;13;3;n467;b5p168+b6p348+b8p267+b9p348    line 228 *--------------------------------------------------------------------* | 15     2      3      | 1467   4567   467    | 14567  8      9      | | 4      159    6      | 127    3578   2789   | 157    37     27     | | 7      8      159    | 1246   3456   2469   | 1456   346    246    | |----------------------+----------------------+----------------------| | 1268   13467  12478  |*467    4678   5      |#3467   9     #467    | | 68   A#3467   478    | 9      2     *4678   | 467-3  5      1      | A => r4c7=3 | 569    45679  4579   | 3     *467    1      | 2     #467    8      | |----------------------+----------------------+----------------------| | 3     #4679   24789  | 5     *467    2467   | 89     1     *467    | | 156    14567  1457   | 8      9     *467    |*467    2      3      | | 2689  #4679   24789  |*2467   1      3      | 89    *467    5      | *--------------------------------------------------------------------*`

I'm not sure to understand what you mean.
The first puzzle is in T&E(3), like all the puzzles in mith database.
Using only ordinary whips and tridagon-ORk-chains, one can reach the resolution state you mentioned:
Code: Select all
`hidden-pairs-in-a-column: c7{n8 n9}{r7 r9} ==> r9c7≠7, r9c7≠6, r9c7≠4, r7c7≠7, r7c7≠6, r7c7≠4   +-------------------+-------------------+-------------------+    ! 15    2     3     ! 1467  4567  467   ! 14567 8     9     !    ! 4     159   6     ! 127   3578  2789  ! 157   37    27    !    ! 7     8     159   ! 1246  3456  2469  ! 1456  346   246   !    +-------------------+-------------------+-------------------+    ! 1268  13467 12478 ! 467   4678  5     ! 3467  9     467   !    ! 68    3467  478   ! 9     2     4678  ! 3467  5     1     !    ! 569   45679 4579  ! 3     467   1     ! 2     467   8     !    +-------------------+-------------------+-------------------+    ! 3     4679  24789 ! 5     467   2467  ! 89    1     467   !    ! 156   14567 1457  ! 8     9     467   ! 467   2     3     !    ! 2689  4679  24789 ! 2467  1     3     ! 89    467   5     !    +-------------------+-------------------+-------------------+ OR3-anti-tridagon[12] for digits 4, 6 and 7 in blocks:         b5, with cells: r4c4, r5c6, r6c5        b6, with cells: r4c9, r5c7, r6c8        b8, with cells: r9c4, r8c6, r7c5        b9, with cells: r9c8, r8c7, r7c9with 3 guardians: n8r5c6 n3r5c7 n2r9c4 t-whip[4]: r7n2{c6 c3} - r7n8{c3 c7} - r7n9{c7 c2} - r2n9{c2 .} ==> r2c6≠2t-whip[5]: c1n9{r6 r9} - c1n2{r9 r4} - c1n8{r4 r5} - c6n8{r5 r2} - r2n9{c6 .} ==> r6c2≠9t-whip[5]: r2n9{c2 c6} - r2n8{c6 c5} - c5n3{r2 r3} - c5n5{r3 r1} - r1c1{n5 .} ==> r2c2≠1Trid-OR3-whip[5]: r5c1{n6 n8} - c6n8{r5 r2} - OR3{{n8r5c6 n3r5c7 | n2r9c4}} - b2n2{r2c4 r3c6} - c6n9{r3 .} ==> r5c7≠6Trid-OR3-ctr-whip[6]: c2n3{r4 r5} - r5n6{c2 c6} - c6n8{r5 r2} - c6n9{r2 r3} - c6n2{r3 r7} - OR3{{n2r9c4 n3r5c7 n8r5c6 | .}} ==> r4c2≠6Trid-OR3-ctr-whip[6]: c1n2{r4 r9} - c3n2{r9 r4} - r4n1{c3 c2} - c2n3{r4 r5} - r5n6{c2 c6} - OR3{{n2r9c4 n3r5c7 n8r5c6 | .}} ==> r4c1≠6whip[8]: r5c1{n6 n8} - c6n8{r5 r2} - c6n9{r2 r3} - c6n2{r3 r7} - r9n2{c4 c3} - c3n8{r9 r7} - c3n9{r7 r6} - c1n9{r6 .} ==> r9c1≠6Trid-OR3-whip[8]: r4n2{c3 c1} - r4n8{c1 c5} - c6n8{r5 r2} - c6n9{r2 r3} - c6n2{r3 r7} - OR3{{n2r9c4 n8r5c6 | n3r5c7}} - c2n3{r5 r4} - r4n1{c2 .} ==> r4c3≠4Trid-OR3-whip[8]: r4n2{c3 c1} - r4n8{c1 c5} - c6n8{r5 r2} - c6n9{r2 r3} - c6n2{r3 r7} - OR3{{n2r9c4 n8r5c6 | n3r5c7}} - c2n3{r5 r4} - r4n1{c2 .} ==> r4c3≠7whip[7]: r5c1{n6 n8} - c6n8{r5 r2} - r2n9{c6 c2} - c2n5{r2 r8} - c2n1{r8 r4} - r4c3{n1 n2} - r4c1{n2 .} ==> r6c2≠6whip[7]: c1n9{r6 r9} - c1n2{r9 r4} - c1n8{r4 r5} - r4c3{n8 n1} - c2n1{r4 r8} - c2n5{r8 r2} - c2n9{r2 .} ==> r6c1≠5PUZZLE 0 IS NOT SOLVED. 53 VALUES MISSING.Final resolution state:   +-------------------+-------------------+-------------------+    ! 15    2     3     ! 1467  4567  467   ! 14567 8     9     !    ! 4     59    6     ! 127   3578  789   ! 157   37    27    !    ! 7     8     159   ! 1246  3456  2469  ! 1456  346   246   !    +-------------------+-------------------+-------------------+    ! 128   1347  128   ! 467   4678  5     ! 3467  9     467   !    ! 68    3467  478   ! 9     2     4678  ! 347   5     1     !    ! 69    457   4579  ! 3     467   1     ! 2     467   8     !    +-------------------+-------------------+-------------------+    ! 3     4679  24789 ! 5     467   2467  ! 89    1     467   !    ! 156   14567 1457  ! 8     9     467   ! 467   2     3     !    ! 289   4679  24789 ! 2467  1     3     ! 89    467   5     !    +-------------------+-------------------+-------------------+ `

This RS still requires T&E(2) to be solved. So, the original puzzle has been downgraded from T&E(3) to T&E(2) without using any other impossible pattern.
denis_berthier
2010 Supporter

Posts: 3536
Joined: 19 June 2007
Location: Paris

### Re: T&E(2) patterns and puzzles

denis_berthier wrote:
totuan wrote:IMO, I’m not sure but just checked some on “min_expand_20221106_basics_special_only_full” then many puzzles need other impossible pattern beside TH (trivalue oddagon) to downgrade…
Code: Select all
`.23....894.6......78............5.9....92..51...3.12.83..5...1....89..23....13..5;37;269;13;3;n467;b5p168+b6p348+b8p267+b9p348    line 228 *--------------------------------------------------------------------* | 15     2      3      | 1467   4567   467    | 14567  8      9      | | 4      159    6      | 127    3578   2789   | 157    37     27     | | 7      8      159    | 1246   3456   2469   | 1456   346    246    | |----------------------+----------------------+----------------------| | 1268   13467  12478  |*467    4678   5      |#3467   9     #467    | | 68   A#3467   478    | 9      2     *4678   | 467-3  5      1      | A => r4c7=3 | 569    45679  4579   | 3     *467    1      | 2     #467    8      | |----------------------+----------------------+----------------------| | 3     #4679   24789  | 5     *467    2467   | 89     1     *467    | | 156    14567  1457   | 8      9     *467    |*467    2      3      | | 2689  #4679   24789  |*2467   1      3      | 89    *467    5      | *--------------------------------------------------------------------*`

I'm not sure to understand what you mean.

I meant - for this one, using impossible pattern to eliminate 3r5c7 at start then after this one is easy to downgrade with guardians 8r5c6 & 2r9c4.
BTW, WC: France 3-1 Poland

totuan
totuan

Posts: 169
Joined: 25 May 2010
Location: vietnam

### Re: T&E(2) patterns and puzzles

.
Hi totuan,

Among the 63,137 min-expands (min-expands are the only puzzles we need to consider), 49,651 can be solved in W8+OR5W8. That doesn't leave many puzzles not solvable using only Tridagon rules, but that leaves place for more puzzles being solved:
- either in Wn+ORkWn for k>5 and/or n>8,
- or with ORk-chains more complex than ORk-whips: ORk-g-whips, ORk-braids, ORk-g-braids.., and their forcing counterparts,
- or both.

Admitedly, even so, there will remain a few puzzles that can't be solved with only such rules and that remain in T&E(2) after their application. Among these few, some may be solved by applying patterns that can be proven contradictory in T&E(2).
(Notice that, among the puzzles solvable by tridagon rules, some solutions rely on versions of the original anti-tridagon that degenerate during the resolution process, i.e. on impossible patterns that I have proven to be in T&E(2).)

But there's no reason to restrict our considerations to such tridagon-related puzzles. What I mean in this thread is:
- start from patterns that are known to belong to T&E(2) - e.g. eleven's list of impossible patterns (excluding the only one in T&E(3) that'd better be considered in the T&E(3) thread),
- and generate puzzles that display them (patterns with no example have limited interest) - the method used by mith for puzzles with tridagons should work,
- more prospectively, have a principled approach to finding patterns in T&E(2), possibly starting from only the impossible patterns.
.
denis_berthier
2010 Supporter

Posts: 3536
Joined: 19 June 2007
Location: Paris