## The tridagon rule

Advanced methods and approaches for solving Sudoku puzzles

### Re: The tridagon rule

.
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.

denis_berthier
2010 Supporter

Posts: 3856
Joined: 19 June 2007
Location: Paris

### Re: The tridagon rule

.
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***********************************************************************************************100100000010010000001001000100001000010010000001100000000000000000000000000000000Simulated elimination of 311Simulated elimination of 211naked-single ==> r1c1=1Resolution 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 remainingGENERATING 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 remainingGENERATING CONTEXT 2 AT DEPTH 2, SON OF CONTEXT 1, FROM HYPOTHESIS n2r2c2.naked-single ==> r3c3=3naked-single ==> r3c6=1naked-single ==> r2c5=3naked-single ==> r4c6=2naked-single ==> r4c1=3naked-single ==> r5c2=1NO 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=3naked-single ==> r3c3=2naked-single ==> r6c3=1naked-single ==> r5c2=2naked-single ==> r5c5=1NO 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 remainingGENERATING CONTEXT 4 AT DEPTH 2, SON OF CONTEXT 3, FROM HYPOTHESIS n2r2c2.naked-single ==> r3c3=3naked-single ==> r6c3=1naked-single ==> r5c2=3naked-single ==> r4c1=2naked-single ==> r5c5=1NO 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=3naked-single ==> r3c3=2naked-single ==> r3c6=1naked-single ==> r4c6=3naked-single ==> r5c5=1naked-single ==> r5c2=2NO 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=1GENERATING CONTEXT 5 AT DEPTH 1, SON OF CONTEXT 0, FROM HYPOTHESIS n3r6c3.naked-single ==> r3c3=2naked-single ==> r2c2=3naked-single ==> r4c1=2naked-single ==> r5c2=1naked-single ==> r4c6=3naked-single ==> r5c5=2naked-single ==> r2c5=1NO 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=2naked-single ==> r3c3=3naked-single ==> r2c2=2naked-single ==> r4c1=3naked-single ==> r4c6=2naked-single ==> r3c6=1naked-single ==> r2c5=3PUZZLE 0 HAS NO SOLUTION : NO CANDIDATE FOR RC-CELL r5c5MOST COMPLEX RULE TRIED = NSPuzzle 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: 3856
Joined: 19 June 2007
Location: Paris

### Re: The tridagon rule

