The tridagon rule

Advanced methods and approaches for solving Sudoku puzzles

Re: The tridagon rule

Postby denis_berthier » Sun Sep 11, 2022 7:55 am

.
ORk-FW classification results for mith's 63137 min-expand puzzles in T&E(3):

Puzzles solved in SFin+Trid+Wn+ORkFWn
Code: Select all
-----------------------------------------------------------------------
        n=3                 n=5                 n=7                 n=8    
-----------------------------------------------------------------------
     8 ,196   puzzles solved by SFin+Trid (among 63 137 min-expands)   
-----------------------------------------------------------------------
k=0   8,137              17,532              21,160              22,332
     16,333       9,395  25,728       3,628  29,356       1,172  30,528
-----------------------------------------------------------------------
k=2   3,350               8,713              11,231              12,068   
     19,683      14,758  34,441       6,146  40,587       2,009  42,596   
-----------------------------------------------------------------------
k=3     428               2,255               3,471      
     20,111      16,585  36,696       7,362  44,058      
-----------------------------------------------------------------------
k=4      67                 365                 540      
     20,178      16,883  37,061       7,537  44,598      
-----------------------------------------------------------------------
k=5       2                  28                  99      
     20,180      16,909  37,089       7,608  44,697      
-----------------------------------------------------------------------
k=6       0                   4            
     20,180      16,913  37,093   
-----------------------------------------------------------------------

Lines are separated by dashes, columns are separated by large white spaces.
Each (k, n) cell has three values in it:
- the main one, in the lower right corner, is the total number of puzzles solved by SFin + Trid + Wn + ORkFWn;
- the value above it is the difference with the previous line; it shows what’s gained by increasing k by 1;
- the value on the left of the main number is the difference with the previous cell; it shows what’s gained by increasing n.

Some general conclusions can be drawn from this table:
• for fixed n, as k increases, the difference between two lines decreases quite fast; this shouldn’t be too surprising, as larger k means more chains have to converge to the same candidate;
• for fixed k, as n increases, the difference between two columns decreases quite fast; this shouldn’t be too surprising either, as it already happens with all the “classical” chains (whips…);
• starting from k=2 and n=3, at any point in the table, it is much more fruitful to increase n than to increase k;

I'll give a similar table for ORk-Contrad-Whips, but the calculations are still running.

[Edit]:added case (k=2, n=8)
denis_berthier
2010 Supporter
 
Posts: 4238
Joined: 19 June 2007
Location: Paris

Re: The tridagon rule

Postby denis_berthier » Tue Sep 13, 2022 5:10 am

.
Degenerated trivalue-oddagons: case of 1 decided value

Suppose that, instead of the standard contradictory trivlaue-oddagon pattern, with alll 3 candidates in all 12 cells, one of its cells is a decided value; say r1c1=1.
It is obvious that this pattern is still contradictory. However, it no longer requires T&E(3) to be proven contradictory: this can be done in T&E(2).


The pattern is (modulo isomorphisms):
Code: Select all
+-------------------------------+-------------------------------+-------------------------------+
! 1         123456789 123456789 ! 123       123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123       123456789 ! 123456789 123       123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123       ! 123456789 123456789 123       ! 123456789 123456789 123456789 !
+-------------------------------+-------------------------------+-------------------------------+
! 123       123456789 123456789 ! 123456789 123456789 123       ! 123456789 123456789 123456789 !
! 123456789 123       123456789 ! 123456789 123       123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123       ! 123       123456789 123456789 ! 123456789 123456789 123456789 !
+-------------------------------+-------------------------------+-------------------------------+
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
+-------------------------------+-------------------------------+-------------------------------+


Here is a way to prove the contradiction in T&E(2), using SudoRules.
Choose T&E(2) in the configuration file.
If you try to apply function "solve-sukaku-grid" to the above resolution state, computations will take too long.
On the other hand, if you try to use function "solve-k-digit-pattern-string" directly, the candidates n2r1c2 and n3r1c1 will not be deleted before starting.

There is a way out of this. Use the following two commands:
Code: Select all
(bind ?*simulated-eliminations* (create$ 211 311))
(solve-k-digit-pattern-string 3 "100100000010010000001001000100001000010010000001100000000000000000000000000000000")


SudoRules outputs a quick and short proof of the contradiction in T&E(2):

Hidden Text: Show
Code: Select all
***********************************************************************************************
***  SudoRules 20.1.s based on CSP-Rules 2.1.s, config = T&E(BRT, 2)
***  Using CLIPS 6.32-r823
***  Running on MacBookPro 16'' M1Max 2021, 64GB LPDDR5, MacOS 12.5
***  Download from: https://github.com/denis-berthier/CSP-Rules-V2.1
***********************************************************************************************
100100000010010000001001000100001000010010000001100000000000000000000000000000000
Simulated elimination of 311
Simulated elimination of 211
naked-single ==> r1c1=1
Resolution state after Singles:
   +-------------------------------+-------------------------------+-------------------------------+
   ! 1         23456789  23456789  ! 23        23456789  23456789  ! 23456789  23456789  23456789  !
   ! 23456789  23        23456789  ! 123456789 123       123456789 ! 123456789 123456789 123456789 !
   ! 23456789  23456789  23        ! 123456789 123456789 123       ! 123456789 123456789 123456789 !
   +-------------------------------+-------------------------------+-------------------------------+
   ! 23        123456789 123456789 ! 123456789 123456789 123       ! 123456789 123456789 123456789 !
   ! 23456789  123       123456789 ! 123456789 123       123456789 ! 123456789 123456789 123456789 !
   ! 23456789  123456789 123       ! 123       123456789 123456789 ! 123456789 123456789 123456789 !
   +-------------------------------+-------------------------------+-------------------------------+
   ! 23456789  123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
   ! 23456789  123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
   ! 23456789  123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
   +-------------------------------+-------------------------------+-------------------------------+

634 candidates, 0 csp-links and 0 links. Density = 0.0%
Starting non trivial part of solution.

*** STARTING T&E IN CONTEXT 0 at depth 1 with 1 csp-variables solved and 634 candidates remaining ***

        STARTING PHASE 1 IN CONTEXT 0 with 1 csp-variables solved and 634 candidates remaining


GENERATING CONTEXT 1 AT DEPTH 1, SON OF CONTEXT 0, FROM HYPOTHESIS n3r6c4.
naked-single ==> r1c4=2

*** STARTING T&E IN CONTEXT 1 at depth 1 with 1 csp-variables solved and 634 candidates remaining ***

        STARTING PHASE 1 IN CONTEXT 1 AT DEPTH 1, with 1 csp-variables solved and 634 candidates remaining


GENERATING CONTEXT 2 AT DEPTH 2, SON OF CONTEXT 1, FROM HYPOTHESIS n2r2c2.
naked-single ==> r3c3=3
naked-single ==> r3c6=1
naked-single ==> r2c5=3
naked-single ==> r4c6=2
naked-single ==> r4c1=3
naked-single ==> r5c2=1
NO POSSIBLE VALUE for csp-variable 155 IN CONTEXT 2. RETRACTING CANDIDATE n2r2c2 FROM CONTEXT 1.

