The tridagon rule

Advanced methods and approaches for solving Sudoku puzzles

The tridagon rule

Postby denis_berthier » Sun Mar 13, 2022 9:09 am

.
THE TRIDAGON ELIMINATION RULE

Some forms of this rule have been known under the names of trivalue-oddagon or Thor's Hammer.
As I can't see anything related to oddagons, neither in the pattern nor in the way the rule can be proven, and "Thor's Hammer" does not sound very serious, I've found this short name, but I'm ready to change it.
For references or some history, see the next post.

Let there be four blocks forming a rectangle in two bands and two stacks:
b11 b12
b21 b22
Let there be three digits (the target digits), say 1 2 3, such that:
- in each of the four blocks, there are three cells in different rows and different columns such that:
--- each of these 4x3 cells contains the three digits,
--- eleven of these cells (the 123-cells) do not contain any other digit,
--- the twelfth cell (the target cell) contains at least one more digit,
- some additional conditions to be found below are satisfied.
Then the 3 target digits can be eliminated from the target cell.


The purpose of this thread is:
- to find the necessary and sufficient additional conditions for the rule to be valid;
- to prove the rule in these conditions;
- to analyse the possibility of missing candidates in the 11 cells;
- to list references to the first mentions of (some versions of) this pattern
- to discuss examples;
...


My first goal here is to find the additional conditions, i.e. all the possible patterns of cells in b22.
I propose here a T&E-ish direct proof, assuming the basic condition that in each block there is only one of the 3 cells per row and per column.
It will be very inelegant, but it will not use any uniqueness argument.

First, notice that in such conditions, it is easy to:
- make permutations of stacks and bands such that the target cell is in block b11
- make permutations of rows in the first band such that the target cell is in row r1
- make permutations of the columns in each of the 2 stacks and then permutation of the rows in the band of b21 and b22, such that we have the following pattern, with the target cell in r1c1 and with the 123-cells of the first 3 blocks in their anti-diagonal.
Code: Select all
+-------------------------------+-------------------------------+
! 123456789 .         .         ! 123       .         .         !
! .         123       .         ! .         123       .         !
! .         .         123       ! .         .         123       !
+-------------------------------+-------------------------------+
! 123       .         .         ! *         *         *         !
! .         123       .         ! *         *         *         !
! .         .         123       ! *         *         *         !
+-------------------------------+-------------------------------+

Blocks not concerned by the pattern are not represented.
456789 means that each of these candidates may be in the cell and at least one must be in it.
. means a cell that does not participate in the pattern or its proof
* means a cell for which we are trying to decide whether it can be part of the pattern
At this point, there is nothing we can say about where the 3 cells of interest in b22 are. We only know that, given the conditions at the start, they can form only 6 non-isomorphic patterns of cells in b22.

Notice that, at this point, we have exhausted all the possibilities of applying isomorphisms.

By symmetry of the conditions wrt 1, 2, 3, we can always assume that r1c1 = 1, which gives:
Code: Select all
+-------------------------------+-------------------------------+
! 1         .         .         ! 23        .         .         !
! .         23        .         ! .         123       .         !
! .         .         23        ! .         .         123       !
+-------------------------------+-------------------------------+
! 23        .         .         ! *         *         *         !
! .         123       .         ! *         *         *         !
! .         .         123       ! *         *         *         !
+-------------------------------+-------------------------------+


Again, by symmetry of this situation wrt digits 2 and 3, we can always assume that r2c2 = 2, which gives:
Code: Select all
+-------------------------------+-------------------------------+
! 1         .         .         ! 23        .         .         !
! .         2         .         ! .         13        .         !
! .         .         3         ! .         .         12        !
+-------------------------------+-------------------------------+
! 23        .         .         ! *         *         *         !
! .         13        .         ! *         *         *         !
! .         .         12        ! *         *         *         !
+-------------------------------+-------------------------------+