.
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***********************************************************************************************100100000010010000001001000100001000010010000001100000000000000000000000000000000Simulated elimination of 311Resolution 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 remainingGENERATING 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 remainingGENERATING CONTEXT 2 AT DEPTH 2, SON OF CONTEXT 1, FROM HYPOTHESIS n1r1c1.naked-single ==> r1c4=2NO 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=1NO 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=2NO 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=1NO 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=2naked-single ==> r1c4=1naked-single ==> r3c3=3naked-single ==> r3c6=2naked-single ==> r2c5=3naked-single ==> r4c6=1naked-single ==> r4c1=3naked-single ==> r5c2=2NO 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=1naked-single ==> r1c4=2naked-single ==> r3c3=3naked-single ==> r3c6=1naked-single ==> r2c5=3naked-single ==> r4c6=2naked-single ==> r4c1=3naked-single ==> r5c2=1NO 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=3GENERATING CONTEXT 8 AT DEPTH 2, SON OF CONTEXT 1, FROM HYPOTHESIS n1r2c5.naked-single ==> r5c5=2naked-single ==> r4c6=1naked-single ==> r5c2=1naked-single ==> r6c3=2naked-single ==> r3c3=1naked-single ==> r1c1=2NO 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=2naked-single ==> r5c5=1naked-single ==> r5c2=2naked-single ==> r6c3=1naked-single ==> r4c1=3naked-single ==> r3c3=2naked-single ==> r1c1=1NO 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 remainingGENERATING CONTEXT 10 AT DEPTH 2, SON OF CONTEXT 9, FROM HYPOTHESIS n1r1c1.naked-single ==> r1c4=3NO 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=2NO 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=2naked-single ==> r3c3=3naked-single ==> r6c3=1naked-single ==> r4c1=3naked-single ==> r4c6=1naked-single ==> r3c6=2naked-single ==> r2c5=3NO 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=1naked-single ==> r1c4=3naked-single ==> r2c5=1naked-single ==> r3c6=2naked-single ==> r5c5=3naked-single ==> r4c6=1naked-single ==> r5c2=1naked-single ==> r6c3=3NO 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=3GENERATING CONTEXT 16 AT DEPTH 2, SON OF CONTEXT 9, FROM HYPOTHESIS n1r2c5.naked-single ==> r5c5=3naked-single ==> r4c6=1naked-single ==> r1c4=3naked-single ==> r3c6=2naked-single ==> r3c3=1naked-single ==> r1c1=2naked-single ==> r4c1=3NO 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=2GENERATING CONTEXT 17 AT DEPTH 2, SON OF CONTEXT 9, FROM HYPOTHESIS n1r3c3.naked-single ==> r6c3=3naked-single ==> r3c6=3naked-single ==> r1c4=1naked-single ==> r4c6=1naked-single ==> r4c1=2NO 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=2naked-single ==> r1c1=1naked-single ==> r1c4=3naked-single ==> r3c6=1naked-single ==> r4c6=3naked-single ==> r5c5=1naked-single ==> r5c2=2NO 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=1GENERATING 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 remainingGENERATING CONTEXT 19 AT DEPTH 2, SON OF CONTEXT 18, FROM HYPOTHESIS n1r1c1.naked-single ==> r4c1=2naked-single ==> r4c6=3naked-single ==> r5c5=2naked-single ==> r5c2=1naked-single ==> r3c3=2naked-single ==> r2c2=3naked-single ==> r2c5=1NO 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=2naked-single ==> r4c1=1naked-single ==> r5c2=2naked-single ==> r5c5=3naked-single ==> r4c6=2naked-single ==> r3c3=1naked-single ==> r3c6=3NO 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=2GENERATING CONTEXT 20 AT DEPTH 1, SON OF CONTEXT 0, FROM HYPOTHESIS n3r5c5.naked-single ==> r4c6=2naked-single ==> r5c2=1naked-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 remainingGENERATING CONTEXT 21 AT DEPTH 2, SON OF CONTEXT 20, FROM HYPOTHESIS n1r1c1.naked-single ==> r3c3=3naked-single ==> r2c2=2naked-single ==> r2c5=1NO 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=2naked-single ==> r2c2=3naked-single ==> r3c3=1naked-single ==> r3c6=3NO 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=2naked-single ==> r4c6=3naked-single ==> r4c1=1naked-single ==> r1c1=2naked-single ==> r1c4=3naked-single ==> r2c5=1naked-single ==> r2c2=3PUZZLE 0 HAS NO SOLUTION : NO CANDIDATE FOR RC-CELL r5c2MOST COMPLEX RULE TRIED = NSPuzzle 100100000010010000001001000100001000010010000001100000000000000000000000000000000 :init-time = 0.0s, solve-time = 0.25s, total-time = 0.25ss`

.
Last edited by denis_berthier on Wed Sep 28, 2022 3:23 am, edited 1 time in total.
denis_berthier
2010 Supporter

Posts: 3856
Joined: 19 June 2007
Location: Paris

### Re: The tridagon rule

.
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: 3856
Joined: 19 June 2007
Location: Paris

### Re: The tridagon rule

.
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:
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: 3856
Joined: 19 June 2007
Location: Paris

### Re: The tridagon rule

.
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.

denis_berthier
2010 Supporter

Posts: 3856
Joined: 19 June 2007
Location: Paris

### Re: The tridagon rule

.
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.

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 = 1171Select1 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: 3856
Joined: 19 June 2007
Location: Paris

### Re: The tridagon rule

.
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       restTrid      0   0   32.54   48.46   61.75   69.64   74.19   78.35   21.65Select1   0   0   38.29   58.74   74.43   83.12   87.80   91.15   8.85Select2   0   0   39.46   60.53   76.08   84.46   88.83   91.95   8.05Imp630    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: 3856
Joined: 19 June 2007
Location: Paris

### Re: The tridagon rule

.
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.07100,000   0   0   30.49   15.00   13.01   7.98   4.85   4.23   24.44120,000   0   0   30.89   14.95   12.99   7.98   4.82   4.20   24.17140,000   0   0   31.41   14.71   12.75   7.84   4.86   4.21   24.22158,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: 3856
Joined: 19 June 2007
Location: Paris

### Re: The tridagon rule

.
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: 3856
Joined: 19 June 2007
Location: Paris

### Re: The tridagon rule

.
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 = 9240Imp630-Select2 (total +23789, +18.50% = 85.51%):EL10c28 = 5486 EL13c179 = 4834 EL13c30 = 3200 EL13c171 = 2768 EL13c234 = 2598 EL13c176 = 2475EL10c6 = 2428Imp630-Select3 (total +7427, +5.78% = 91.29):EL13c259 = 2108 EL10c8 = 1804 EL13c172 = 1462 EL14c19 = 1040 EL10c4 = 1013Imp630-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: 3856
Joined: 19 June 2007
Location: Paris

### Re: The tridagon rule

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

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: 3856
Joined: 19 June 2007
Location: Paris

Previous