BACK IN CONTEXT 1 with 1 csp-variables solved and 634 candidates remaining.

naked-single ==> r2c2=3
naked-single ==> r3c3=2
naked-single ==> r6c3=1
naked-single ==> r5c2=2
naked-single ==> r5c5=1
NO POSSIBLE VALUE for csp-variable 125 IN CONTEXT 1. RETRACTING CANDIDATE n3r6c4 FROM CONTEXT 0.

BACK IN CONTEXT 0 with 1 csp-variables solved and 633 candidates remaining.


GENERATING CONTEXT 3 AT DEPTH 1, SON OF CONTEXT 0, FROM HYPOTHESIS n2r6c4.
naked-single ==> r1c4=3

*** STARTING T&E IN CONTEXT 3 at depth 1 with 1 csp-variables solved and 633 candidates remaining ***

        STARTING PHASE 1 IN CONTEXT 3 AT DEPTH 1, with 1 csp-variables solved and 633 candidates remaining


GENERATING CONTEXT 4 AT DEPTH 2, SON OF CONTEXT 3, FROM HYPOTHESIS n2r2c2.
naked-single ==> r3c3=3
naked-single ==> r6c3=1
naked-single ==> r5c2=3
naked-single ==> r4c1=2
naked-single ==> r5c5=1
NO POSSIBLE VALUE for csp-variable 125 IN CONTEXT 4. RETRACTING CANDIDATE n2r2c2 FROM CONTEXT 3.

BACK IN CONTEXT 3 with 1 csp-variables solved and 633 candidates remaining.

naked-single ==> r2c2=3
naked-single ==> r3c3=2
naked-single ==> r3c6=1
naked-single ==> r4c6=3
naked-single ==> r5c5=1
naked-single ==> r5c2=2
NO POSSIBLE VALUE for csp-variable 141 IN CONTEXT 3. RETRACTING CANDIDATE n2r6c4 FROM CONTEXT 0.

BACK IN CONTEXT 0 with 1 csp-variables solved and 632 candidates remaining.

naked-single ==> r6c4=1

GENERATING CONTEXT 5 AT DEPTH 1, SON OF CONTEXT 0, FROM HYPOTHESIS n3r6c3.
naked-single ==> r3c3=2
naked-single ==> r2c2=3
naked-single ==> r4c1=2
naked-single ==> r5c2=1
naked-single ==> r4c6=3
naked-single ==> r5c5=2
naked-single ==> r2c5=1
NO POSSIBLE VALUE for csp-variable 136 IN CONTEXT 5. RETRACTING CANDIDATE n3r6c3 FROM CONTEXT 0.

BACK IN CONTEXT 0 with 2 csp-variables solved and 612 candidates remaining.

naked-single ==> r6c3=2
naked-single ==> r3c3=3
naked-single ==> r2c2=2
naked-single ==> r4c1=3
naked-single ==> r4c6=2
naked-single ==> r3c6=1
naked-single ==> r2c5=3

PUZZLE 0 HAS NO SOLUTION : NO CANDIDATE FOR RC-CELL r5c5
MOST COMPLEX RULE TRIED = NS
Puzzle 100100000010010000001001000100001000010010000001100000000000000000000000000000000 :
init-time = 0.0s, solve-time = 0.11s, total-time = 0.11s

.
Last edited by denis_berthier on Wed Sep 28, 2022 3:22 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 4238
Joined: 19 June 2007
Location: Paris

Re: The tridagon rule

Postby denis_berthier » Tue Sep 13, 2022 5:16 am

.
Degenerated trivalue-oddagons: case of 1 missing candidate

Suppose that, instead of the standard contradictory trivlaue-oddagon pattern, with alll 3 candidates in all 12 cells, one of these candidates is missing; say n3r1c1.
It is obvious that this pattern is still contradictory. However, it no longer requires T&E(3) to be proven contradictory: this can be done in T&E(2).


The pattern is (modulo isomorphisms):
Code: Select all
+-------------------------------+-------------------------------+-------------------------------+
! 12        123456789 123456789 ! 123       123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123       123456789 ! 123456789 123       123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123       ! 123456789 123456789 123       ! 123456789 123456789 123456789 !
+-------------------------------+-------------------------------+-------------------------------+
! 123       123456789 123456789 ! 123456789 123456789 123       ! 123456789 123456789 123456789 !
! 123456789 123       123456789 ! 123456789 123       123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123       ! 123       123456789 123456789 ! 123456789 123456789 123456789 !
+-------------------------------+-------------------------------+-------------------------------+
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
+-------------------------------+-------------------------------+-------------------------------+


Here is a way to prove the contradiction in T&E(2), using SudoRules, in the same way as before.
Choose T&E(2) in the configuration file.
Use the following two commands:
Code: Select all
(bind ?*simulated-eliminations* (create$ 311))
(solve-k-digit-pattern-string 3 "100100000010010000001001000100001000010010000001100000000000000000000000000000000")


SudoRules still outputs a quick and short proof (though not as short as before) of the contradiction in T&E(2):

Hidden Text: Show
Code: Select all
***********************************************************************************************
***********************************************************************************************
***  SudoRules 20.1.s based on CSP-Rules 2.1.s, config = T&E(BRT, 2)
***  Using CLIPS 6.32-r823
***  Running on MacBookPro 16'' M1Max 2021, 64GB LPDDR5, MacOS 12.5
***  Download from: https://github.com/denis-berthier/CSP-Rules-V2.1
***********************************************************************************************
100100000010010000001001000100001000010010000001100000000000000000000000000000000
Simulated elimination of 311
Resolution state after Singles:
   +-------------------------------+-------------------------------+-------------------------------+
   ! 12        123456789 123456789 ! 123       123456789 123456789 ! 123456789 123456789 123456789 !
   ! 123456789 123       123456789 ! 123456789 123       123456789 ! 123456789 123456789 123456789 !
   ! 123456789 123456789 123       ! 123456789 123456789 123       ! 123456789 123456789 123456789 !
   +-------------------------------+-------------------------------+-------------------------------+
   ! 123       123456789 123456789 ! 123456789 123456789 123       ! 123456789 123456789 123456789 !
   ! 123456789 123       123456789 ! 123456789 123       123456789 ! 123456789 123456789 123456789 !
   ! 123456789 123456789 123       ! 123       123456789 123456789 ! 123456789 123456789 123456789 !
   +-------------------------------+-------------------------------+-------------------------------+
   ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
   ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
   ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
   +-------------------------------+-------------------------------+-------------------------------+

656 candidates, 0 csp-links and 0 links. Density = 0.0%
Starting non trivial part of solution.

*** STARTING T&E IN CONTEXT 0 at depth 1 with 0 csp-variables solved and 656 candidates remaining ***

        STARTING PHASE 1 IN CONTEXT 0 with 0 csp-variables solved and 656 candidates remaining