At this point, we can have either r4c1 = 2 or r4c1 = 3
First suppose that r4c1 = 2
Code: Select all
+-------------------------------+-------------------------------+
! 1         .         .         ! 23        .         .         !
! .         2         .         ! .         13        .         !
! .         .         3         ! .         .         12        !
+-------------------------------+-------------------------------+
! 2         .         .         ! *         *         *         !
! .         3         .         ! *         *         *         !
! .         .         1         ! *         *         *         !
+-------------------------------+-------------------------------+


We can now have either r1c4 = 2 or r1c4 = 3
if r1c4 = 2
Code: Select all
+-------------------------------+-------------------------------+
! 1         .         .         ! 2         .         .         !
! .         2         .         ! .         3         .         !
! .         .         3         ! .         .         1         !
+-------------------------------+-------------------------------+
! 2         .         .         ! 13*       1*        3*        !
! .         3         .         ! 1*        12*       2*        !
! .         .         1         ! 3*        2*        23*       !
+-------------------------------+-------------------------------+

At this point, we can check how a contradiction could arise in b22, depending on where the 3 cells with no other candidates are placed.
There are 3 cases:
cells 357 in b22 (anti-diagonal): 3 appears twice in b22
cells 249 in b22: 1 appears twice in b22
cells 168 in b22: 2 appears twice in b22

if r1c4 = 3:
Code: Select all
+-------------------------------+-------------------------------+
! 1         .         .         ! 3         .         .         !
! .         2         .         ! .         1         .         !
! .         .         3         ! .         .         2         !
+-------------------------------+-------------------------------+
! 2         .         .         ! 1*        3*        13*       !
! .         3         .         ! 12*       2*        1*        !
! .         .         1         ! 2*        23*       3*        !
+-------------------------------+-------------------------------+

At this point, we can check how a contradiction could arise in b22, depending on where the 3 cells are placed.
There are 3 cases:
cells 357 in b22 (anti-diagonal): 2 appears twice in b22
cells 168 in b22: 1 appears twice in b22
cells 249 in b22: 3 appears twice in b22
Same possibilities as before



At the point where we could have either r4c1 = 2 or r4c1 = 3
suppose r4c1 = 3
Code: Select all
+-------------------------------+-------------------------------+
! 1         .         .         ! 23        .         .         !
! .         2         .         ! .         13        .         !
! .         .         3         ! .         .         12        !
+-------------------------------+-------------------------------+
! 3         .         .         ! *         *         *         !
! .         1         .         ! *         *         *         !
! .         .         2         ! *         *         *         !
+-------------------------------+-------------------------------+

We can now have either r1c4 = 2 or r1c4 = 3

if r1c4 = 2:
Code: Select all
+-------------------------------+-------------------------------+
! 1         .         .         ! 2         .         .         !
! .         2         .         ! .         3         .         !
! .         .         3         ! .         .         1         !
+-------------------------------+-------------------------------+
! 3         .         .         ! 1*        12*       2*        !
! .         1         .         ! 3*        2*        23*       !
! .         .         2         ! 13*       1*        3*        !
+-------------------------------+-------------------------------+

At this point, we can check how a contradiction could arise in b22, depending on where the 3 cells are placed.
There are 3 cases:
cells 357 in b22 (anti-diagonal): 2 appears twice in b22
cells 168 in b22: 1 appears twice in b22
cells 249 in b22: 3 appears twice in b22
Same possibilities as before

if r1c4 = 3:
Code: Select all
+-------------------------------+-------------------------------+
! 1         .         .         ! 3         .         .         !
! .         2         .         ! .         1         .         !
! .         .         3         ! .         .         2         !
+-------------------------------+-------------------------------+
! 3         .         .         ! 12*       2*        1*        !
! .         1         .         ! 2*        23*       3*        !
! .         .         2         ! 1*        3*        13*       !
+-------------------------------+-------------------------------+

At this point, we can check how a contradiction could arise in b22, depending on where the 3 cells are placed.
There are 3 cases:
cells 357 in b22 (anti-diagonal): 1 appears twice in b22
cells 249 in b22: 2 appears twice in b22
cells 168 in b22: 3 appears twice in b22
Same possibilities as before


Conclusion: when the patterns of cells in the first 3 blocks are fixed as at the start (anti-diagonal, with the target cell in r1c1), there are three and only three possible patterns of 123-cells for the fourth block that make the rule valid:

