.
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.
.
T&E(2) patterns and puzzles
6 posts
• Page 1 of 1
T&E(2) patterns and puzzles
by denis_berthier » Mon Nov 28, 2022 7:16 am
- denis_berthier
- 2010 Supporter
- Posts: 4233
- Joined: 19 June 2007
- Location: Paris
Re: T&E(2) patterns and puzzles
by denis_berthier » Mon Nov 28, 2022 4:56 pm
.
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.
[Edit]: T&E(T, n) is coded in CSP-Rules for n≤3. T can be selected in the config file
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).
[Edit]: 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: 4233
- Joined: 19 June 2007
- Location: Paris
Re: T&E(2) patterns and puzzles
by totuan » Sun Dec 04, 2022 3:31 pm
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… 
It’s not hard to prove those impossible patterns (some cases that needs to use RT in puzzles).
totuan
Hidden Text: Show
It’s not hard to prove those impossible patterns (some cases that needs to use RT in puzzles).
totuan
- totuan
- Posts: 249
- Joined: 25 May 2010
- Location: vietnam
Re: T&E(2) patterns and puzzles
by denis_berthier » Sun Dec 04, 2022 4:40 pm
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;1
3;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, r7c9
with 3 guardians: n8r5c6 n3r5c7 n2r9c4
t-whip[4]: r7n2{c6 c3} - r7n8{c3 c7} - r7n9{c7 c2} - r2n9{c2 .} ==> r2c6≠2
t-whip[5]: c1n9{r6 r9} - c1n2{r9 r4} - c1n8{r4 r5} - c6n8{r5 r2} - r2n9{c6 .} ==> r6c2≠9
t-whip[5]: r2n9{c2 c6} - r2n8{c6 c5} - c5n3{r2 r3} - c5n5{r3 r1} - r1c1{n5 .} ==> r2c2≠1
Trid-OR3-whip[5]: r5c1{n6 n8} - c6n8{r5 r2} - OR3{{n8r5c6 n3r5c7 | n2r9c4}} - b2n2{r2c4 r3c6} - c6n9{r3 .} ==> r5c7≠6
Trid-OR3-ctr-whip[6]: c2n3{r4 r5} - r5n6{c2 c6} - c6n8{r5 r2} - c6n9{r2 r3} - c6n2{r3 r7} - OR3{{n2r9c4 n3r5c7 n8r5c6 | .}} ==> r4c2≠6
Trid-OR3-ctr-whip[6]: c1n2{r4 r9} - c3n2{r9 r4} - r4n1{c3 c2} - c2n3{r4 r5} - r5n6{c2 c6} - OR3{{n2r9c4 n3r5c7 n8r5c6 | .}} ==> r4c1≠6
whip[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≠6
Trid-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≠4
Trid-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≠7
whip[7]: r5c1{n6 n8} - c6n8{r5 r2} - r2n9{c6 c2} - c2n5{r2 r8} - c2n1{r8 r4} - r4c3{n1 n2} - r4c1{n2 .} ==> r6c2≠6
whip[7]: c1n9{r6 r9} - c1n2{r9 r4} - c1n8{r4 r5} - r4c3{n8 n1} - c2n1{r4 r8} - c2n5{r8 r2} - c2n9{r2 .} ==> r6c1≠5
PUZZLE 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: 4233
- Joined: 19 June 2007
- Location: Paris
Re: T&E(2) patterns and puzzles
by totuan » Sun Dec 04, 2022 5:26 pm
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;1
3;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: 249
- Joined: 25 May 2010
- Location: vietnam
Re: T&E(2) patterns and puzzles
by denis_berthier » Mon Dec 05, 2022 4:56 am
.
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.
.
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: 4233
- Joined: 19 June 2007
- Location: Paris
6 posts
• Page 1 of 1