GENERATING CONTEXT 1 AT DEPTH 1, SON OF CONTEXT 0, FROM HYPOTHESIS n3r6c4.

*** STARTING T&E IN CONTEXT 1 at depth 1 with 0 csp-variables solved and 656 candidates remaining ***

        STARTING PHASE 1 IN CONTEXT 1 AT DEPTH 1, with 0 csp-variables solved and 656 candidates remaining


GENERATING CONTEXT 2 AT DEPTH 2, SON OF CONTEXT 1, FROM HYPOTHESIS n1r1c1.
naked-single ==> r1c4=2
NO CONTRADICTION FOUND IN CONTEXT 2.
BACK IN CONTEXT 1 with 0 csp-variables solved and 656 candidates remaining.


GENERATING CONTEXT 3 AT DEPTH 2, SON OF CONTEXT 1, FROM HYPOTHESIS n2r1c1.
naked-single ==> r1c4=1
NO CONTRADICTION FOUND IN CONTEXT 3.
BACK IN CONTEXT 1 with 0 csp-variables solved and 656 candidates remaining.


GENERATING CONTEXT 4 AT DEPTH 2, SON OF CONTEXT 1, FROM HYPOTHESIS n1r1c4.
naked-single ==> r1c1=2
NO CONTRADICTION FOUND IN CONTEXT 4.
BACK IN CONTEXT 1 with 0 csp-variables solved and 656 candidates remaining.


GENERATING CONTEXT 5 AT DEPTH 2, SON OF CONTEXT 1, FROM HYPOTHESIS n2r1c4.
naked-single ==> r1c1=1
NO CONTRADICTION FOUND IN CONTEXT 5.
BACK IN CONTEXT 1 with 0 csp-variables solved and 656 candidates remaining.


GENERATING CONTEXT 6 AT DEPTH 2, SON OF CONTEXT 1, FROM HYPOTHESIS n1r2c2.
naked-single ==> r1c1=2
naked-single ==> r1c4=1
naked-single ==> r3c3=3
naked-single ==> r3c6=2
naked-single ==> r2c5=3
naked-single ==> r4c6=1
naked-single ==> r4c1=3
naked-single ==> r5c2=2
NO POSSIBLE VALUE for csp-variable 155 IN CONTEXT 6. RETRACTING CANDIDATE n1r2c2 FROM CONTEXT 1.

BACK IN CONTEXT 1 with 0 csp-variables solved and 656 candidates remaining.


GENERATING CONTEXT 7 AT DEPTH 2, SON OF CONTEXT 1, FROM HYPOTHESIS n2r2c2.
naked-single ==> r1c1=1
naked-single ==> r1c4=2
naked-single ==> r3c3=3
naked-single ==> r3c6=1
naked-single ==> r2c5=3
naked-single ==> r4c6=2
naked-single ==> r4c1=3
naked-single ==> r5c2=1
NO POSSIBLE VALUE for csp-variable 155 IN CONTEXT 7. RETRACTING CANDIDATE n2r2c2 FROM CONTEXT 1.

BACK IN CONTEXT 1 with 0 csp-variables solved and 656 candidates remaining.

naked-single ==> r2c2=3

GENERATING CONTEXT 8 AT DEPTH 2, SON OF CONTEXT 1, FROM HYPOTHESIS n1r2c5.
naked-single ==> r5c5=2
naked-single ==> r4c6=1
naked-single ==> r5c2=1
naked-single ==> r6c3=2
naked-single ==> r3c3=1
naked-single ==> r1c1=2
NO POSSIBLE VALUE for csp-variable 114 IN CONTEXT 8. RETRACTING CANDIDATE n1r2c5 FROM CONTEXT 1.

BACK IN CONTEXT 1 with 0 csp-variables solved and 656 candidates remaining.

naked-single ==> r2c5=2
naked-single ==> r5c5=1
naked-single ==> r5c2=2
naked-single ==> r6c3=1
naked-single ==> r4c1=3
naked-single ==> r3c3=2
naked-single ==> r1c1=1
NO POSSIBLE VALUE for csp-variable 114 IN CONTEXT 1. RETRACTING CANDIDATE n3r6c4 FROM CONTEXT 0.

BACK IN CONTEXT 0 with 0 csp-variables solved and 655 candidates remaining.


GENERATING CONTEXT 9 AT DEPTH 1, SON OF CONTEXT 0, FROM HYPOTHESIS n2r6c4.

*** STARTING T&E IN CONTEXT 9 at depth 1 with 0 csp-variables solved and 655 candidates remaining ***

        STARTING PHASE 1 IN CONTEXT 9 AT DEPTH 1, with 0 csp-variables solved and 655 candidates remaining


GENERATING CONTEXT 10 AT DEPTH 2, SON OF CONTEXT 9, FROM HYPOTHESIS n1r1c1.
naked-single ==> r1c4=3
NO CONTRADICTION FOUND IN CONTEXT 10.
BACK IN CONTEXT 9 with 0 csp-variables solved and 655 candidates remaining.


GENERATING CONTEXT 11 AT DEPTH 2, SON OF CONTEXT 9, FROM HYPOTHESIS n2r1c1.
NO CONTRADICTION FOUND IN CONTEXT 11.
BACK IN CONTEXT 9 with 0 csp-variables solved and 655 candidates remaining.


GENERATING CONTEXT 12 AT DEPTH 2, SON OF CONTEXT 9, FROM HYPOTHESIS n1r1c4.
naked-single ==> r1c1=2
NO CONTRADICTION FOUND IN CONTEXT 12.
BACK IN CONTEXT 9 with 0 csp-variables solved and 655 candidates remaining.


GENERATING CONTEXT 13 AT DEPTH 2, SON OF CONTEXT 9, FROM HYPOTHESIS n3r1c4.
NO CONTRADICTION FOUND IN CONTEXT 13.
BACK IN CONTEXT 9 with 0 csp-variables solved and 655 candidates remaining.


GENERATING CONTEXT 14 AT DEPTH 2, SON OF CONTEXT 9, FROM HYPOTHESIS n1r2c2.
naked-single ==> r1c1=2
naked-single ==> r3c3=3
naked-single ==> r6c3=1
naked-single ==> r4c1=3
naked-single ==> r4c6=1
naked-single ==> r3c6=2
naked-single ==> r2c5=3
NO POSSIBLE VALUE for csp-variable 155 IN CONTEXT 14. RETRACTING CANDIDATE n1r2c2 FROM CONTEXT 9.

BACK IN CONTEXT 9 with 0 csp-variables solved and 655 candidates remaining.