Code: Select all
+-------+
! . . * !
! . * . !
! * . . !
+-------+

+-------+
! . * . !
! * . . !
! . . * !
+-------+

+-------+
! * . . !
! . . * !
! . * . !
+-------+


Notice that, when cell r1c1 is fixed, the first two are non-isomorphic, but the last two are isomorphic, via r2->r3, c2->c3, r5->r6, c5->c6.

This is half of the possible patterns satisfying the conditions at the start.
.
[edit]: for non ambiguity, explicitly repeated the condition on target cell being in r1c1 in the conclusion.
[Edit 2]: take into account 999_spring remark.
[Edit3]: For an edited version of the contents of this thread, see Part III if the "Augmented User Manual for CSP-Rules-V2.1" ([AUM] , available on ResearchGate: https://www.researchgate.net/publication/365186265_Augmented_User_Manual_for_CSP-Rules-V21),
also available as part of CSP-Rules (https://github.com/denis-berthier/CSP-Rules-V2.1).
Last edited by denis_berthier on Fri May 12, 2023 4:21 am, edited 4 times in total.
denis_berthier
2010 Supporter
 
Posts: 3958
Joined: 19 June 2007
Location: Paris

Re: The tridagon rule

Postby denis_berthier » Sun Mar 13, 2022 9:10 am

.
References

This is just a quick sketch. Don't hesitate to propose more references.

- following a series of new hard puzzles by mith, 1st mention of a new impossible pattern: http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-810.html
- 1st mention of the name "trivalue oddagon" on this forum: http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-811.html

- eleven's first expianation of the pattern: http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-816.html
- eleven's proof of the pattern: http://forum.enjoysudoku.com/post318379.html#p318379
- Coloin's identification of 6 cases: http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-817.html

- Mith's first 11.9 "Loki", the 10th known puzzle with SER = 11.9: http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-1030.html
- Loki shown to be the 1st ever puzzle not in T&E(2): http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-1048.html
- see also all the posts following the previous two and the discussion about "trivalue oddagons"

- Resolutions of Loki: http://forum.enjoysudoku.com/loki-ser-11-9-t39840.html

- videos of the pattern (by rangsk, developing ryokousha’s parity argument): https://www.youtube.com/_xMtwqTTK6o, https://youtu.be/V7RC1hJ8vZ8

- My interpretation of the pattern for easy coding as a resolution rule: http://forum.enjoysudoku.com/the-tridagon-rule-t39859.html
.

[Edit: added references provided by mith]
Last edited by denis_berthier on Fri Aug 11, 2023 7:01 am, edited 5 times in total.
denis_berthier
2010 Supporter
 
Posts: 3958
Joined: 19 June 2007
Location: Paris

Re: The tridagon rule

Postby denis_berthier » Sun Mar 13, 2022 11:32 am

.
Example: Loki

After my first post, I decided to code this rule in SudoRules. Here is my first try with it. Note that, as tridagons rely on 12 CSP-variables (the 12 rc-cells), they are assigned complexity 12. That's why one appears only after a whip[9] in the following path.

Loki (created by mith) was the first puzzle I found not to be in T&E(2). This (indirectly) made me interested in tridagons. Here is Loki's solution, with this rule blended with whips.
Code: Select all
Resolution state after Singles and whips[1]:
   +----------------------+----------------------+----------------------+
   ! 5      7      3468   ! 238    346    13     ! 9      123    136    !
   ! 23469  2349   3469   ! 2357   34567  13579  ! 3457   12357  8      !
   ! 234689 1      34689  ! 23578  34567  3579   ! 3457   2357   3567   !
   +----------------------+----------------------+----------------------+
   ! 379    359    1      ! 6      8      357    ! 357    4      2      !
   ! 3467   345    34567  ! 1      357    2      ! 8      357    9      !
   ! 378    358    2      ! 357    9      4      ! 1      6      357    !
   +----------------------+----------------------+----------------------+
   ! 134789 34589  345789 ! 357    2      6      ! 357    135789 1357   !
   ! 137    6      357    ! 9      357    8      ! 2      1357   4      !
   ! 23789  23589  35789  ! 4      1      357    ! 6      35789  357    !
   +----------------------+----------------------+----------------------+
205 candidates.

hidden-pairs-in-a-column: c8{n8 n9}{r7 r9} ==> r9c8≠7, r9c8≠5, r9c8≠3, r7c8≠7, r7c8≠5, r7c8≠3, r7c8≠1
whip[9]: b9n1{r7c9 r8c8} - b3n1{r2c8 r1c9} - r1c6{n1 n3} - c4n3{r3 r6} - c5n3{r5 r8} - r8c1{n3 n7} - r6n7{c1 c9} - r9n7{c9 c6} - r4n7{c6 .} ==> r7c9≠3
tridagon in blocks b9, b8, b6 and b5 for digits 3, 5 and 7 ==> r8c8≠3,5,7
singles ==> r8c8=1, r1c9=1, r1c6=3, r1c8=2, r1c4=8, r2c6=1, r3c6=9, r3c9=6, r7c1=1
finned-x-wing-in-columns: n3{c4 c9}{r6 r7} ==> r7c7≠3
hidden-single-in-a-block ==> r9c9=3
whip[1]: b9n5{r7c9 .} ==> r7c2≠5, r7c3≠5, r7c4≠5
whip[1]: b9n7{r7c9 .} ==> r7c3≠7, r7c4≠7
singles ==> r7c4=3, r5c5=3, r4c7=3
naked-pairs-in-a-row: r6{c4 c9}{n5 n7} ==> r6c2≠5, r6c1≠7
finned-x-wing-in-rows: n7{r4 r9}{c6 c1} ==> r8c1≠7
singles ==> r8c1=3, r6c1=8, r6c2=3, r3c3=8, r2c3=3, r3c8=3
whip[1]: c3n9{r9 .} ==> r7c2≠9, r9c1≠9, r9c2≠9
biv-chain[2]: r6n7{c4 c9} - c8n7{r5 r2} ==> r2c4≠7
biv-chain[2]: r6n5{c4 c9} - c8n5{r5 r2} ==> r2c4≠5
stte
denis_berthier
2010 Supporter
 
Posts: 3958
Joined: 19 June 2007
Location: Paris

Re: The tridagon rule

Postby denis_berthier » Sun Mar 13, 2022 11:47 am

.
Example 2:

denis_berthier wrote:
mith wrote:
Code: Select all
. . . . . . . . 1
. . . . . 2 . . .
. . . . 3 . . 4 5
. . 6 . . . . . .
. 7 1 . 8 . . . .
3 2 . . 6 7 . . 8
. 6 . . 2 3 . . .
. 8 3 7 . . 1 . .
7 . 2 8 1 . 6 . .

This should be the 26c minimal, if I haven’t made a typo. The other is 27c.

This is a new puzzle not in T&E(2).
Like Loki, its is not in gT&E(2) either; but it is in T&E(W2, 2).


Code: Select all
Resolution state after Singles and whips[1]:
   +----------------------+----------------------+----------------------+
   ! 24569  3459   45789  ! 4569   4579   4589   ! 23789  236789 1      !
   ! 4569   13459  45789  ! 14569  4579   2      ! 3789   36789  3679   !
   ! 269    19     789    ! 169    3      189    ! 2789   4      5      !
   +----------------------+----------------------+----------------------+
   ! 8      459    6      ! 123459 459    1459   ! 234579 123579 23479  !
   ! 459    7      1      ! 23459  8      459    ! 23459  23569  23469  !
   ! 3      2      459    ! 1459   6      7      ! 459    159    8      !
   +----------------------+----------------------+----------------------+
   ! 1      6      459    ! 459    2      3      ! 45789  5789   479    !
   ! 459    8      3      ! 7      459    6      ! 1      259    249    !
   ! 7      459    2      ! 8      1      459    ! 6      359    349    !
   +----------------------+----------------------+----------------------+
205 candidates.


hidden-pairs-in-a-column: c4{n2 n3}{r4 r5} ==> r5c4≠9, r5c4≠5, r5c4≠4, r4c4≠9, r4c4≠5, r4c4≠4, r4c4≠1
tridagon for digits 4, 5 and 9 in blocks:
----- b5, cells: r6c4 (target cell), r5c6, r4c5
----- b4, cells: r6c3, r5c1, r4c2
----- b8, cells: r7c4, r9c6, r8c5
----- b7, cells: r7c3, r9c2, r8c1
==> r6c4≠4,5,9

singles ==> r6c4=1, r3c6=1, r3c2=9, r3c4=6, r3c1=2, r2c2=1, r1c2=3, r1c6=8, r4c8=1
finned-x-wing-in-columns: n4{c2 c6}{r9 r4} ==> r4c5≠4
whip[1]: b5n4{r5c6 .} ==> r9c6≠4
finned-x-wing-in-columns: n5{c2 c6}{r9 r4} ==> r4c5≠5
singles ==> r4c5=9, r9c6=9
naked-pairs-in-a-row: r4{c2 c6}{n4 n5} ==> r4c9≠4, r4c7≠5, r4c7≠4
biv-chain[3]: c3n9{r7 r6} - r6c8{n9 n5} - r9n5{c8 c2} ==> r7c3≠5
biv-chain[3]: r8c5{n4 n5} - b7n5{r8c1 r9c2} - r9n4{c2 c9} ==> r8c9≠4
biv-chain[3]: c1n9{r5 r8} - b7n5{r8c1 r9c2} - c2n4{r9 r4} ==> r5c1≠4
z-chain[3]: r8c9{n9 n2} - r8c8{n2 n5} - r6c8{n5 .} ==> r7c8≠9
z-chain[3]: c8n7{r2 r7} - c8n8{r7 r2} - r3c7{n8 .} ==> r1c7≠7, r2c9≠7, r2c7≠7
t-whip[3]: c3n9{r7 r6} - r6c8{n9 n5} - b9n5{r7c8 .} ==> r7c7≠9
finned-x-wing-in-rows: n9{r7 r6}{c3 c9} ==> r5c9≠9
t-whip[3]: c8n8{r7 r2} - r3c7{n8 n7} - c8n7{r1 .} ==> r7c8≠5
t-whip[3]: r3c7{n8 n7} - c8n7{r2 r7} - r7n8{c8 .} ==> r2c7≠8
biv-chain[4]: r6c8{n9 n5} - r9n5{c8 c2} - r4c2{n5 n4} - r6n4{c3 c7} ==> r6c7≠9
finned-x-wing-in-rows: n9{r6 r7}{c3 c8} ==> r8c8≠9
whip[1]: b9n9{r8c9 .} ==> r2c9≠9
biv-chain[3]: r9n3{c8 c9} - r2c9{n3 n6} - b6n6{r5c9 r5c8} ==> r5c8≠3
biv-chain[4]: r6c8{n5 n9} - c3n9{r6 r7} - c9n9{r7 r8} - b9n2{r8c9 r8c8} ==> r8c8≠5
singles ==> r8c8=2, r8c9=9, r7c3=9, r5c1=9, r6c8=9, r1c7=2, r2c7=9, r1c4=9
whip[1]: c7n3{r5 .} ==> r4c9≠3, r5c9≠3
finned-x-wing-in-rows: n4{r8 r1}{c5 c1} ==> r2c1≠4
finned-x-wing-in-rows: n5{r8 r1}{c5 c1} ==> r2c1≠5
stte


Notice that, while Loki followed the first of the 3 patterns at the end of the first post, this puzzle follows the third (after isomorphisms that put them in the proper forms).

[Edit]: added cell information to the printed form of the pattern.
The information displayed follows the conventions and order of the first post.
denis_berthier
2010 Supporter
 
Posts: 3958
Joined: 19 June 2007
Location: Paris

Re: The tridagon rule

Postby eleven » Mon Mar 14, 2022 12:37 pm

Haven't seen this post yesterday, so i posted my proof to the hardest thread.
It shows, that whenever you have a single rectangle in such a pattern (3 cells in 4 boxes of 2 bands/stacks, where in each box there is a single cell in minirow/column), it cannot be solved with 3 digits.
The 3 cases above in fact are equivalent (isomorph).
It also can be proven, that for each possible placement of one digit you are left with a bivalue oddagon for the other digits (but i needed to distinguish 7 cases for that), so in my eyes the name oddagon is justified.
Note that the one rectangle observation has been mentioned by Marek Stefanik already in July last year.
eleven
 
Posts: 3067
Joined: 10 February 2008

Re: The tridagon rule

Postby denis_berthier » Mon Mar 14, 2022 12:46 pm

eleven wrote:Haven't seen this post yesterday, so i posted my proof to the hardest thread.
It shows, that whenever you have a single rectangle in such a pattern (3 cells in 4 boxes of 2 bands/stacks, where in each box there is a single cell in minirow/column), it cannot be solved with 3 digits.

OK, I've added it to the (currently short) list of references.

eleven wrote:The 3 cases above in fact are equivalent (isomorph).

How do you change the 4th block without touching the first 3 (in particular, keeping the target cell in r1c1)?
denis_berthier
2010 Supporter
 
Posts: 3958
Joined: 19 June 2007
Location: Paris

Re: The tridagon rule

Postby eleven » Mon Mar 14, 2022 3:56 pm

Ah, i see. I don't need a target cell, it suffices to know, that the 3-digit pattern isn't possible, so at least one of the extra candidates must be true.
If e.g. there was an extra candidate in 2 of the cells, the pattern would provide a strong link between them.
eleven
 
Posts: 3067
Joined: 10 February 2008

Re: The tridagon rule

Postby 999_Springs » Mon Mar 14, 2022 4:02 pm

i think there is no need to specifically distinguish a "target cell" in your definition of the pattern.

the underlying logic behind the pattern is that if we limit the cells marked x to digits 1,2,3 only, then there is no solution:
Code: Select all
+-------+-------+
| x . . | x . . |
| . x . | . x . |
| . . x | . . x |
+-------+-------+
| x . . | . . x |
| . x . | . x . |
| . . x | x . . |
+-------+-------+

as a corollary of this, if we have any number of these cells containing any number of extra digits, then we know that at least one of the extra digits in any cell marked x must be true.

since the pattern of x's in cells is isomorphic, by rearranging rows and columns, to the other two cases of trivalue oddagons with the x's in b5 in p168 and p249, then when proving that there is no solution, we can use this isomorphism to immediately get that the same pattern with the x's elsewhere in b5 also has no solution, thus, at least one of any additional candidates in the x cells must be true. this avoids the need to distinguish a target cell, and with it, the need to distinguish between the 3 cases that you did.

your definition only allows for the specific case where one extra cell has additional candidates. thus, according to your definition, this pattern is not a trivalue oddagon, and would not be found by your solver as such:

mith's 37-clue 11.5
........1....12.3..13.45....34...16.1.74.63.886..31..4.81.6...33.61.48.747....61.
Code: Select all
...|...|..1
...|.12|.3.
.13|.45|...
---+---+---
x34|...|16x
1x7|4.6|3x8
86x|.31|x.4
---+---+---
x81|.6.|x.3
3x6|1.4|8x7
47x|...|61x

the cells marked x form the trivalue oddagon pattern in digits 259, but we have 2 cells with extra candidates: extra 7 in r6c7 and extra 4 in r7c7.

that means that at least one of 7r6c7 and 4r7c7 is true. whichever one of these is true will form a hidden pair with 8 in r13c8
=> r1c8 =/= 259, r3c8 =/= 29

i am guessing that, in your proof, if you did a case analysis for N>1 target cells, it would be far more complicated.

i think that by far the easiest way to view this pattern is as a "deadly pattern", like a BUG or UR/UL, without the uniqueness assumption: the logic is the same otherwise; if we have a BUG or UR with any number of additional candidates in any number of cells, at least one of those additional candidates must be true. limiting it to only one cell with additional candidates is like only considering BUG type 1's and UR type 1's, when there are other types available (e.g. BUG type 2 is the case where N>1 cells have one extra candidate, all of the same digit). but there is no need to do specific patterns for each type if you don't want to: in general, the derived inference you get from the additional candidates in such a deadly pattern can be used in a chain, just like any other inferences can - and it is only for convenience that we assign type numbers (1 to 6?) to the simplest versions of such chains for patterns easily recognisable to a human eye (the above example would be a "type 3 with hidden pair" using uniqueness pattern terminology)

edit: i notice that eleven wrote the above post at the same time as i did, and we make the same point

edit edit: even if you insist on a target cell in r1c1, you can still swap r23,c23,r56,c56 to get the case with the x's in b5p249, giving you only 2 cases to consider (target cell is either in the rectangle or it isn't) instead of 3
999_Springs
 
Posts: 591
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Re: The tridagon rule

Postby denis_berthier » Mon Mar 14, 2022 4:41 pm

.
Hi eleven, 999_spring

I understand you're interested in the contradictory situation. I'm more interested in expressing the resulting elimination rule. I see no contradiction in our approaches.
The target cell is where there is a difference and where changes happen during resolution, so it seems to me it's much more natural to specify it in the definition of the resolution rule.
eleven, you are right that I don't deal with the case of several cells with an additional candidates but, as you write, they could only provide "strong links", i.e. no independent resolution rule. I can hardly imagine using such links (resulting from a very complex and extremely rare pattern) as parts of other patterns. In any case, this is not what I am dealing with here.

Secondarily, from a programming POV in the CLIPS implementation of SudoRules, the pattern-matcher automatically takes all the isomorphisms into account. It's simpler to code the target cell as variable r1c1 instead of having to choose at the end which variable ricj among the 12 ones will be concerned by the eliminations. It took me only 2 hours to code my version of the rule.
denis_berthier
2010 Supporter
 
Posts: 3958
Joined: 19 June 2007
Location: Paris

Re: The tridagon rule

Postby mith » Mon Mar 14, 2022 10:22 pm

I was going to post this as an example of a non-direct deduction from the deadly pattern; it's not too different from what 999_Springs posted, but anyway:

Code: Select all
........1.......2.....13.45...3.56...371.....6.5.78....6.73...8.785.1...3.1.86.5.  ED=11.8/1.2/1.2


Here, rather than two cells contained in a column which have extra digits, the two cells are confined to the same box (trivalue oddagon on 249, with 8r5c1 and 1r6c2 as guardians). This time, the result is that at exactly one of 18 is in r4c12, with the other in r4c8 (so -79r4c8, and 7 is in r4c9, reducing the puzzle to a ~9.2).

It's perfectly reasonable to use the basic elimination (one cell as guardian, eliminate the three values from that cell) as a starting point, but I think it's going to miss more puzzles than you are expecting. At some point I'm intending to code up a search on the database to get an idea of exactly how frequent the basic elimination is vs. a two-or-more guardian case. (It's somewhat interesting that the puzzles to defeat T&E(2) so far only have one guardian, but too small a sample size at this point to say that trend will continue.) This is to say nothing of the remote triples that are inherent in the trivalue structure, which can themselves be used as part of other patterns. Whether something like that is worth including in SudoRules is of course an entirely separate question, which I have very little opinion on.

