Denis, I agree that we are not always speaking about the same things. No worries there.
When I say pattern, I am not using it in the sense that you are - just in a more colloquial sense of "something to be recognized and used". It would be more precise to say I'm talking about graphs, specifically those with the rc-cells as vertices. For my part, I am not so much concerned with the language of CSP or patterns as you've defined them; I'm concerned with human-findable logic.
I understand that an OR relationship doesn't make a CSP-Variable... it does often make for a useful logical deduction, however. I don't currently have enough knowledge of CSP in general or CSP-Rules specifically to suggest a way to turn something like that into a pattern. I think we had the same issue initially with the replacement/relabel thing, where one can often use the logic of "whatever digit is in r2c3 is also in r3c9, and then..." rather than literally placing digits into cells. The CSP-Variables don't really support this kind of equivalence logic, at least directly... instead, the replacement is mapping from one domain (digits 1-9) to a different domain (the values in the cells of whatever house you're replacing into, whatever those happen to be) and then back. I don't see an analogue in the case of a "guardian OR", though.
The tridagon rule
Re: The tridagon rule
by denis_berthier » Thu Jul 14, 2022 5:36 am
.
The question is not human vs machine (generally a sign of having no rational argument when used in a discussion), but well-defined vs undefined. It's at a logic/abstract level where the difference between brains and CPUs is totally irrelevant.
Mith, I understand your purpose is not to develop/use a formal version of any concept, but that's the best way to keep turning into circles.
Solving a puzzle with a pseudo-TO with 11 extra candidates by an ad hoc piece of reasoning is one thing (and I admit it may be fun for some); defining precise patterns and general rules that can do this on their own (with no one having to manually fill in logical gaps) is a totally different thing - and that's the thing I'm interested in. Of course, my approach is much more constrained and it will probably not take into account all the ad hoc possibilities. As I said before, this is exactly the same situation as with the precisely defined pattern of J-Exocets vs the largely undefined notion of an Exocet.
Note that I'm not saying that imprecise definitions don't have to play a role at the start of a study. Studying informal Exocets may lead to variants of J-Exocets. Similarly, studying cases of pseudo-TO that don't fit into the Tridagon rule or the Tridagon-Forcing-Whips (and it seems there are many of them) may lead to variants of them or to new rules.
The basic resolution rules I've developed (whips, braids, g-whips, g-braids and all the special cases of them I've selected as worth considering) all share a property: they have no OR branching. This is absolutely essential in terms of complexity (be it for a human or a machine). [One could argue that using g-candidates is a form of OR-branching, but it is so controlled within the chains that it doesn't matter much.] Using an OR-relation is basically introducing OR-branching.
I've also (later) introduced Forcing-Whips (and I could obviously have defined Forcing-g-Whips, Forcing-Braids in similar ways...]. These patterns have one thing in common: they have OR-branching only at their start. This is also a restricted form of OR-branching, but it already comes with its own cost in additional complexity.
Obviously, these could be generalised to more than 2 candidates at the start (at the cost of still more complexity increase). And, obviously also, as shown by the Tridagon-Forcing-Whips, they can start from other OR relations than the bivalue ones. And, still obviously, both extensions could be considered together.
What I don't have (and don't plan to have, because of complexity reasons) is OR-branching inside chain patterns, i.e. what I would call Dynamic-Forcing-Whips to paraphrase the Sudoku Explainer meaning of "Dynamic". [Marek, is this what you were thinking about?]
What I might consider adding is Generalised Forcing-T&E based on pseudo-TO patterns; but:
- this will not provide a pattern-based solution (T&E is not a resolution rule)
- this supposes some oracle provides the pseudo-TOs and their "guardians" as starting points, because I still can't see any computable pattern-based way of finding them. Mith, as your scripts seem to be able to do this, could you add this information (number and list of guardian candidates) to your min-expands database? If so, I can easily write the Generalised Forcing-T&E procedure necessary to check if they lead to a solution (or to produce the resulting resolution state - a sukaku). The results could be interesting as a measure of the resolution potential of pseudo-TOs.
Note however that the more "guardians" there are, the more unlikely it is Forcing-T&E based on them can do much: Forcing-T&E means that all the branches have some assertion/elimination in common.
The question is not human vs machine (generally a sign of having no rational argument when used in a discussion), but well-defined vs undefined. It's at a logic/abstract level where the difference between brains and CPUs is totally irrelevant.
Mith, I understand your purpose is not to develop/use a formal version of any concept, but that's the best way to keep turning into circles.
Solving a puzzle with a pseudo-TO with 11 extra candidates by an ad hoc piece of reasoning is one thing (and I admit it may be fun for some); defining precise patterns and general rules that can do this on their own (with no one having to manually fill in logical gaps) is a totally different thing - and that's the thing I'm interested in. Of course, my approach is much more constrained and it will probably not take into account all the ad hoc possibilities. As I said before, this is exactly the same situation as with the precisely defined pattern of J-Exocets vs the largely undefined notion of an Exocet.
Note that I'm not saying that imprecise definitions don't have to play a role at the start of a study. Studying informal Exocets may lead to variants of J-Exocets. Similarly, studying cases of pseudo-TO that don't fit into the Tridagon rule or the Tridagon-Forcing-Whips (and it seems there are many of them) may lead to variants of them or to new rules.
The basic resolution rules I've developed (whips, braids, g-whips, g-braids and all the special cases of them I've selected as worth considering) all share a property: they have no OR branching. This is absolutely essential in terms of complexity (be it for a human or a machine). [One could argue that using g-candidates is a form of OR-branching, but it is so controlled within the chains that it doesn't matter much.] Using an OR-relation is basically introducing OR-branching.
I've also (later) introduced Forcing-Whips (and I could obviously have defined Forcing-g-Whips, Forcing-Braids in similar ways...]. These patterns have one thing in common: they have OR-branching only at their start. This is also a restricted form of OR-branching, but it already comes with its own cost in additional complexity.
Obviously, these could be generalised to more than 2 candidates at the start (at the cost of still more complexity increase). And, obviously also, as shown by the Tridagon-Forcing-Whips, they can start from other OR relations than the bivalue ones. And, still obviously, both extensions could be considered together.
What I don't have (and don't plan to have, because of complexity reasons) is OR-branching inside chain patterns, i.e. what I would call Dynamic-Forcing-Whips to paraphrase the Sudoku Explainer meaning of "Dynamic". [Marek, is this what you were thinking about?]
What I might consider adding is Generalised Forcing-T&E based on pseudo-TO patterns; but:
- this will not provide a pattern-based solution (T&E is not a resolution rule)
- this supposes some oracle provides the pseudo-TOs and their "guardians" as starting points, because I still can't see any computable pattern-based way of finding them. Mith, as your scripts seem to be able to do this, could you add this information (number and list of guardian candidates) to your min-expands database? If so, I can easily write the Generalised Forcing-T&E procedure necessary to check if they lead to a solution (or to produce the resulting resolution state - a sukaku). The results could be interesting as a measure of the resolution potential of pseudo-TOs.
Note however that the more "guardians" there are, the more unlikely it is Forcing-T&E based on them can do much: Forcing-T&E means that all the branches have some assertion/elimination in common.
- denis_berthier
- 2010 Supporter
- Posts: 4213
- Joined: 19 June 2007
- Location: Paris
Re: The tridagon rule
by marek stefanik » Thu Jul 14, 2022 1:08 pm
No, I had expected you to implement TO-Braids in a similar fashion to your S- and B-Braids, rather than TO-Forcing-Whips.denis_berthier wrote:What I don't have (and don't plan to have, because of complexity reasons) is OR-branching inside chain patterns, i.e. what I would call Dynamic-Forcing-Whips to paraphrase the Sudoku Explainer meaning of "Dynamic". [Marek, is this what you were thinking about?]
To give an example – puzzle 7 from the original list of 246 expanded forms:
- Code: Select all
........1.....234...5..36.2....7..36....894....46......125...6.4.31..52.56....1..
.-----------------------.---------------------.-------------------.
| 23 23 #6789 | 4789 4569 45678 |#789 5789 1 |
| 16789 #789 16789 | 789 1569 2 | 3 4 #5789 |
|#1789 4 5 | 789 19 3 | 6 #789 2 |
:-----------------------+---------------------+-------------------:
| 1289 2589 189 | 24 7 145 | 289 3 6 |
| 12367 2357 167 | 23 8 9 | 4 157 57 |
| 123789 235789 4 | 6 235 15 | 2789 15789 5789 |
:-----------------------+---------------------+-------------------:
|#789 1 2 | 5 349 478 |#789 6 34 |
| 4 #789 3 | 1 69 678 | 5 2 #789 |
| 5 6 #789 | 234789 2349 478 | 1 #789 34 |
'-----------------------'---------------------'-------------------'
Or maybe the (non-contradictory) 11-cell patterns defined at the beginning of this thread could also be used at an earlier stage of the chain:
TO-whip[14]: n6c5{r2 r1} – {n6r1c3 [TO[11] label placeholder]} – r3c1{n9 n1} – n1c5{r3 .} ==> -5r2c5
(I hope that I notated it correctly, with the exception of the missing TO-labels.)
This would avoid any OR-branching as well as the need to define "potential TOs" to start the OR-branching from.
Marek
- marek stefanik
- Posts: 359
- Joined: 05 May 2021
Re: The tridagon rule
by denis_berthier » Thu Jul 14, 2022 2:10 pm
marek stefanik wrote: I had expected you to implement TO-Braids in a similar fashion to your S- and B-Braids, rather than TO-Forcing-Whips.
OK, I see what you mean - using a contextual TO instead of the final CSP contradiction in a whip. Your example is interesting.
But there's a complexity problem. Finding a real TO with 1 or 2 additional candidates is not very difficult. But having to consider all the contextual TOs at every step of every whip/braid is largely more computationally complex than having to consider all the potential Subsets.
As I said before, all this is meaningful only in the presence of an oracle saying that there is some possibility of a pseudo-TO. Otherwise, the return on investment for this kind of TO-chain is null.
Take any puzzle in ph2010 and tell me what you get by trying this.
- denis_berthier
- 2010 Supporter
- Posts: 4213
- Joined: 19 June 2007
- Location: Paris
Re: The tridagon rule
by mith » Thu Jul 14, 2022 4:53 pm
Denis, this started with you invoking the "real player". Any "human vs. machine" arguments are stemming from that.
As for the well-defined vs. undefined thing, your definition of "well-defined" seems to be contingent on fitting into your pattern-based resolution rules ("a pattern is well defined if..."). It should be clear that I am not talking about patterns in the sense of CSP-Rules. Whether my "Chromatic-Forcing-T&E" definition is a pattern in your sense or whether you are interested in it has no impact on it being well-defined or not. Nor whether there is a complexity problem for that matter - I'm making no claim as to whether it would be feasible to broadly look for OR-branching Forcing Chains based on arbitrary non-k-chromatic graphs of cells, obviously. But it is still well-defined as a piece of logic. (I do think it's feasible to broadly look for trivalue oddagon forcing chains, and again, this has already been implemented in YZF_Sudoku.)
As for an "oracle", I can certainly look into adding this in a usable way (right now the code is a bit of a mess, spitting out results for a narrow purpose). Of course, it will have to wait until I have a working computer!
As for the well-defined vs. undefined thing, your definition of "well-defined" seems to be contingent on fitting into your pattern-based resolution rules ("a pattern is well defined if..."). It should be clear that I am not talking about patterns in the sense of CSP-Rules. Whether my "Chromatic-Forcing-T&E" definition is a pattern in your sense or whether you are interested in it has no impact on it being well-defined or not. Nor whether there is a complexity problem for that matter - I'm making no claim as to whether it would be feasible to broadly look for OR-branching Forcing Chains based on arbitrary non-k-chromatic graphs of cells, obviously. But it is still well-defined as a piece of logic. (I do think it's feasible to broadly look for trivalue oddagon forcing chains, and again, this has already been implemented in YZF_Sudoku.)
As for an "oracle", I can certainly look into adding this in a usable way (right now the code is a bit of a mess, spitting out results for a narrow purpose). Of course, it will have to wait until I have a working computer!
- mith
- Posts: 996
- Joined: 14 July 2020
Re: The tridagon rule
by marek stefanik » Thu Jul 14, 2022 5:36 pm
Personally my main interest would be the effect of TOs on the puzzles' ratings (where they fit on the (TO, Bp)B scale, that being a placeholder rating for braids with TOs and braids[p] as rlcs).denis_berthier wrote:But there's a complexity problem. Finding a real TO with 1 or 2 additional candidates is not very difficult. But having to consider all the contextual TOs at every step of every whip/braid is largely more computationally complex than having to consider all the potential Subsets.
I am curious if there is a puzzle in the database that remains outside T&E(2) with TOs used.
For any (TO, Bp)B rating, to determine whether a puzzle is in (TO, Bp)B:
1) Reach the state after all available (TO, Bp)B eliminations have been made (at the start no TOs have been identified, ie. all BpB eliminations).
1.1) If the puzzle is solved, it is.
2) Identify TOs from the dead ends of partial (TO-)braids for each candidate (or stop once you find a new one).
2.1) If none (new) has been found, it is not (you can keep the TOs and look for a solution in (TO, Bp+1)B).
3) Repeat from 1) with the identified TOs.
For this problem there are many optimizations one can make.
When using T&E to simulate steps 1 and 2, they can be done at once, eliminating the candidates if they produce a contradiction in step 2 after the TO deductions.
For puzzles solvable by TO-braids:
While you could try to find the path using the smallest patterns, a single class would be much more efficient.
For puzzles not in BpB for any given BpB rating:
If a candidate C can be eliminated using the TO contradiction pattern, this pattern must be present at the dead end of the T&E procedure starting with the placement of C (and the mutual dead end of partial braids with C as their target).
When identifying useful TOs, one can simply look at the dead end for each candidate (and ignore llcs of the partial braids of the candidates which have already been checked; in an attempt to eliminate these candidates only check for the TOs already found).
(If the 11-cell patterns are also used, we have to look at the dead ends of the TO-braids with the identified TOs.)
(Any candidate which can be eliminated using the TO[12] pattern without the TO[11] patterns can also be eliminated using the TO[11] patterns without the TO[12] pattern, but not vice versa.)
This should limit the number of possible TOs to just a few, each of which occurs for some candidates (due to the process they were found).
Looking for the TOs might still take a relatively long time if there is none or you want to find all of them (say to find every possible TO-braid/the shortest one, which is one of the differences between human solvers and computer programs – no human solver would ever be required to do that).
A different way would be needed to find TOs for candidates which can be eliminated without them (not a problem when trying to determine a (TO, Bp)B rating).
I might try it, the pattern is very constraining.denis_berthier wrote:As I said before, all this is meaningful only in the presence of an oracle saying that there is some possibility of a pseudo-TO. Otherwise, the return on investment for this kind of TO-chain is null.
Take any puzzle in ph2010 and tell me what you get by trying this.
Marek
- marek stefanik
- Posts: 359
- Joined: 05 May 2021
Re: The tridagon rule
by denis_berthier » Thu Jul 14, 2022 5:39 pm
.
"well-defined" means "well defined", CSP-Rules doesn't have anything to do in this. The TO contradiction pattern is well-defined. Anything that has an unspecified number of additional candidates at unspecified places is not a well-defined pattern. With such broad pseudo-definitions, you can only define a pattern of cells in 4 blocks and almost everything based on it would be a TO pattern - i.e. 100,000s possible patterns of candidates. And the only "piece of logic" associated to this is, it allows a big OR conclusion, which itself doesn't allow anything precise.
Nobody knows how YZF_Sudoku works, but its chains are obviously not pattern-based, and I've never seen any definition of any of the techniques it uses, so this software is of little interest when talking of pattern-based solutions.
As for the complexity of this implementation, there's an easy test: activate YZF trivalue oddagon forcing chains on the original ph2010 and tell me what you get.
"well-defined" means "well defined", CSP-Rules doesn't have anything to do in this. The TO contradiction pattern is well-defined. Anything that has an unspecified number of additional candidates at unspecified places is not a well-defined pattern. With such broad pseudo-definitions, you can only define a pattern of cells in 4 blocks and almost everything based on it would be a TO pattern - i.e. 100,000s possible patterns of candidates. And the only "piece of logic" associated to this is, it allows a big OR conclusion, which itself doesn't allow anything precise.
mith wrote:I do think it's feasible to broadly look for trivalue oddagon forcing chains, and again, this has already been implemented in YZF_Sudoku.
Nobody knows how YZF_Sudoku works, but its chains are obviously not pattern-based, and I've never seen any definition of any of the techniques it uses, so this software is of little interest when talking of pattern-based solutions.
As for the complexity of this implementation, there's an easy test: activate YZF trivalue oddagon forcing chains on the original ph2010 and tell me what you get.
- denis_berthier
- 2010 Supporter
- Posts: 4213
- Joined: 19 June 2007
- Location: Paris
Re: The tridagon rule
by mith » Fri Jul 15, 2022 5:30 pm
You're badly overestimating the number of patterns actually possible here. Just for a quick check, I hacked something together to find all naively possible TO graphs and triples for those graphs, and ran it on all the ph2010 11.9s + Loki. Of the 489888 (9 choices of 4 boxes, 8 choices of parity, 3^4 choices of diagonal, 84 triples) possibilities, only 673 are viable in the worst case (eleven's .2.4...8.....8...68....71..2..5...9..95.......4..3.........1..7..28...4.....6.3..). This took on the order of 0.05 seconds per puzzle. (The lowest was Loki at 163; not surprising, the more givens there are the fewer viable options.)
A rough outline of how this code works:
1. Iterate over the choices of 4 boxes.
2. Iterate over the choices of parity (either 3 positive and 1 negative, or 1 positive and 3 negative; and then 4 choices for which box is the odd one out).
3. Choose a diagonal for the first box.
4. Starting with the full list of 84 triples, check which ones are viable for that diagonal. A triple is viable if there is a way to place the three digits of the triple in the three cells of the diagonal chosen. (If there is no way to place the triple on the diagonal, we can already eliminate this possibility - these three cells already can't be "three colored" with this triple, so knowing that the full pattern of cells isn't 3-colorable provides no new information.)
5. Choose a diagonal for the second box.
6. Starting with the list of triples viable for the first box, check which are viable for the second.
7. Repeat for the other boxes. If at any point there are no triples on the list, continue to the next choice of diagonal.
None of the ph2010 11.9s have a pattern/triple combination with fewer than 13 guardian candidates, and likely after narrowing down with more checks the lower bound would be even higher. For a concrete example, here's a "13 guardian candidate" TO (boxes and cells are 0-index here):
[edit]There was a typo resulting in a miscount of guardian candidates, this has been corrected above[/edit]
This one fails checking possibilities for 7 in b78 - in both cases, 7 can only appear in the bottom row. This sort of check should be easy enough to add, though more complicated examples may exist.
I suspect after adding checks like this, the number of viable patterns/triples to check would be in the single digits, if not zero, for the vast majority of puzzles, and that those viable combinations would have a huge number of guardian candidates (well beyond the point that it would be fruitful to check an OR-branched T&E on them... but it *could* be done). Whereas there will be at least one viable combination for all known depth 3 puzzles, with at most about 12 guardian candidates (some of which, even with so many guardian candidates, will lead to a useful elimination/placement, even for a "real player").
A rough outline of how this code works:
1. Iterate over the choices of 4 boxes.
2. Iterate over the choices of parity (either 3 positive and 1 negative, or 1 positive and 3 negative; and then 4 choices for which box is the odd one out).
3. Choose a diagonal for the first box.
4. Starting with the full list of 84 triples, check which ones are viable for that diagonal. A triple is viable if there is a way to place the three digits of the triple in the three cells of the diagonal chosen. (If there is no way to place the triple on the diagonal, we can already eliminate this possibility - these three cells already can't be "three colored" with this triple, so knowing that the full pattern of cells isn't 3-colorable provides no new information.)
5. Choose a diagonal for the second box.
6. Starting with the list of triples viable for the first box, check which are viable for the second.
7. Repeat for the other boxes. If at any point there are no triples on the list, continue to the next choice of diagonal.
None of the ph2010 11.9s have a pattern/triple combination with fewer than 13 guardian candidates, and likely after narrowing down with more checks the lower bound would be even higher. For a concrete example, here's a "13 guardian candidate" TO (boxes and cells are 0-index here):
- Code: Select all
.---------------------.--------------------.----------------------.
| 23467 24789 36789 | 46789 4567 45789 | 3689 36789 1 |
| 167 1789 16789 | 6789 2 3 | 689 4 5 |
| 3467 4789 5 | 1 467 4789 | 2 36789 3689 |
:---------------------+--------------------+----------------------:
| 347 479 2 | 5 3467 478 | 34689 1 34689 |
| 1345 6 139 | 348 134 2 | 7 3589 3489 |
| 8 1457 137 | 3467 9 147 | 3456 2356 2346 |
:---------------------+--------------------+----------------------:
| 156 158 4 | 2 135 159 | 135689 35689 7 |
| 1257 3 178 | 479 1457 6 | 14589 2589 2489 |
| 9 1257 167 | 347 8 1457 | 13456 2356 2346 |
'---------------------'--------------------'----------------------'
box 3 cells 0, 4, 8 possibles [3, 4, 7], [6], [1, 3, 7]
box 4 cells 2, 4, 6 possibles [4, 7, 8], [1, 3, 4], [3, 4, 6, 7]
box 6 cells 0, 4, 8 possibles [1, 5, 6], [3], [1, 6, 7]
box 7 cells 1, 5, 6 possibles [1, 3, 5], [6], [3, 4, 7]
triples [[3, 6, 7]] guardians [13]
[edit]There was a typo resulting in a miscount of guardian candidates, this has been corrected above[/edit]
This one fails checking possibilities for 7 in b78 - in both cases, 7 can only appear in the bottom row. This sort of check should be easy enough to add, though more complicated examples may exist.
I suspect after adding checks like this, the number of viable patterns/triples to check would be in the single digits, if not zero, for the vast majority of puzzles, and that those viable combinations would have a huge number of guardian candidates (well beyond the point that it would be fruitful to check an OR-branched T&E on them... but it *could* be done). Whereas there will be at least one viable combination for all known depth 3 puzzles, with at most about 12 guardian candidates (some of which, even with so many guardian candidates, will lead to a useful elimination/placement, even for a "real player").
- mith
- Posts: 996
- Joined: 14 July 2020
Re: The tridagon rule
by denis_berthier » Sat Jul 16, 2022 4:38 am
.
Hi mith
Interesting. Your general TO conditions seem to be more restrictive than I thought.
These results make it look more interesting to check how far Forcing-T&E based on these conditions would lead in the min-expands database.
Hi mith
Interesting. Your general TO conditions seem to be more restrictive than I thought.
These results make it look more interesting to check how far Forcing-T&E based on these conditions would lead in the min-expands database.
- denis_berthier
- 2010 Supporter
- Posts: 4213
- Joined: 19 June 2007
- Location: Paris
Re: The tridagon rule
by mith » Sat Jul 16, 2022 9:27 pm
So preliminary results with a rudimentary filter:
For each graph/triple combination, check each box for valid placements of the triple within the chosen cells. Track any digit which is forced to a single cell in the box in this way. If two such forced digits see each other, filter this combination out.
This is already a little stronger than the example given above. There, 7 could only appear in one cell of each of two boxes, and both were in the bottom row. Here, there can be cases where a digit placement is forced *by the other digits* in the triple, so rather than just considering two cells of the pattern we may be considering six (all three cells in both boxes).
In theory, this can be extended further. For example, consider ........1....23.45..51..2....25...1..6...27..8...9......42....7.3...6...9...8.... (dobrichev 11.9). A possible TO/triple combination here is 467 in b1p267, b2p348, b4p159, b5p357.
Under the naive check, this is valid - in each box, 467 can be placed in the three chosen cells in at least one order.
Under the new filter, this is still valid. In b45, the digit placement is forced (467b4p159, 746b5p357) but these do not clash. b12 placements are not forced for any of the digits.
However, now consider b12 in relation to the forced digits in the other boxes. b1p6 naively could contain 6 or 7, but b4p9 must contain 7 (if all cells were to be from 467), so b1p6 is forced to be 6. Continuing in this way, you eventually end up with 4 in both b1p2 and b2p3, and it breaks - but to do so, you have considered all 12 cells.
These cases could be caught as well and filtered out - and I think if this were done it would filter all or almost all combinations - but when we're considering all 12 cells anyway to prove it's broken, I'm not sure that logically there is any meaningful difference in this and any other TO with a ton of guardians. It's just that we're proving directly that the triple can't fill all 12 cells, rather than proving it with graph colorability.
(Something to consider is whether even some of the currently filtered cases - considering 6 cells in 2 boxes - may yield some logic using the "guardians" in those cells. Probably not anything that couldn't be found in a simpler way, but it's still a question.)
Results in next posts.
For each graph/triple combination, check each box for valid placements of the triple within the chosen cells. Track any digit which is forced to a single cell in the box in this way. If two such forced digits see each other, filter this combination out.
This is already a little stronger than the example given above. There, 7 could only appear in one cell of each of two boxes, and both were in the bottom row. Here, there can be cases where a digit placement is forced *by the other digits* in the triple, so rather than just considering two cells of the pattern we may be considering six (all three cells in both boxes).
In theory, this can be extended further. For example, consider ........1....23.45..51..2....25...1..6...27..8...9......42....7.3...6...9...8.... (dobrichev 11.9). A possible TO/triple combination here is 467 in b1p267, b2p348, b4p159, b5p357.
Under the naive check, this is valid - in each box, 467 can be placed in the three chosen cells in at least one order.
Under the new filter, this is still valid. In b45, the digit placement is forced (467b4p159, 746b5p357) but these do not clash. b12 placements are not forced for any of the digits.
However, now consider b12 in relation to the forced digits in the other boxes. b1p6 naively could contain 6 or 7, but b4p9 must contain 7 (if all cells were to be from 467), so b1p6 is forced to be 6. Continuing in this way, you eventually end up with 4 in both b1p2 and b2p3, and it breaks - but to do so, you have considered all 12 cells.
These cases could be caught as well and filtered out - and I think if this were done it would filter all or almost all combinations - but when we're considering all 12 cells anyway to prove it's broken, I'm not sure that logically there is any meaningful difference in this and any other TO with a ton of guardians. It's just that we're proving directly that the triple can't fill all 12 cells, rather than proving it with graph colorability.
(Something to consider is whether even some of the currently filtered cases - considering 6 cells in 2 boxes - may yield some logic using the "guardians" in those cells. Probably not anything that couldn't be found in a simpler way, but it's still a question.)
Results in next posts.
- mith
- Posts: 996
- Joined: 14 July 2020
Re: The tridagon rule
by mith » Sat Jul 16, 2022 9:33 pm
For the first batch, I ran all the 11.7+ puzzles from ph2010. (These are taking a bit over a second per now with the additional filter and some other stuff I put in, but I'm sure it could be optimized. And this is on my beaten up work laptop, since my desktop is still out of action.)
The first column here is the number of combinations after the new filter. The second column is the number filtered out by the new filter (so the sum is the naively valid count). The next two numbers are the min/max guardian candidate counts for the valid combinations. The lowest guardian count of any combination in these 208 puzzles is 11. The highest valid combination count is 508.
Hidden Text: Show
The first column here is the number of combinations after the new filter. The second column is the number filtered out by the new filter (so the sum is the naively valid count). The next two numbers are the min/max guardian candidate counts for the valid combinations. The lowest guardian count of any combination in these 208 puzzles is 11. The highest valid combination count is 508.
- mith
- Posts: 996
- Joined: 14 July 2020
Re: The tridagon rule
by mith » Sat Jul 16, 2022 9:38 pm
For comparison, here are the first 188 min-expands (this should be all min-expands from the original batch of 972 puzzles; might be a little off, hard to check since I'm not on the desktop).
Overall, there are fewer valid combinations - this isn't surprising, given the digit distribution of these grids. Only three hit triple digits (and all of those have a single-guardian TO available). The minimum guardian counts are of course way lower as well - a max of 6, barely half as much as the lowest from ph2010, and an average minimum below 2.
Hidden Text: Show
Overall, there are fewer valid combinations - this isn't surprising, given the digit distribution of these grids. Only three hit triple digits (and all of those have a single-guardian TO available). The minimum guardian counts are of course way lower as well - a max of 6, barely half as much as the lowest from ph2010, and an average minimum below 2.
- mith
- Posts: 996
- Joined: 14 July 2020
Re: The tridagon rule
by mith » Mon Jul 18, 2022 2:16 pm
I took an expanded look at the min-expands, printing any combination with <= 10 guardian candidates. A cap on the guardian candidate count reduces all of these to a single-digit number of combinations, always with the same triple of digits. This suggests it's only ever worthwhile to check the triple suggested by the digit distribution, though of course it's not proven that this triple will always be the best choice.
There is also always a clear best option among these, corresponding to the choice of boxes based on where the triple digits appear as givens. Again not surprising, but not a proof that this must be the case.
I wanted to highlight this puzzle:
This was the puzzle in the batch with the highest minimum guardian count. According to the current script, this is an ambiguous case - we can choose either of two diagonals in box 5. However, on closer inspection this is not actually ambiguous, because one cell in the box is limited to the 379 triple. As mentioned previously, in such a case this cell *must* be included as part of the cell pattern - if such a cell exists off-diagonal, then the diagonal cells of course can never actually be filled with the triple, as it would leave nothing for the off-diagonal cell. I'll look at adding this filter to the code as well (I suspect it won't matter for the ph2010 puzzles, but will matter a great deal for the te3 puzzles).
There is also always a clear best option among these, corresponding to the choice of boxes based on where the triple digits appear as givens. Again not surprising, but not a proof that this must be the case.
I wanted to highlight this puzzle:
- Code: Select all
..34.6....5....1.27.92..........851........28......4.65.86....46.28.4.51..1..5...
boxes [4, 5, 7, 8] cells [[0, 5, 7], [2, 3, 7], [2, 4, 6], [1, 3, 8]] trips [3, 7, 9] guard 6
boxes [4, 5, 7, 8] cells [[1, 3, 8], [2, 3, 7], [2, 4, 6], [1, 3, 8]] trips [3, 7, 9] guard 9
41;137;6;28;..34.6....5....1.27.92..........851........28......4.65.86....46.28.4.51..1..5...;44;272
This was the puzzle in the batch with the highest minimum guardian count. According to the current script, this is an ambiguous case - we can choose either of two diagonals in box 5. However, on closer inspection this is not actually ambiguous, because one cell in the box is limited to the 379 triple. As mentioned previously, in such a case this cell *must* be included as part of the cell pattern - if such a cell exists off-diagonal, then the diagonal cells of course can never actually be filled with the triple, as it would leave nothing for the off-diagonal cell. I'll look at adding this filter to the code as well (I suspect it won't matter for the ph2010 puzzles, but will matter a great deal for the te3 puzzles).
- mith
- Posts: 996
- Joined: 14 July 2020
Re: The tridagon rule
by yzfwsf » Mon Jul 18, 2022 2:36 pm
Triplet Oddagon Forcing Chain: Each true guardian of Triplet Oddagon will all lead To: r7c6<>3,r7c6<>7,r7c6<>9
2r6c5 - 2r6c6 = 2r7c6
1r7c6
2r7c6
btte
2r6c5 - 2r6c6 = 2r7c6
1r7c6
2r7c6
btte
- yzfwsf
- Posts: 905
- Joined: 16 April 2019
Re: The tridagon rule
by mith » Mon Jul 18, 2022 2:40 pm
Yeah, this stripped out a good number of <= 10 guardian candidate combinations. There are still some true ambiguous cases - for example:
Here, box 7 has no givens at all, and no cell is limited to only 125 - so any of the three diagonals with the correct parity can be used. (And actually all six diagonals are used, depending on the choice of other boxes. In the first case, boxes 2 and 8 have different parity, so boxes 1 and 7 need the same parity for a broken pattern; in the second, boxes 3 and 9 have the same parity, so boxes 1 and 7 need different parities. One choice is dropped here in the b1379 case because it has 11 guardian candidates.)
(Of course, the clear best choice here is boxes 2389, placing a digit immediately.)
- Code: Select all
...4.6...4.7.89.368..37...429.....6...1.........9.3.......946.7...8.739....63..48
boxes [0, 1, 6, 7] cells [[0, 4, 8], [1, 3, 8], [0, 4, 8], [0, 4, 8]] trips [1, 2, 5] guard 8
boxes [0, 1, 6, 7] cells [[0, 4, 8], [1, 3, 8], [1, 5, 6], [0, 4, 8]] trips [1, 2, 5] guard 10
boxes [0, 1, 6, 7] cells [[0, 4, 8], [1, 3, 8], [2, 3, 7], [0, 4, 8]] trips [1, 2, 5] guard 8
boxes [0, 2, 6, 8] cells [[0, 4, 8], [2, 3, 7], [0, 5, 7], [1, 5, 6]] trips [1, 2, 5] guard 9
boxes [0, 2, 6, 8] cells [[0, 4, 8], [2, 3, 7], [1, 3, 8], [1, 5, 6]] trips [1, 2, 5] guard 9
boxes [1, 2, 4, 5] cells [[1, 3, 8], [2, 3, 7], [2, 3, 7], [0, 4, 8]] trips [1, 2, 5] guard 10
boxes [1, 2, 7, 8] cells [[1, 3, 8], [2, 3, 7], [0, 4, 8], [1, 5, 6]] trips [1, 2, 5] guard 1
boxes [4, 5, 7, 8] cells [[0, 5, 7], [0, 4, 8], [0, 4, 8], [1, 5, 6]] trips [1, 2, 5] guard 9
52;32;1;27;...4.6...4.7.89.368..37...429.....6...1.........9.3.......946.7...8.739....63..48;71;823
Here, box 7 has no givens at all, and no cell is limited to only 125 - so any of the three diagonals with the correct parity can be used. (And actually all six diagonals are used, depending on the choice of other boxes. In the first case, boxes 2 and 8 have different parity, so boxes 1 and 7 need the same parity for a broken pattern; in the second, boxes 3 and 9 have the same parity, so boxes 1 and 7 need different parities. One choice is dropped here in the b1379 case because it has 11 guardian candidates.)
(Of course, the clear best choice here is boxes 2389, placing a digit immediately.)
- mith
- Posts: 996
- Joined: 14 July 2020