GENERATING CONTEXT 15 AT DEPTH 2, SON OF CONTEXT 9, FROM HYPOTHESIS n2r2c2.
naked-single ==> r1c1=1
naked-single ==> r1c4=3
naked-single ==> r2c5=1
naked-single ==> r3c6=2
naked-single ==> r5c5=3
naked-single ==> r4c6=1
naked-single ==> r5c2=1
naked-single ==> r6c3=3
NO POSSIBLE VALUE for csp-variable 133 IN CONTEXT 15. RETRACTING CANDIDATE n2r2c2 FROM CONTEXT 9.

BACK IN CONTEXT 9 with 0 csp-variables solved and 655 candidates remaining.

naked-single ==> r2c2=3

GENERATING CONTEXT 16 AT DEPTH 2, SON OF CONTEXT 9, FROM HYPOTHESIS n1r2c5.
naked-single ==> r5c5=3
naked-single ==> r4c6=1
naked-single ==> r1c4=3
naked-single ==> r3c6=2
naked-single ==> r3c3=1
naked-single ==> r1c1=2
naked-single ==> r4c1=3
NO POSSIBLE VALUE for csp-variable 163 IN CONTEXT 16. RETRACTING CANDIDATE n1r2c5 FROM CONTEXT 9.

BACK IN CONTEXT 9 with 0 csp-variables solved and 655 candidates remaining.

naked-single ==> r2c5=2

GENERATING CONTEXT 17 AT DEPTH 2, SON OF CONTEXT 9, FROM HYPOTHESIS n1r3c3.
naked-single ==> r6c3=3
naked-single ==> r3c6=3
naked-single ==> r1c4=1
naked-single ==> r4c6=1
naked-single ==> r4c1=2
NO POSSIBLE VALUE for csp-variable 111 IN CONTEXT 17. RETRACTING CANDIDATE n1r3c3 FROM CONTEXT 9.

BACK IN CONTEXT 9 with 0 csp-variables solved and 655 candidates remaining.

naked-single ==> r3c3=2
naked-single ==> r1c1=1
naked-single ==> r1c4=3
naked-single ==> r3c6=1
naked-single ==> r4c6=3
naked-single ==> r5c5=1
naked-single ==> r5c2=2
NO POSSIBLE VALUE for csp-variable 141 IN CONTEXT 9. RETRACTING CANDIDATE n2r6c4 FROM CONTEXT 0.

BACK IN CONTEXT 0 with 0 csp-variables solved and 654 candidates remaining.

naked-single ==> r6c4=1

GENERATING CONTEXT 18 AT DEPTH 1, SON OF CONTEXT 0, FROM HYPOTHESIS n3r6c3.

*** STARTING T&E IN CONTEXT 18 at depth 1 with 1 csp-variables solved and 633 candidates remaining ***

        STARTING PHASE 1 IN CONTEXT 18 AT DEPTH 1, with 1 csp-variables solved and 633 candidates remaining


GENERATING CONTEXT 19 AT DEPTH 2, SON OF CONTEXT 18, FROM HYPOTHESIS n1r1c1.
naked-single ==> r4c1=2
naked-single ==> r4c6=3
naked-single ==> r5c5=2
naked-single ==> r5c2=1
naked-single ==> r3c3=2
naked-single ==> r2c2=3
naked-single ==> r2c5=1
NO POSSIBLE VALUE for csp-variable 136 IN CONTEXT 19. RETRACTING CANDIDATE n1r1c1 FROM CONTEXT 18.

BACK IN CONTEXT 18 with 1 csp-variables solved and 633 candidates remaining.

naked-single ==> r1c1=2
naked-single ==> r4c1=1
naked-single ==> r5c2=2
naked-single ==> r5c5=3
naked-single ==> r4c6=2
naked-single ==> r3c3=1
naked-single ==> r3c6=3
NO POSSIBLE VALUE for csp-variable 114 IN CONTEXT 18. RETRACTING CANDIDATE n3r6c3 FROM CONTEXT 0.

BACK IN CONTEXT 0 with 1 csp-variables solved and 632 candidates remaining.

naked-single ==> r6c3=2

GENERATING CONTEXT 20 AT DEPTH 1, SON OF CONTEXT 0, FROM HYPOTHESIS n3r5c5.
naked-single ==> r4c6=2
naked-single ==> r5c2=1
naked-single ==> r4c1=3

*** STARTING T&E IN CONTEXT 20 at depth 1 with 2 csp-variables solved and 612 candidates remaining ***

        STARTING PHASE 1 IN CONTEXT 20 AT DEPTH 1, with 2 csp-variables solved and 612 candidates remaining


GENERATING CONTEXT 21 AT DEPTH 2, SON OF CONTEXT 20, FROM HYPOTHESIS n1r1c1.
naked-single ==> r3c3=3
naked-single ==> r2c2=2
naked-single ==> r2c5=1
NO POSSIBLE VALUE for csp-variable 136 IN CONTEXT 21. RETRACTING CANDIDATE n1r1c1 FROM CONTEXT 20.

BACK IN CONTEXT 20 with 2 csp-variables solved and 612 candidates remaining.

naked-single ==> r1c1=2
naked-single ==> r2c2=3
naked-single ==> r3c3=1
naked-single ==> r3c6=3
NO POSSIBLE VALUE for csp-variable 114 IN CONTEXT 20. RETRACTING CANDIDATE n3r5c5 FROM CONTEXT 0.

BACK IN CONTEXT 0 with 2 csp-variables solved and 611 candidates remaining.

naked-single ==> r5c5=2
naked-single ==> r4c6=3
naked-single ==> r4c1=1
naked-single ==> r1c1=2
naked-single ==> r1c4=3
naked-single ==> r2c5=1
naked-single ==> r2c2=3

PUZZLE 0 HAS NO SOLUTION : NO CANDIDATE FOR RC-CELL r5c2
MOST COMPLEX RULE TRIED = NS
Puzzle 100100000010010000001001000100001000010010000001100000000000000000000000000000000 :
init-time = 0.0s, solve-time = 0.25s, total-time = 0.25s
s

.
Last edited by denis_berthier on Wed Sep 28, 2022 3:23 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 4238
Joined: 19 June 2007
Location: Paris

Re: The tridagon rule

Postby denis_berthier » Fri Sep 16, 2022 4:19 pm

.
ORk-CW classification results for mith's 63137 min-expand puzzles in T&E(3):

Here are results for ORk-Contrad-Whips similar to those for ORk-Forcing-Whips in the first post of this page.

Puzzles solved in SFin+Trid+Wn+ORkCWn
Code: Select all
-----------------------------------------------------------------------
        n=3                 n=5                 n=7                 n=8    
-----------------------------------------------------------------------
     8 ,196   puzzles solved by SFin+Trid (among 63 137 min-expands)   
-----------------------------------------------------------------------
k=0   8,137              17,532              21,160              22,332
     16,333       9,395  25,728       3,628  29,356       1,172  30,528
-----------------------------------------------------------------------
k=2   1,700               6,276               8,863               9,944   
     18,033      13,971  32,004       6,215  38,219       2,253  40,472   
-----------------------------------------------------------------------
k=3     286               1,379               2,413      
     18,319      15,064  33,383       7,249  40,632      