Also, tridagon just seems to be an abbreviation of trivalue oddagon? I'm not sure I understand any other reason for this name.
mith
 
Posts: 950
Joined: 14 July 2020

Re: The tridagon rule

Postby denis_berthier » Tue Mar 15, 2022 2:43 am

999_Springs wrote:edit edit: even if you insist on a target cell in r1c1, you can still swap r23,c23,r56,c56 to get the case with the x's in b5p249, giving you only 2 cases to consider (target cell is either in the rectangle or it isn't) instead of 3

Just seen your second edit. I'm going to modify my first post.
denis_berthier
2010 Supporter
 
Posts: 3958
Joined: 19 June 2007
Location: Paris

Re: The tridagon rule

Postby denis_berthier » Tue Mar 15, 2022 2:58 am

Hi mith
All this is a work in progress. As of now, I've taken into account only direct eliminations. If other rules appear, I'll see what I do.

mith wrote: tridagon just seems to be an abbreviation of trivalue oddagon? I'm not sure I understand any other reason for this name.

Yes, tridagon is an abbreviation of "trivalue oddagon". I don't like "trivalue oddagon": it's too long and there's no oddagon anywhere in the resolution rule, unless you do some T&E. But I didn't want to forget completely this initial name. That said, I'm not particularly attached to tridagon.
denis_berthier
2010 Supporter
 
