The New Sudoku Players' Forum

by **eleven** » Sat Oct 26, 2024 3:24 pm

@P.O.: Since Denis was not willing or able to simply explain, what is different in his implementation, i read his k-template rule thoroughly, which i thought should be the same as the one we all were working with (a template for a digit n can be removed, if a k-template with n and k-1 other digits is not possible).
Instead he removes all (k-1)-digit templates, which are not compatible with any other digit. So a template/candidate elimination can be made, which depends on a set of k-templates including all 9 digits.
Simple example: Though the 3-template 128 is possible as i posted it, it then can be deleted, because in a 126-template 12 can't be in r6c46.

Code: Select all: +-------+-------+-------+ +-------------------------+-----------------------+----------------------+ | 8 2 . | . 1 . | . . . | | 128 2689 3 | 4 15 568 | 7 58 69 | | . . . | 8 . . | 1 2 . | | 48 5 468 | 3678 378 9 | 1 2 36 | | . . 1 | . 2 . | . 8 . | | 7 689 1689 | 136 2 3568 | 48 458 369 | +-------+-------+-------+ +-------------------------+-----------------------+----------------------+ | 2 1 . | . . . | . . 8 | | 23 1 49 | 5 34 7 | 29 6 8 | | . 8 . | . . . | 2 1 . | | 6 2348 45 | 38 9 2348 | 25 1 7 | | . . . | 1 8 2 | . . . | | 258 2789 57 |*16 18 *26 | 59 3 4 | +-------+-------+-------+ +-------------------------+-----------------------+----------------------+ | . . 2 | . . 8 | . . 1 | | 345 34678 2 | 9 34578 3458 | 3468 48 1 | | 1 . . | . . . | 8 . 2 | | 1345 34678 145678 | 378 34578 3458 | 3468 9 2 | | . . 8 | 2 . 1 | . . . | | 9 348 48 | 2 6 1 | 348 7 5 | +-------+-------+-------+ +-------------------------+-----------------------+----------------------+

Other deletions will be very hard to explain.

Website · by **denis_berthier** » Sat Oct 26, 2024 3:49 pm

.
The rules I've written here were perfectly clear. They are implemented in SudoRules exactly as described here.
But your example is interesting.
.

by **eleven** » Sat Oct 26, 2024 4:35 pm

Yes, nice, after we finally had agreed to one definition, you gave another one to confuse things again.

by **P.O.** » Sat Oct 26, 2024 5:20 pm

@eleven,
in order to fully understand the eliminations made by Denis' implementation, what is needed is the set of templates that T2 leaves to T3 to make its combinations
those remaining after 2-template allow 3-template to make the following combinations (1 2 6):

Hidden Text: Show

another example that makes you think
remember the resolution of Tungston Rod, for you as for me it is in 6-template, after 5-template we find the same count of templates left and the same resolution state with still 245 candidates
Denis classifies Tungston Rod in T4, think about the number of eliminations that his implementation makes with the combinations of 4

Code: Select all: ........7.2.4...6.1.....5...9...2.4....8..6..6..9.......5..3....3..8..2.7....4..1 34589 4568 34689 12356 123569 15689 123489 1389 7 3589 2 3789 4 13579 15789 1389 6 389 1 4678 346789 2367 23679 6789 5 389 23489 358 9 1378 13567 13567 2 1378 4 358 2345 1457 12347 8 13457 157 6 13579 2359 6 14578 123478 9 13457 157 12378 13578 2358 2489 1468 5 1267 12679 3 4789 789 4689 49 3 1469 1567 8 15679 479 2 4569 7 68 2689 256 2569 4 389 3589 1 253 candidates.

after 5-template:

Hidden Text: Show