-----------------------------------------------------------------------
k=4      49                 319                 478      
     18,368      15,534  33,702       7,408  41,110      
-----------------------------------------------------------------------
k=5       6                  25                 111      
     18,374      15,353  33,727       7,494  41,221      
-----------------------------------------------------------------------

Same conventions as above:
Lines are separated by dashes, columns are separated by large white spaces.
Each (k, n) cell has three values in it:
- the main one, in the lower right corner, is the total number of puzzles solved by SFin + Trid + Wn + ORkFWn;
- the value above it is the difference with the previous line; it shows what’s gained by increasing k by 1;
- the value on the left of the main number is the difference with the previous cell; it shows what’s gained by increasing n.

And also same general conclusions:
• for fixed n, as k increases, the difference between two lines decreases quite fast; this shouldn’t be too surprising, as larger k means more chains have to converge to the same candidate;
• for fixed k, as n increases, the difference between two columns decreases quite fast; this shouldn’t be too surprising either, as it already happens with all the “classical” chains (whips…);
• starting from k=2 and n=3, at any point in the table, it is much more fruitful to increase n than to increase k;

Plus a new one:
For any fixed k and n, ORk-Forcing-Whips are more powerful than ORk-Contrad-Whips
denis_berthier
2010 Supporter
 
Posts: 4238
Joined: 19 June 2007
Location: Paris

Re: The tridagon rule

Postby denis_berthier » Wed Oct 26, 2022 7:14 am

.
ORk-W classification results for mith's 63137 min-expand puzzles in T&E(3):

I've almost completed calculations similar to the above ones, for the classification of the 63137 min-expand database:
1) using ORk-whips instead of ORk-forcing-whips or ORk-contrad-whips;
2) using all the ORk-chains together.

The global results and general conclusions are similar to the above ones, with some additional conclusions:
- for any k and n, there is a large overlap between what can be solved with ORk-whips[n] and what can be solved with ORk-forcing-whips[n];
- for any k and n, ORk-whips[n] (which include ORk-contrad-whips as a special case) have a greater resolution power than ORk-forcing-whips[n];
- most of the puzzles that have a solution with ORk-forcing-whips[n] also have one with ORk-whips[n] but the converse is not true: for instance, only 96 puzzles can be solved in SFin+Trid+W5+OR5FW5 but not in SFin+Trid+W5+OR5W5; whereas 1894 can be solved in SFin+Trid+W5+OR5W5 but not in SFin+Trid+W5+ OR5FW5; and the difference is still larger for n=7;
- the difference between ORk-forcing-whips and ORk-whips is not well compensated by increasing the FW lengths: for instance, only 55 puzzles can be solved in SFin+Trid+W5+OR5FW5 but still not in SFin+Trid+W7+OR5W7; whereas 683 can be solved in SFin+Trid+W5+OR5W5 but still not in SFin+Trid+W7+OR5FW7.

It is so complicated to format a table as those I've posted before that I don't try to do it for the ORk-whips. You will find all the details in the forthcoming new version of CSP-Rules manual.

I consider these results as important when one wants to choose which kinds of rules to use.

Notice also that:
- as much as 13% of the puzzles can be solved using only SFin+Trid (Subsets + Finned Fish + the elementary tridagon elimination rule with only 1 guardian); this may give the wrong idea that puzzles with the anti-tridagon pattern can easily be reduced to easy puzzles;
- BUT, even with whips[≤8] and all the ORk-chains[≤8], a noticeable proportion of the puzzles (21%) remains unsolved.
This is to be compared with the result that +99,97% of all the Sudoku puzzles (unbiased statistics - see [PBCS]) can be solved by whips[≤8].

This should be food for thought for people who might have had the idea that finding it was all there is to the anti-tridagon pattern.

As an aside remark, the above results also show that there are several different rating systems for puzzles in T&E(3). Even in case we choose the system based on all the types of ORk-chains, k remains as a parameter.
denis_berthier
2010 Supporter
 
Posts: 4238
Joined: 19 June 2007
Location: Paris

Re: The tridagon rule

Postby denis_berthier » Thu Dec 01, 2022 4:06 am

.
I don't plan to analyse mith's extended database of 158,276 min-expand puzzles (http://forum.enjoysudoku.com/t-e-3-puzzles-split-from-hardest-sudokus-thread-t40514.html) in as much detail as I've analysed the previous 83,177 one (mainly in this thread).
But here is an important result that remains valid after its publication:

All the known 9x9 sudoku puzzles in T&E(3) are indeed at most in T&E(W2, 2).
With the large number of minimal puzzles involved (847,778), this seems to entrench a new frontier of complexity.

(More detail here: http://forum.enjoysudoku.com/t-e-3-puzzles-split-from-hardest-sudokus-thread-t40514-18.html)
denis_berthier
2010 Supporter
 
Posts: 4238
Joined: 19 June 2007
Location: Paris

Re: The tridagon rule

Postby denis_berthier » Sat Apr 08, 2023 6:17 am

.
As a result of my previous analyses, the tridagon related ORk-chain rules are not enough to solve all the puzzles in T&E(3). How much resolution power does adding other impossible patterns bring? Do we need to use a lot more impossible patterns?

In this thread: http://forum.enjoysudoku.com/how-to-deal-with-large-numbers-of-patterns-t40889.html, I've analysed how to deal with large numbers of patterns.

As reported here: http://forum.enjoysudoku.com/csp-rules-sudorules-kakurules-t38200-80.html, I have found that, among the 630 impossible patterns in two bands or two stacks published by eleven, a few impossible patterns appear to be useful in T&E(3) puzzles with much higher frequencies than all the rest.
Most of these patterns are "close" to Tridagon.

The question that naturally arises now is: do these few patterns allow to solve most of the puzzles that could be solved with all the 630 impossible patterns?
This is of interest for manual solvers (who can't obviously learn 630 patterns) and for programmers (who may want to code only a few patterns).

I'll compare 4 sets of patterns (each pattern described in detail in the Augmented User Manual for CSP-Rules):
1) Tridagon
2) Imp630-Select1 (i.e. Trid + EL13c290 EL14c30 EL14c159 EL14c13 EL14c1)
3) Imp630-Select2 ( (i.e. Imp630-Select1 + EL13c30 EL10c28 EL13c179 EL13c176 EL13c234 EL13c171 EL10c6)
4) Imp630-all

In the 4 cases, the following ORk-chains are active: ORk-whips[n], with k≤5 and n≤8. This choice for k and n is based on previous analyses.
The analysis currently bears only on the first 10,000 puzzles in mith's list of 158,276 T&E(3) min-expands; but all my previous analyses on this list have shown little variation among the different slices of the whole list.

Two questions can be asked:
1) does going from one set of impossible patterns to the next allow to lower the ratings of puzzles?
It does in the following numbers of puzzles:
Code: Select all
Trid to Select1 = 1941
Select1 to Select2 = 396
Select2 to all = 215