Posts: 3958
Joined: 19 June 2007
Location: Paris

Re: The tridagon rule

Postby denis_berthier » Tue Mar 15, 2022 6:35 am

.
In the first post of this thread, I found that, starting from the following pattern of cells in the 4 blocks

Code: Select all
# . . | + . .
. + . | . + .
. . + | . . +
-------------
+ . . | x x x
. + . | x x x
. . + | x x x
where
# means fixed target cell,
+ means fixed 123-cell,
x means 123-cell to be determined

there were only 3 patterns of 123-cells for block b22 that allowed the elimination of the target:
Code: Select all
. . +          . + .          + . .
. + .          + . .          . . +
+ . .          . . +          . + .

Under the above conditions, the first and second pattern are not equivalent but 999_spring noticed that the 2nd and 3rd are equivalent.

The 1st pattern is easy to remember: 3 anti-diagonal blocks (with target cell the first cell of the first of these blocks) + a diagonal one (b22). I shall call this pattern the antidiagonal type:
Code: Select all
# . . | + . .
. + . | . + .
. . + | . . +
-------------
+ . . | . . +
. + . | . + .
. . + | + . .


The 2nd (or 3rd) pattern is harder to describe. So, I looked for an equivalent form. Here is one, called the diagonal type:
Code: Select all
# . . | . . +
. + . | . + .
. . + | + . .
-------------
. . + | . . +
. + . | . + .
+ . . | + . .
Same as first pattern, except that the 123-cells in blocks b12 and b21 are now on the diagonals instead of the anti-diagonals