Code: Select all: #VT: (42 10 113 24 42 28 57 144 88) Cells: nil nil nil nil nil nil nil nil nil Candidates:nil nil nil nil nil nil nil nil nil 3combs #VT: (30 10 75 24 42 28 55 97 56) Cells: nil nil nil nil nil nil nil nil nil Candidates:(7) nil (7 27) nil nil nil nil (7 27) (7 27) 4combs #VT: (30 10 74 24 34 28 52 96 56) Cells: nil nil nil nil nil nil nil nil nil Candidates:nil nil nil nil nil nil nil nil nil 5combs #VT: (27 10 53 24 32 28 46 84 51) Cells: nil nil nil nil nil nil nil nil nil Candidates:nil nil (14) nil nil nil nil nil nil 5combs #VT: (27 10 53 24 32 28 45 84 51) Cells: nil nil nil nil nil nil nil nil nil Candidates:nil nil nil nil nil nil nil nil nil Left in pool: (9603 20486 12755 24013 13998 21738 8212 29237 20274 30797 49020 33421 43484 26909 24292 11282 5551 31724 17410 11130 19590 12227 25841 14080 21236 5176 33225 21335 21543 11095 40953 26499 15831 16199 28811 19594 9353 59267 47371 33847 87454 80048 85825 64436 83167 3467 28975 37694 15133 13259 36309 55815 57318 51328 58168 2702 34358 29297 22944 15265 89257 32004 27074 47297 69782 5321 3792 25765 15663 22264 15792 15269 22119 13198 34161 25735 15065 47158 28716 15902 33084 36522 31709 52976 37256 22693 104102 72236 17925 64119 16245 30806 18876 47286 23916 36043 37443 20511 9479 43344 51909 33180 26942 67868 39746 25410 48447 53281 77462 67139 67321 138855 126332 62740 151879 42784 55052 32700 66933 106787 41519 34035 62623 111439 75241 36995) #VT: (27 10 53 24 32 28 45 84 51) 34589 4568 34689 12356 123569 15689 24 1389 7 3589 2 3789 4 1579 15789 1389 6 389 1 4678 346789 2367 23679 6789 5 389 24 358 9 1378 13567 13567 2 1378 4 358 2345 1457 12347 8 13457 157 6 13579 2359 6 14578 123478 9 13457 157 12378 13578 2358 2489 1468 5 1267 12679 3 4789 789 4689 49 3 1469 1567 8 15679 479 2 4569 7 68 2689 256 2569 4 389 3589 1 245 candidates.

Website · by **denis_berthier** » Sat Oct 26, 2024 5:54 pm

eleven wrote:Yes, nice, after we finally had agreed to one definition, you gave another one to confuse things again.

Who is we?
I gave the definition that uses the full power of templates. Not my fault if your definition is restricted to particular cases.
.

by **eleven** » Sat Oct 26, 2024 6:02 pm

@ P.O.: Yes, in my opinion the definition is all but intuitive, and the calculation over-complicated, slow, hardly reproducible or traceable, and the result of minor worth.
But scientifically correct

Website · by **denis_berthier** » Sat Oct 26, 2024 6:24 pm

.
Templates are not for human solving, except in extremely rare cases. Your restricted definition doesn't change this.

Elimination of a template[k] if it can't be extended to any template[k+1] couldn't be more intuitive.
As for computational complexity, it takes about 1hr to compute all the cbg-000 collection. I'm curious to see what you can do with your program.

by **eleven** » Sat Oct 26, 2024 8:10 pm

Well in the old times manual players were interested, because there were relationships to Exocet and SK-loops, but as you say, it turned out to be no applicable help for them.
As said, i don't have my old program anymore.
What i would be interested in at the end is, if P.O.'s calculation for the k-template depths of tridagon puzzles are relatively low, too.

by **Maxito_Bahiense** » Sat Oct 26, 2024 10:07 pm

eleven wrote:Well in the old times manual players were interested, because there were relationships to Exocet and SK-loops, but as you say, it turned out to be no applicable help for them.

I was thinking about that. We colourists work with candidate links. Strong implications usually come from bivaluedness/bilocation, and so on, but sometimes links and implications can be found by other means, for instance, Thor's hammers with two guardians give candidates in two parities. I was wondering if template analysis can tell us something general of such links outside bivaluedness/bilocation.

by **blue** » Sat Oct 26, 2024 11:18 pm

denis_berthier wrote:.As for computational complexity, it takes about 1hr to compute all the cbg-000 collection. I'm curious to see what you can do with your program.

At 3.6 GHz:

Code: Select all: // level 0 : 7489 (35.0%) // level 1 : 3630 (17.0%) // level 2 : 1916 ( 9.0%) // level 3 : 6903 (32.3%) <- correction: 6984 (32.7%) // level 4 : 1420 ( 6.6%) <- correction: 1339 ( 6.3%) // level 5 : 17 ( 0.1%) // CPU time : 48.08s