Note that in most solvable cases, the difference in ratings is low (1 or 2).

2) does going from one set of impossible patterns to the next allow to solve more puzzles?
It does in the following numbers of puzzles:
Code: Select all
Trid to Select1 = 1171
Select1 to Select2 = 127
Select2 to all = 60

Note in particular that only 60 puzzles (in 10,000) can be solved when the 630 patterns are allowed but not when only Select2 is allowed.

It seems to me that Select2 is the right balance between number of patterns used and resolution power.

.
denis_berthier
2010 Supporter
 
Posts: 4238
Joined: 19 June 2007
Location: Paris

Re: The tridagon rule

Postby denis_berthier » Wed May 03, 2023 6:20 am

.
This post elaborates the results of the previous one, with the sets Select1, Select2 and Imp630 as above.
All the results are based on the first 60,000 puzzles of mith's list of 158,276 T&E(3) min-expands.
(Because nothing guarantees any kind of randomness in the 158,276 min-expand collection, the results may differ slightly if one uses the full collection instead. However, the computations have been extended progressively by slices of 10000 and they show no significant variations among the slices.)

The following table compares the cumulative distribution functions (expressed in %) of the S + W + T-OR5-W ratings for 4 sets T of impossible patterns (rows are for the sets of rules in the 1st column, columns are for n).
columns n = 1 and n = 2 have 0s because of the priority assigned to the detection of impossible patterns: immediately after S3.

Code: Select all
   n ->   1   2   3       4       5       6       7       8       rest
Trid      0   0   32.54   48.46   61.75   69.64   74.19   78.35   21.65
Select1   0   0   38.29   58.74   74.43   83.12   87.80   91.15   8.85
Select2   0   0   39.46   60.53   76.08   84.46   88.83   91.95   8.05
Imp630    0   0   40.23   61.74   77.32   85.55   89.58   92.45   7.55


The table clearly shows that:
– for any of the four T’s, increasing n brings diminishing returns – which we already knew from previous tables in the T = Trid case;
– going from Trid to Select1 allows to solve significantly more puzzles, be it globally or at any length ≤ 6;
– going from Select1 to Select2 has a much smaller impact;
– going from Select2 to all of Imp630 doesn’t bring much.

The results also show that increasing the maximal allowed chain length (n) by one is statistically much more useful than passing from Select1 to all of Imp630.

I think the above results fully justify my global approach of how to deal with large sets of impossible patterns and my general guideline for puzzles in T&E(3): first try a solution with no additional pattern and then, if not enough, with only a small set of them (Select1).

If a short summary is needed: starting from 630 impossible patterns, I've shown that, apart from rare cases (1.3%), only the five ones in Select1 are really useful.

So, I now consider that the right balance between resolution power and number of patterns is Select1 (not the larger Select2, as I said in my previous post).
.
denis_berthier
2010 Supporter
 
Posts: 4238
Joined: 19 June 2007
Location: Paris

Re: The tridagon rule

Postby denis_berthier » Sun May 14, 2023 11:55 am

.
More classification results.
Let's forget the 630 impossible patterns for a while and get back to the tridagon pattern and to mith's large collection of 158,276 T&E(3) min-expand puzzles.
Until now, I had provided statistical analyses only for the smaller collection of 63,137 ones.

My stats for the larger collection are based on a different approach: instead of concentrating on which puzzles are solvable depending on n and k, I used the previous result that, for the tridagon pattern, k=5 (the max number of guardians) is a good balance between resolution power and complexity and I computed the W+Trid-OR5W ratings (it doesn't make much difference with the previous tables for k=5, but it avoids redundant calculations).
The table below shows the distribution of the W+Trid-OR5W rating (with all the ultra-persistency and splitting rules active) for increasing slices of the larger collection. The last line is for the full collection. Column 0 is the slice size; columns 1 and 2 have zeroes because the tridagon pattern is looked for only after S3 and no puzzle in the list can be solved without a tridagon.

Code: Select all
rating -> 1   2   3       4       5       6      7      8      >8
 20,000   0   0   30.51   14.67   12.46   8.14   4.78   4.16   25.28
 40,000   0   0   31.08   14.14   12.73   7.82   4.71   4.21   24.31
 60,000   0   0   32.54   15.92   13.29   7.89   4.55   4.17   21.65
 80,000   0   0   30.72   15.61   13.36   8.14   4.82   4.28   23.07
100,000   0   0   30.49   15.00   13.01   7.98   4.85   4.23   24.44
120,000   0   0   30.89   14.95   12.99   7.98   4.82   4.20   24.17
140,000   0   0   31.41   14.71   12.75   7.84   4.86   4.21   24.22
158,276   0   0   31.60   15.00   13.15   7.94   4.86   4.20   23.25


The table shows slight fluctuations (to be expected, considering the way the collection was generated, by vicinity search) from one slice to the next larger one, with no systematic trend, in particular no noticeable trend for puzzles being harder or easier when one goes from the first ones to the full list.

This observation also provides some justification for my approach of eleven's 630 impossible patterns:
1) I used only the first 50,000 puzzles to define four increasing sets (Select1 ... Select4) of most "useful" patterns;
2) for the patterns thus found, I analysed their additional resolution power wrt tridagon and their missing resolution power wrt to the full 630 list;
3) the above analyses are progressively being extended from the initial sublist of 50,000 puzzles (when I and my Mac have free time); the progressive extension has currently reached 100,000 puzzles and it doesn't show any noticeable difference with the results for the first 60,000 reported in my previous posts. Considering this result, I may decide to stop the extension at this point.
.
denis_berthier
2010 Supporter
 
Posts: 4238
Joined: 19 June 2007
Location: Paris

Re: The tridagon rule

Postby denis_berthier » Thu Jun 01, 2023 5:28 am