Proving the equivalence is obvious; I leave it to the reader as an exercise.
Last edited by denis_berthier on Wed Mar 16, 2022 8:07 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 3958
Joined: 19 June 2007
Location: Paris

Re: The tridagon rule

Postby xzccs » Tue Mar 15, 2022 9:20 am

Hi everyone,

I abstracted some conditions from the dead pattern which I think is the essence of it. Also I came up with a proof base on these conditions. (availble for n boxes case)
Image
Conditions:
1. There are n triples in n boxes.
2. Only two cells in each row or column.
3. Only connecting cells by weak links in rows and columns, it can be divided to a loop of length n and a loop of length 2n. (n is not necessary to be even, although odd case may not appear in strandard sudoku)

Prove:
Image
Abstracting as above, in the 2n-loop, it can be divided into n pairs within each block. All pairs are connected with parallel weak link, except for one cross weak link. (Actually any odd number of cross link is OK because it can be twisted into the one case like a rope loop). All the digital permutation (ordered) of the pairs can be divided in to two group: A and B.

Then we can get the inference as follow:
1. In the n-loop, It can’t be the same digit in adjacent position.
2. In the 2n-loop, It can’t be the same digital combination (unordered) in adjacent position. (derived from 1)
3. In the 2n-loop, within the two groups, pairs can be adjacent in parallel link but not in cross link, while between the two group, pairs can be adjacent in cross link but not in parallel link. (derived from 2)
4. All pairs are connected by at least one parallel link, so they can be only group A or group B respectively. However, there is still a cross link, which means there must be a group-A-pair and a group-B-pair. Contradict.

An interesting thing is that the condition 3 can be transform to “There are odd number of intersections of these links”, although I think it’s not so convenient as condition 3 unless we draw the links. Also note that condition 3 is a possible way to prove this pattern, it doesn’t mean it is the only way or the best way to observe.
xzccs
 
Posts: 25
Joined: 02 January 2022
Location: Fiji

Re: The tridagon rule

Postby eleven » Tue Mar 15, 2022 7:51 pm

Sorry, i don't understand. Maybe it's getting clearer, when you post the images.
eleven
 
Posts: 3067
Joined: 10 February 2008

Next

Return to Advanced solving techniques