(This was just "test" code. I'm sure that the CPU time can be reduced significantly.)

When I try to code your method, I run into a problem.
After T2 rules stall out, the T3 rules cause template[2] items to be "deleted", but you haven't given enough detail for me to know how that would lead to any changes in template[1] lists.
If I don't add something else to the code, it builds and prunes lists up through size 9, and bails.
The template[9] list, only has has one entry, but the pencilmark state has been unchanged since T2 stalled out.

If I make a guess that "Tk-delete" (k >= 2) should be re-phrased to say that an item in a template[k-1] list should be "deleted" whenever it doesn't have extensions in each of the relevant template[k] lists ... (9-(k-1)) of them ... then the "T4" puzzles at the top of the thread, are all solved in T3 !

I have another guess, but it can't be right either.

What's the story ?
Lots of detail, please

Cheers,
Blue.

Website · by **denis_berthier** » Sun Oct 27, 2024 3:42 am

Hi Blue,
Nice to see you here

I can't say much more than what I've already written. Maybe I can say it in a slightly different way.
I think the main differences in my approach are:
- I define the rules at the pure logic level (regardless of any possible implementation);
- templates are built and eliminated progressively at each depth.
Consider that I write "eliminated", "deleted" ... as a shorthand for the pure logic terms: "proven impossible".

blue wrote:When I try to code your method, I run into a problem.
After T2 rules stall out, the T3 rules cause template[2] items to be "deleted", but you haven't given enough detail for me to know how that would lead to any changes in template[1] lists.

Every time one or more templates[2] get(s) deleted, new T2-delete rules become applicable (because they have fewer conditions to satisfy). There's nothing more.
In SudoRules, this is dealt with automatically by the pattern matcher: for logical consistency, it works on the real logic state at the time a rule is applied.
In procedural programming, you need to retry all the T2-delete rules.
This is valid also at any Tk level. Deletions of templates[k] enable new Tk-delete rules.

blue wrote:If I don't add something else to the code, it builds and prunes lists up through size 9, and bails.

As all the puzzles are in T4, I never have to consider templates[9]. But when a template[k} is deleted, every larger template that contains it is deleted (for obvious reasons) - or never built when its level is reached, if it hadn't been reached before.

blue wrote:If I make a guess that "Tk-delete" (k >= 2) should be re-phrased to say that an item in a template[k-1] list should be "deleted" whenever it doesn't have extensions in each of the relevant template[k] lists ... (9-(k-1)) of them ...

Rule Tk-delete doesn't need to be rephrased. It says that a template[k-1] for numbers n1...nk-1 must be deleted if there's a number nk different of n1...nk-1 such that this template[k-1] doesn't have any extension to a template[k] for n1...nk-1 nk.
Here also, it's progressive. Templates[k-1] can only be eliminated directly by templates[k]; no need to go up to 9.
.

by **blue** » Sun Oct 27, 2024 6:20 am

Hi Denis,
Thanks.

denis_berthier wrote:
blue wrote:If I make a guess that "Tk-delete" (k >= 2) should be re-phrased to say that an item in a template[k-1] list should be "deleted" whenever it doesn't have extensions in each of the relevant template[k] lists ... (9-(k-1)) of them ...

Rule Tk-delete doesn't need to be rephrased. It says that a template[k-1] for numbers n1...nk-1 must be deleted if it doesn't have any extension to a template[k] for each k set of different numbers containing n1...nk-1.
Here also, it's progressive. Templates[k-1] can only be eliminated directly by templates[k]; no need to go up to 9.

What you're saying, seems to imply that my guess was correct ... at least as far as "what I needed to do", to make the code functional.
Your statement of the "T2-delete" rule, doesn't mention "template[2] (anything)" directly, and likewise "Tk-delete", doesn't mention "template[k]".

denis_berthier wrote:.
- rule T2-delete: Given an instantiation I of a template[1] for number n1, if there's a number n2≠n1 such that I is not compatible with any instantiation of a template[1] for number n2, then the instantiation I must be deleted.

- rule Tk-delete: Given an instantiation I of a template[k-1] for numbers n1... nk-1, if there's a number nk≠n1,...nk-1 such that no instantiation of the template[1] for number nk is compatible with I, then the instantiation I of the template[k-1] must be deleted.

IMHO, a re-phrasing would be helpful.

Now my only question is: why does my code think that your T4 puzzles are actually in T3 ?
I'll check the code again, but I don't think it has bugs.

Website · by **denis_berthier** » Sun Oct 27, 2024 6:44 am

blue wrote:Your statement of the "T2-delete" rule, doesn't mention "template[2] (anything)" directly, and likewise "Tk-delete", doesn't mention "template[k]".

But it mentions them semi-directly via the word "compatible". This is standard practice in definitions.
Any template[k] is the extension of a template[k-1] by a compatible template[1] for a different number.
This allows to give a uniform definition for all k.

blue wrote:Now my only question is: why does my code think that your T4 puzzles are actually in T3 ?
I'll check the code again, but I don't think it has bugs.

Too many eliminations?
An easy way to detect bugs (due to unjustified deletions) is to find a "puzzle with no solution" (when you know it has one).
.

by **blue** » Sun Oct 27, 2024 8:34 am

denis_berthier wrote:
blue wrote:Your statement of the "T2-delete" rule, doesn't mention "template[2] (anything)" directly, and likewise "Tk-delete", doesn't mention "template[k]".

But it mentions them semi-directly via the word "compatible". This is standard practice in definitions.
Any template[k] is the extension of a template[k-1] by a compatible template[1] for a different number.

But the reverse isn't always the case: that the extension of a template[k-1] by a compatible template[1] for a different number, is (still) a member of the relevant template[k] list. That was the point. I think you're being argumentative for no good reason.

denis_berthier wrote:Definition: two template[1] patterns for different digits ?n1 and ?n2 are said compatible if their respective sets or sequences of rc-cells don't overlap.
If you call these sets ci, i=1...9, and c'i, i=1..9, this means ci≠c'i for all i.

Definition: the template[2] pattern is defined by:
- two different digits ?n1 and ?n2
- two compatible templates[1], respectively for ?n1 and ?n2.

Here, you're defining compatiblity for (n1:t1) and (n2:t2) independently of whether (n1:t1,n2:t2) appears in the relevant template[2] list.

denis_berthier wrote:
blue wrote:Now my only question is: why does my code think that your T4 puzzles are actually in T3 ?
I'll check the code again, but I don't think it has bugs.

Too many eliminations?
An easy way to detect bugs (due to unjustified deletions) is to find a "puzzle with no solution" (when you know it has one).

"Too many eliminations" ... you would think so, but the "no solution" problem hasn't come up, even for your list of 100 T3 puzzles.
I'm still reviewing things ...

Cheers.

P.S.: For your "cbg-000" list, I get these results:

Code: Select all: T0 : 7489 (35.0%) T1 : 3630 (17.0%) T2 : 1916 ( 9.0%) T3 : 8340 (39.0%)

That seems to be in line with your results for the larger list.

Website · by **denis_berthier** » Sun Oct 27, 2024 9:05 am

blue wrote:
denis_berthier wrote:
blue wrote:Your statement of the "T2-delete" rule, doesn't mention "template[2] (anything)" directly, and likewise "Tk-delete", doesn't mention "template[k]".

But it mentions them semi-directly via the word "compatible". This is standard practice in definitions.
Any template[k] is the extension of a template[k-1] by a compatible template[1] for a different number.

But the reverse isn't always the case: that the extension of a template[k-1] by a compatible template[1] for a different number, is (still) a member of the relevant template[k] list. That was the point. I think you're being argumentative for no good reason.

I don't understand what you mean by "relevant list". If you mean that they are compatible with the grid data (i.e. the current resolution state), all the template[k] instantiations I ever consider are a priori compatible with the grid data - until they are eventually proven to be impossible.

blue wrote:
denis_berthier wrote:
blue wrote:Now my only question is: why does my code think that your T4 puzzles are actually in T3 ?
I'll check the code again, but I don't think it has bugs.

Too many eliminations?
An easy way to detect bugs (due to unjustified deletions) is to find a "puzzle with no solution" (when you know it has one).

"Too many eliminations" ... you would think so, but the "no solution" problem hasn't come up, even for your list of 100 T3 puzzles.

So, considering our common results below, this suggests:
- either you have a bug and it is localised in your templates[4];
- or I miss some eliminations in T4 (I've already checked my code several times, but I'll do it again).

blue wrote:P.S.: For your "cbg-000" list, I get these results:
Code: Select all
T0 : 7489 (35.0%) T1 : 3630 (17.0%) T2 : 1916 ( 9.0%) T3 : 8340 (39.0%)

That seems to be in line with your results for the larger list.

Same as me.
.

The New Sudoku Players' Forum

Templates as patterns

Re: Templates as patterns

Re: Templates as patterns

Re: Templates as patterns

Re: Templates as patterns

Re: Templates as patterns

Re: Templates as patterns

Re: Templates as patterns

Re: Templates as patterns

Re: Templates as patterns

Re: Templates as patterns

Re: Templates as patterns

Re: Templates as patterns

Re: Templates as patterns

Re: Templates as patterns

Re: Templates as patterns