.
Remember my old comparisons of ratings reported in [PBCS 1 to 3]
(https://www.researchgate.net/publication/280301697_Pattern-Based_Constraint_Satisfaction_and_Logic_Puzzles,...,
https://www.researchgate.net/publication/356313228_Pattern-Based_Constraint_Satisfaction_and_Logic_Puzzles_Third_Edition)
and recalled here:
http://forum.enjoysudoku.com/pattern-based-constraint-satisfaction-2nd-3rd-eds-t32567-11.html?

in particular those for the W and gW ratings, based on the 21,375 first puzzles of the controlled-bias collection (cbg-000 ):
denis_berthier wrote:W vs gW
Note that one must always have W ≥ gW
In reality, there are only 48 differences, i.e. a proportion of 0,22% differences.
And there are only 5 cases with difference > 1 (0,023%) and only one with difference > 2.


The question here is: what about the puzzles in T&E(3)? As this is a completely different collection - strongly biased, with all the puzzles having a particular pattern (tridagon) -, there's no a priori reason that would allow to extend the previous results to it. And indeed, they can't be extended. The differences are much higher.
To be more precise, consider the W+Trid-OR5W and the gW+Trid-OR5gW ratings (with ?*max-guardians* set to 8 and with all the ORk-consistency and splitting rules active). From my experience with puzzles in T&E(3), this is a good basis for comparison.
The comparison is here restricted to the first 10,000 puzzles in mith's collection of 158,276 min-expands.

Of course, one always has: gW+Trid-OR5gW ≤ W+Trid-OR5W
In reality, the W+Trid-OR5W and gW+Trid-OR5gW ratings are different in 3.69% of the T&E(3) puzzles (instead of 0.22% for W vs gW in cbg-000).
Also, 1.12% of the puzzles that are not solved in W8+OR5W8 get solved in gW8+OR5gW8


Whether this larger difference is totally due to the puzzles being much harder than those in cbg-000 or whether this is somehow specifically related to the presence of the anti-tridagon pattern remains undecided at this point.

For two examples of puzzles with different ratings, see:
- http://forum.enjoysudoku.com/1418-in-158-276-t-e-3-min-expands-t41482.html
- http://forum.enjoysudoku.com/5383-in-158-276-t-e-3-min-expands-t41504.html
The difference can appear with the presence of ordinary g-whips, ORk-gwhips or both.
.
denis_berthier
2010 Supporter
 
Posts: 4238
Joined: 19 June 2007
Location: Paris

Re: The tridagon rule

Postby denis_berthier » Thu Jul 13, 2023 4:00 am

.
SudoRules has finally completed its analysis of mith's collection of 158,276 min-expand puzzles in T&E(3) and of eleven's list of 630 3-digit impossible patterns in two bands (or two stacks).
As expected, the full calculations don't bring results significantly different from those obtained before with the partial lists of puzzles:
- there are four natural selections of Subsets of the 630 patterns (defined by how "useful" they are in solving the puzzles);
- Select1 is unchanged, apart from the last two patterns being permuted (but internal changes are not really relevant);
- there is more internal change in the other 3 subsets (but internal changes are not really relevant);
- 2 patterns are downgraded from Select3 to Select4 (but anyway, no calculations were done with Select3 or Select4);
- 2 new patterns are added to Select4.

The final result is:
Select1 = {EL13c290, EL14c30, EL14c159, EL14c1, EL14c13}
Select2 = Select1 + {EL10c28, EL13c179, EL13c30, EL13c171, EL13c234, EL13c176, EL10c6}
Select3 = Select2 + {EL13c259, EL10c8, EL13c172, EL14c19, EL10c4}
Select4 = Select3 + {EL13c175, EL13c136, EL15c97, EL13c187, EL14c93, EL12c2, EL14c154, EL13c19, EL13c170, EL13c168, EL10c10}
and these are the four subsets of patterns that can be collectively selected in SudoRules.

Remember that "usefulness" of a pattern is defined by the number of puzzles in which it leads to at least one elimination when the rules of (Trid+Imp630)+W8+OR5W8 are activated.
The final "usefulness" numbers are as follows. I give them here to show that the four subsets appear quite naturally.

Code: Select all
Trid = 152446 (in some puzzles, the tridagon pattern doesn't imply any elimination)
Total IMP630-EL<xxx>c<yyy> = 128584 (percentages below are wrt to this number)

Imp630-Select1 (total 86164, 67.01%):
EL13c290 = 29764
EL14c30 = 22989
EL14c159 = 14111
EL14c1 = 10027
EL14c13 = 9240

Imp630-Select2 (total +23789, +18.50% = 85.51%):
EL10c28 = 5486
EL13c179 = 4834
EL13c30 = 3200
EL13c171 = 2768
EL13c234 = 2598
EL13c176 = 2475
EL10c6 = 2428

Imp630-Select3 (total +7427, +5.78% = 91.29):
EL13c259 = 2108
EL10c8 = 1804
EL13c172 = 1462
EL14c19 = 1040
EL10c4 = 1013

Imp630-Select4 (total +5309, +4.13% = 95.42%):
EL13c175 = 726
EL13c136 = 656
EL15c97 = 623
EL13c187 = 581
EL14c93 = 578
EL12c2 = 448
EL14c154 = 396
EL13c19 = 389
EL13c170 = 316
EL13c168 = 307
EL10c10 = 289


SudoRules has been updated to reflect these minor changes (to be published soon).
The User Manual is also being updated and will be published soon. It will contain detailed additional results on the classification of puzzles that allow to draw stronger conclusions than the existence of the above sets of patterns.

As a personal side note:
After the discovery of the tridagon impossible pattern and of Loki by mith (http://forum.enjoysudoku.com/loki-ser-11-9-t39840.html?hilit=Loki)
and following my surprise to find it was in T&E(3) (http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-1048.html),
I've been working on how to define generic resolution rules (ORk-chains) able to use application-specific impossible patterns (applied in particular to T&E(3) puzzles). More specifically, my recent work has been on selecting a small set of impossible patterns from the full set, with almost the same resolution power.
The above results make me feel my approach has reached its goals and I can now switch to other topics.

As a result, I don't plan to propose more T&E(3) puzzles from mith's collection in the "Puzzles" section (those I've proposed illustrate the different cases of interest I've found). However, I plan to publish my detailed classification results on GitHub, together with some explanation of how to use them to find more interesting puzzles. It may take some time to prepare all this.
Alternatively, you can use the "puzzles" section in a new way, to ask questions such as: is there a T&E(3) puzzle such that.... I can probably not answer all such questions, but let's see.
.
denis_berthier
2010 Supporter
 
Posts: 4238
Joined: 19 June 2007
Location: Paris

Re: The tridagon rule

Postby JP_BENTZ » Thu Aug 17, 2023 11:02 am

Hello,
I haven't really been following your work, so I'm at risk of hitting a few open doors, but I'd like to submit to you an empirical solubility test which may be usable for certain specific configurations discussed in 2022.
Let's first define "pseudo-independent" positions (or "PIPs") in a block as positions within this block which do not share any row nor any column. Note : there are 2 different ways of completely dividing a block into 3 sets of 3 PIPs.
Let's now select in a grid ANY set of 3 PIPs in EACH one of ANY 4 blocks at the corners of a square or of a rectangle. And let's consider the path or paths which link(s), one to the other and from each block to the next, those of the 12 selected PIPs (i.e. 4 x 3) which are aligned along the rows and along the columns of these 4 blocks.
RULE (still to be formally demonstrated and possibly extended) : If the TOTAL number of crossings of this path with itself, or of these paths with each other, is odd, then the 4 sets of 3 PIPs cannot contain the same triplet of figures. As a result, if these 12 PIPS contain each the same triplet of candidates, this configuration has no solution as it stands (i.e. without additional information).
Last edited by JP_BENTZ on Fri Aug 18, 2023 10:08 am, edited 1 time in total.
JP_BENTZ
 
Posts: 7
Joined: 16 August 2023

Re: The tridagon rule

Postby denis_berthier » Thu Aug 17, 2023 6:30 pm

Hi Jean Paul
Welcome on this forum
JP_BENTZ wrote:I'd like to submit to you an empirical solubility test which may be usable for certain specific configurations discussed in 2022.
Let's first define "pseudo-independent" positions (or "PIPs") in a block as positions within this block which do not share any row nor any column. Note : there are 2 different ways of completely dividing a block into 3 sets of 3 PIPs.
Let's now select in a grid ANY set of 3 PIPs in EACH one of ANY 4 blocks at the corners of a square or of a rectangle.

If you take this with the contraposition of
JP_BENTZ wrote:the 4 sets of 3 PIPs cannot contain the same triplet of figures

then you get the conditions in my first post (without additional conditions).

Using isomorphisms, there are only two possibilities:
Code: Select all
+-------------------------------+-------------------------------+
! 123       .         .         ! 123       .         .         !
! .         123       .         ! .         123       .         !
! .         .         123       ! .         .         123       !
+-------------------------------+-------------------------------+
! 123       .         .         ! 123       .         .         !
! .         123       .         ! .         123       .         !
! .         .         123       ! .         .         123       !
+-------------------------------+-------------------------------+

and
Code: Select all
+-------------------------------+-------------------------------+
! 123       .         .         ! 123       .         .         !
! .         123       .         ! .         123       .         !
! .         .         123       ! .         .         123       !
+-------------------------------+-------------------------------+
! 123       .         .         ! .         .         123       !
! .         123       .         ! .         123       .         !
! .         .         123       ! 123       .         .         !
+-------------------------------+-------------------------------+


The second case is the trivalue oddagon impossible pattern.
It shouldn't be too difficult to write your path condition from it.
.
denis_berthier
2010 Supporter
 
Posts: 4238
Joined: 19 June 2007
Location: Paris

Re: The tridagon rule

Postby denis_berthier » Mon Oct 16, 2023 2:57 am

.
The degenerate cyclic anti-tridagon pattern

The most general non-degenerate anti-tridagon pattern with guardians has been defined here: http://forum.enjoysudoku.com/the-tridagon-rule-t39859-95.html
Non-degenerate means that each of the 3 candidates is present in each of the 12 cells of the pattern.
Proving the pattern contradictory requires (restricted) T&E(3).
This is a very strong condition, but all the known puzzles in T&E(3) happen to have this pattern.


Two degenerate forms of the anti-tridagon pattern were considered:
- here when a value is decided in one of the 12 cells:
http://forum.enjoysudoku.com/the-tridagon-rule-t39859-106.html
- and here for (the more general case of) 1 missing candidate in one of the 12 cells:
http://forum.enjoysudoku.com/the-tridagon-rule-t39859-106.html
It was shown there that these two cases require only T&E(2) to be proven contradictory.


Definition: the degenerate cyclic anti-tridagon pattern
- the pattern of 12 cells satisfies the same conditions as in the first post of this thread or as here: http://forum.enjoysudoku.com/the-tridagon-rule-t39859-95.html
- the pattern of digits in these cells has relaxed conditions, allowing some of the 123-candidates to be missing, but in a controlled way: in each of the 4 blocks, the 3 cells of the pattern must have the cyclic pattern of 123 digits, i.e. at least the respective following contents, in any order: 12 23 31.


Remarks:
- this defines a restricted form of degeneracy;
- none of the 12 cells of the pattern can be decided;
- from the above theorem, this pattern can be proven contradictory in T&E(2);
- cyclic conditions appear quite naturally in other patterns, such as Triplets or Quads and are used in SudoRules to differentiate non-degenerate Subsets from degenerate ones;
- the pattern of cells and the cyclic conditions make it relatively easy to identify the degenerate cyclic pattern, even with very large numbers of guardians.



******************

One question is, can one find this pattern in old puzzle collections? Moreover, how far back in time can one go and find it?
The question comes naturally when considering the search methods used to find the "hardest" puzzles: vicinity search starts from puzzles with high SER and looks for hopefully harder puzzles in their neighbourhood.


At this point, it is essential to recall that this is how Loki (and similar puzzles) was originally found by mith: as a puzzle with high SER (11.9).
Later, I found that Loki was not in T&E(2) but in T&E(3). Replacing SER by T&E-depth in the search scripts then led to find many more puzzles in T&E(3), but the original way Loki was found was by vicinity search for high SER, starting from puzzles with already high SER (which I proved long ago to be in T&E(2)).
Note also that there has never been any explicit search for the tridagon pattern. It is a fact that it appears in all the T&E(3) puzzles, but it just happens to be so.


As a result, it is natural to think there must have been some precursors of the tridagon pattern in the T&E(2) puzzles that were used as seeds in the vicinity search procedures. And the degenerate cyclic anti-tridagon pattern appears to be a good choice for a possible precursor.

Note that the case of a decided cell may also be a precursor, but I haven't yet investigated it .
.
denis_berthier
2010 Supporter
 
Posts: 4238
Joined: 19 June 2007
Location: Paris

Re: The tridagon rule

Postby denis_berthier » Mon Oct 16, 2023 3:10 am

.
Answers to the questions in the previous post.

The first collection I tried is eleven's "gotchi" collection:
http://forum.enjoysudoku.com/the-making-of-a-gotchi-a-simple-way-to-find-extreme-sudokus-t30150.html,
because it was built in a pattern-independent way and I've analysed it recently in relation to the BpB classification of puzzles in T&E(2):
https://github.com/denis-berthier/Classification-of-TE2-Sudokus
10861 out of 26,370 puzzles (41 %) have a degenerate cyclic anti-tridagon, regardless of their place in the collection (i.e. of their SER).


******************

The second collection I tried is the famous Magictour "top 1465 hardest" collection (unfortunately, I don't have any url to give for it).
There was a time when it contained part of the currently hardest known puzzles. I've shown long ago that all of its puzzles are in T&E(1), except 3 that are in gT&E(1).
By today's standards, it is therefore not an extremely hard collection and one may not necessarily expect to have any precursor of the tridagon pattern in it.
However, it is there:
53 out of the 1465 puzzles (3.6 %) have the degenerate cyclic anti-tridagon pattern, regardless of their place in the collection.


******************

The third collection I tried is my controlled-bias one, which is in the mean still easier than Magictour. The degenerate pattern is there also, though not very frequently.
48 out of 21375 (0.22 %) puzzles have the degenerate cyclic anti-tridagon pattern. This is not much, but this nevertheless proves that one doesn't have to look very long for the pattern before finding it.


******************

Conclusion: degenerate cyclic precursors of the anti-tridagon pattern are everywhere around. This allows to understand why vicinity search can eventually find non-degenerate ones.
Note however that, in most cases, they have very large numbers of guardians, which makes them quite useless for solving puzzles.


[Edit]: needless to say, but: in all of these collections, there's no non-degenerate tridagon.
.
Last edited by denis_berthier on Sun Oct 29, 2023 5:18 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 4238
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to Advanced solving techniques

cron