Robert's puzzles 2020-10-26

Post puzzles for others to solve here.

Re: Robert's puzzles 2020-10-26

Postby denis_berthier » Fri Oct 30, 2020 6:42 am

Mauriès Robert wrote:Hi Denis en Space,
It is a pity that your general debate, which has nothing to do with this thread, has not been the subject of a separate thread.
The original subject is totally drowned out and I doubt it will be easy for a newcomer to find his way around!


Hi Robert,
A thread sliding away from its original topic - this happens so frequently that we no longer notice.
One way out of this is changing the title of the thread (i.e. the title of your first post) so that it reflects the content - it's up to you. I've done it occasionally in some of my threads.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: Robert's puzzles 2020-10-26

Postby Mauriès Robert » Fri Oct 30, 2020 7:40 am

Hi Space,

SpAce wrote:
Mauriès Robert wrote:Don't forget that I reason like a sudokist who does pencil marking, so you have to work on the puzzle physically!

I don't see how that's an excuse :) Don't we all reason like sudokists? Yet some notations are understandable without consulting the grid physically and reworking the logic oneself. Yours isn't at all. It's VERY tedious to follow, especially in more complex cases.


When I represent an anti-track by the following expression
P'(5r2c3) = {-5r2c3, 47r12c3, 47r2c38, 25r2c5, 4r9c1, 8r9c7, 25r9c5, 2r5c6, 24r6c79, 5r23c1, 5r5c9, 8r4c8,...}.
you have understood, without any doubt, that this is the (partial) set of candidates or group of candidates composing this anti-track (I had forgotten 47r2c78, I corrected) and not the set of links to follow to identify them, and that to understand it I give the puzzle on which the colour marking is made. I add that the order of the elements indicated is the one in which I made the colour marking.
So yes, it requires an effort to look at the puzzle to understand it, just as it requires me to look at the puzzle to understand any other form of textual expression given by others.
But, I receive your criticisms positively, so I give you the grahique corresponding to the construction of this anti-track, and I would like you to give me the corresponding TM matrix so that I can learn how to do it.
Cordialy
Robert

Code: Select all
             
(-5r2c5)=> ->47r2c38->25r2c5---------------------->2r5c6->24r6c79->8r4c8
          |\                                     /               /
          |  ->47r12c3->(4r9c1->8r9c7)->25r9c5->                /
          |                        \                           /
          |                          ->-----------------------/
          |                                                  /
          ->5r23c1->5r5c9->---------------------------------
Last edited by Mauriès Robert on Fri Oct 30, 2020 7:33 pm, edited 2 times in total.
Mauriès Robert
 
Posts: 585
Joined: 07 November 2019
Location: France

Re: Robert's puzzles 2020-10-26

Postby SpAce » Fri Oct 30, 2020 6:27 pm

Mauriès Robert wrote:When I represent an anti-track by the following expression
P'(5r2c3) = {-5r2c3, 47r12c3, 47r2c38, 25r2c5, 4r9c1, 8r9c7, 25r9c5, 2r5c6, 5r23c1, 5r5c9, 8r4c8,...}.
you have understood, without any doubt, that this is the (partial) set of candidates or group of candidates composing this anti-track (I had forgotten 47r2c78, I corrected) and not the set of links to follow to identify them, and that to understand it I give the puzzle on which the colour marking is made.

Yes, but none of that directly indicates how the individual parts of the anti-track have been determined. It's up to the reader to either trust the author or work it out on the grid, and the latter is not always trivial. For example, this anti-track is far from it.

Most critically, it took me a while to see what gave birth to the last element 8r4c8. It would have been easy if I'd seen that the corresponding SIS/CSP-variable was 8s in box 6. Nothing in your notation told me that, so I had to figure it out. It wasn't hard, but it wasn't obvious either. Checks like that take time, and I don't like to waste mine. That's why I don't like to read notations that give me no choice.

I add that the order of the elements indicated is the one in which I made the colour marking.

That helps a bit, of course, but not all the way. Btw, a minor detail: technically you shouldn't call it a set if the elements are ordered. It's a list or a tuple.

So yes, it requires an effort to look at the puzzle to understand it, just as it requires me to look at the puzzle to understand any other form of textual expression given by others.

There's a crucial difference, though. With enough experience it's possible to read complete notations without looking at the grid, because they have enough information to imagine what the relevant parts of the grid look like. With yours it's impossible, no matter how much experience one has, because there's simply not enough information. That's partly true about Denis' notation as well, but not nearly as critically.

But, I receive your criticisms positively

Glad to hear that! I definitely give it positively as well.

so I give you the grahique corresponding to the construction of this anti-track, and I would like you to give me the corresponding TM matrix so that I can learn how to do it.

Hidden Text: Show
Code: Select all
             
(-5r2c3)=> ->47r2c38->25r2c5---------------------->2r5c6->24r6c79->8r4c8
          |\                                     /               /
          |  ->47r12c3->(4r9c1->8r9c7)->25r9c5->                /
          |                        \                           /
          |                          ->-----------------------/
          |                                                  /
          ->5r23c1->5r5c9->---------------------------------


I'm glad to hear that too. However, I suggest you start with easier examples. This is pretty complex logic, and the corresponding matrix is not trivial. In fact, it's not possible to write it as a simple TM because of the subset nodes. It's only possible if we don't attempt to break them into individual candidates, which makes it easier to understand anyway (and it corresponds with your logic directly). In that case the TM would look like:

10x10 TM (with groups and subsets as nodes): Show
Code: Select all
 5r2c3 47r12c3
 . . . 4r78c3  4r9c1
 . . . . . . . 4r9c7 8r9c7
 5r2c3 . . . . . . . . . . 47r2c38
 . . . . . . . 4r9c5 8r9c5 4|7r2c5 25r29c5
 . . . . . . . . . . . . . . . . . 2r6c5 . 24r6c79
 5r2c3 . . . . . . . . . . . . . . . . . . . . . . 5r23c1
 . . . . . . . . . . . . . . . . . . . . . . . . . 5r5c1  5r5c9
 . . . . . . . . . . 8r5c7 . . . . . . . . 8r6c79  . . .  8r5c9 8r4c8
 5r2c3 . . . . . . . . . . . . . . . . . . . . . . . . . . . .  8r1c8
=====================================================================
+5r2c3

Note that it doesn't use 2r5c6 because it's not needed. The SIS in the last line is derived from the UR, which you mentioned earlier. It also makes it explicit that the naked pair 25r29c5 is used -- that's missing from your graphic which only lists the two cells separately (which is kind of confusing). Otherwise it should correspond with your graphic.

I guess that would be an S-braid, but I'm not sure how its length should be determined with those subsets. I think it's between 10-14 anyway. (Denis, can you tell what it's exactly? Btw, I guess the conclusion in your chains should be negative: -47 r2c3.)

If we want to break the subset-nodes into their components, then it becomes a block triangular matrix (BTM), which contains several ORed TMs.

14x14 BTM (with groups as nodes): Show
Code: Select all
 5r2c3 7r2c3 4r2c3
 . . . 7r1c3 4r1c3
 . . . . . . 4r78c3  4r9c1
 . . . . . . . . . . 4r9c7 8r9c7
 . . . . . . . . . . 4r9c5 8r9c5 . . . . . . 5r9c5 2r9c5
 5r2c3 . . . . . . . . . . . . . 7r2c3 4r2c3 . . . . . .
 . . . . . . . . . . . . . . . . 7r2c8 4r2c8 . . . . . .
 . . . . . . . . . . . . . . . . 7r2c5 4r2c5 5r2c5 2r2c5
 . . . . . . . . . . . . . . . . . . . . . . . . . 2r6c5 2r6c7 2r6c9
 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4r6c7 4r6c9
 5r2c3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5r23c1
 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5r5c1 . 5r5c9
 . . . . . . . . . . . . . 8r5c7 . . . . . . . . . . . . 8r6c7 8r6c9 . . . . 8r5c9 8r4c8
 5r2c3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8r1c8
========================================================================================
+5r2c3

BTMs are much more complex and harder to read and write than TMs. I don't even guarantee the correctness of mine. (Non-degenerate) BTMs indicate that OR-logic is needed no matter which way you traverse the logic. TMs have pure AND-logic when reading downwards, and pure OR-logic when reading upwards.

Anyway, I'm happy to help if you're interested in learning about matrices. Like I said, I would suggest starting with simpler examples. Btw, Cenoman is the real master of matrices. I learned from him.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: Robert's puzzles 2020-10-26

Postby Mauriès Robert » Fri Oct 30, 2020 7:45 pm

Thank you Space, I will think about it.
Robert
Mauriès Robert
 
Posts: 585
Joined: 07 November 2019
Location: France

Re: Robert's puzzles 2020-10-26

Postby SpAce » Fri Oct 30, 2020 11:59 pm

Mauriès Robert wrote:Thank you SpAce, I will think about it.

No problem. Here's a slightly different version of the first matrix:

10x10 TM (with subsets as nodes): Show
Code: Select all
 5r2c3 5r23c1
 . . . 5r5c1 . 5r5c9
 5r2c3 . . . . . . . 47r2c38
 5r2c3 . . . . . . . . . . . 47r12c3
 . . . . . . . . . . . . . . 4r78c3  4r9c1
 . . . . . . . . . . . . . . . . . . 4r9c7 8r9c7
 . . . . . . . . . . 4|7r2c5 . . . . 4r9c5 8r9c5 25r29c5
 . . . . . . . . . . . . . . . . . . . . . . . . 2r6c5 . 24r6c79
 . . . . . . . 8r5c9 . . . . . . . . . . . 8r5c7 . . . . 8r6c79  8r4c8
 5r2c3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8r1c8
======================================================================
+5r2c3

I rearranged some rows to get the longest possible continuous chain (starting at row 4). I think it would make it easier to write as a braid. In fact, if 47r2c5 and 8r5c9 were eliminated, the first three rows would be unnecessary and it would become an S-whip. Here's a pseudo-braid for that matrix:
{5r2c3 5r23c1} - {5r5c1 5r5c9} -- {5r2c3 47r2c38} -- {5r2c3 47r12c3} - {4r78c3 4r9c1} - {4r9c7 8r9c7} - {8r9c5 25r29c5} - {2r6c5 24r6c79} - {8r6c79 8r4c8} - UR{8r1c8 .} => +5 r2c3 (or -47 r2c3)

Something like that might be an easy option for you to notate your anti-tracks a bit more understandably yet relatively compactly (if Denis doesn't mind such abuse of his notation). In this case one could also replace the '.' with '5r2c3' to make it easier to read for us verity-people. It works because it's a z-candidate. If the last CSP-variable (i.e. the bottom row of the matrix) has only t-candidates besides the left-linking candidate (i.e. nothing in the first column), then the dot is the only option. (Denis, is that what you meant when you said that whips can catch more contradictions than chains?)

Here's the full logic graphically, with the core chain in the middle:

net diagram 1: Show
Code: Select all
           (5)r23c1 - r5c1 = (5)r5c9 ------------------------------------------- (8)r5c9
          //                                                                     ||
         //                               .------------------------------------- (8)r5c7
        //                               /                                       ||
(5)r2c3 = (74)r12c3 - r78c3 = r9c1 - (4=8)r9c7 - (8)r9c5 = (52)r29c5 - r6c5 = (24-8)r6c79 = (8)r4c8 - (8)r1c8 =UR= (5)r2c3
        \\                         \             ||
         \\                         '----------- (4)r9c5
          \\                                     ||
           (47)r2c38 --------------------------- (4)r2c5
                     \                           ||
                      '------------------------- (7)r2c5

=> +5r2c3

It's a bit confusing with the bent SISs, though. Here's how I'd normally draw it:

net diagram 2: Show
Code: Select all
             (5)r23c1 - r5c1 = (5)r5c9 ------------------------------- (8)r5c9
            //                                                         ||
           //                               .------------------------- (8)r5c7
          //                               /                           ||
         //                               /      (52)r29c5 - r6c5 = (24-8)r6c79
        //                               /       ||                    ||
(5)r2c3 = (74)r12c3 - r78c3 = r9c1 - (4=8)r9c7 - (8)r9c5               (8)r4c8 - (8)r1c8
        \\                         \             ||                              ||
         \\                         '----------- (4)r9c5                        !UR(47)r12c38!
          \\                                     ||                              ||
           (47)r2c38 --------------------------- (4)r2c5                         (5)r2c3
                     \                           ||
                      '------------------------- (7)r2c5

=> +5r2c3

It doesn't show the core chain as clearly, but it's otherwise more in line with our typical net diagrams. It's also easier to read as a multi-kraken, if one wishes, though it would be easiest if it were written as one in the first place:

Double Kraken: 8b6, AAALS (24578)r29c5: Show
Code: Select all
(8)r4c8 - (8)r1c8 =UR= (5)r2c3
||
(8-5)r5c9 = r5c1 - r23c1 = (5)r2c3
||
(8)r5c7 - (8=4)r9c7 - r9c1 = r78c3 - (47)r12c3 = (5)r2c3
||
(84-2)r6c79 = r6c5 - (25)r29c5
                     ||
                     (4|7)r2c5 - (47)r2c38 = (5)r2c3
                     ||
                     (4)r9c5 - r9c1 = r78c3 - (47)r12c3 = (5)r2c3
                     ||
                     (8)r9c5 - (8=4)r9c7 - r9c1 = r78c3 - (47)r12c3 = (5)r2c3

=> +5r2c3

The kraken is the easiest to read for those who don't mind OR-logic and a bit of redundancy. No join points needed. Only linear chains in the branches. For the same reasons it's also much easier to write than other types of net diagrams.

All of these options are supported by the same matrix. They depict the same exact pattern, just from different points of view. With a bit of practice, one can read all of these and more directly from the matrix.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: Robert's puzzles 2020-10-26

Postby denis_berthier » Sat Oct 31, 2020 4:29 am

SpAce wrote:
Hidden Text: Show
Code: Select all
             
(-5r2c3)=> ->47r2c38->25r2c5---------------------->2r5c6->24r6c79->8r4c8
          |\                                     /               /
          |  ->47r12c3->(4r9c1->8r9c7)->25r9c5->                /
          |                        \                           /
          |                          ->-----------------------/
          |                                                  /
          ->5r23c1->5r5c9->---------------------------------

[...]
10x10 TM (with groups and subsets as nodes): Show
Code: Select all
 5r2c3 47r12c3
 . . . 4r78c3  4r9c1
 . . . . . . . 4r9c7 8r9c7
 5r2c3 . . . . . . . . . . 47r2c38
 . . . . . . . 4r9c5 8r9c5 4|7r2c5 25r29c5
 . . . . . . . . . . . . . . . . . 2r6c5 . 24r6c79
 5r2c3 . . . . . . . . . . . . . . . . . . . . . . 5r23c1
 . . . . . . . . . . . . . . . . . . . . . . . . . 5r5c1  5r5c9
 . . . . . . . . . . 8r5c7 . . . . . . . . 8r6c79  . . .  8r5c9 8r4c8
 5r2c3 . . . . . . . . . . . . . . . . . . . . . . . . . . . .  8r1c8
=====================================================================
+5r2c3

Note that it doesn't use 2r5c6 because it's not needed. The SIS in the last line is derived from the UR, which you mentioned earlier. It also makes it explicit that the naked pair 25r29c5 is used -- that's missing from your graphic which only lists the two cells separately (which is kind of confusing). Otherwise it should correspond with your graphic.

I guess that would be an S-braid, but I'm not sure how its length should be determined with those subsets. I think it's between 10-14 anyway. (Denis, can you tell what it's exactly? Btw, I guess the conclusion in your chains should be negative: -47 r2c3.)


I define the length of a chain, or, more generally, the size of any pattern, as the number of CSP-Variables it involves. Notice that, as a result, g-candidates count only for 1. Here, based only on the matrix: r1c3, r2c3, r9c1, r9c7, r2c3, r2c8, r2c5, r9c5, r6c7, r6c9, r23c1 (g-cand), r5c9, r4c8, r1c8/.? Total: 14

Notice that this writing is not yet explicit enough. I've played it the lazy way: some variables noted rc may indeed be block variables (the count will not be changed).
A way of improving the readability of matrices would be to add a column on the left with the explicit names of the csp-vars.


PS./ can you check the last line (I mean the 5r2c3): 5r2c3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8r1c8
Last edited by denis_berthier on Sat Oct 31, 2020 5:27 am, edited 3 times in total.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: Robert's puzzles 2020-10-26

Postby denis_berthier » Sat Oct 31, 2020 4:45 am

SpAce wrote:I rearranged some rows to get the longest possible continuous chain (starting at row 4). I think it would make it easier to write as a braid. In fact, if 47r2c5 and 8r5c9 were eliminated, the first three rows would be unnecessary and it would become an S-whip. Here's a pseudo-braid for that matrix:

{5r2c3 5r23c1} - {5r5c1 5r5c9} -- {5r2c3 47r2c38} -- {5r2c3 47r12c3} - {4r78c3 4r9c1} - {4r9c7 8r9c7} - {8r9c5 25r29c5} - {2r6c5 24r6c79} - {8r6c79 8r4c8} - UR{8r1c8 .} => +5 r2c3 (or -47 r2c3)
Something like that might be an easy option for you to notate your anti-tracks a bit more understandably yet relatively compactly (if Denis doesn't mind such abuse of his notation).

I don't own the / and {} symbols. - has always been used by everybody to notate links and in maths { } to notate sets.
If there's an UR, it's not an S-braid.
My main objection to this notation (though it's much better than Robert's) is, it still misses the most important information: the sequence of csp-variables - which can't always be reconstructed from the llcs and rlcs (sometimes it could be a row or a bloc).

As this information is necessarily available at the time each step is obtained, it would cost nothing more to make it explicit in the solution, which seems to lead to my notation. I mean, at each assertive step, the T&E procedure underlying the solution uses one and only one of the 4 Singles rule: that gives the csp-variable at this step.

As a side remark; I don't understand UR{8r1c8 .}. A UR lies on 4 rc-cells; all 4 should somehow appear in the notation.

SpAce wrote: If the last CSP-variable (i.e. the bottom row of the matrix) has only t-candidates besides the left-linking candidate (i.e. nothing in the first column), then the dot is the only option. (Denis, is that what you meant when you said that whips can catch more contradictions than chains?)

Yes, that's an example of it.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: Robert's puzzles 2020-10-26

Postby SpAce » Sat Oct 31, 2020 5:48 am

Hi Denis,

I just noticed your latest comments. Thanks for them. I'm replying here to your earlier ones first.

denis_berthier wrote:What do you call advanced whips? There are g-whips already, but they don't shorten the resolution paths. If you mean S-whips (i.e. with Subsets allowed as rlcs), their additional resolution power is not worth the effort to code them, considering their increased computational complexity - and they are not necessary for puzzles in T&E(1), i.e. all but 1/30,000,000 puzzles.

Ok. I didn't realize that S-whips weren't implemented in SudoRules. In that case I would just ask for a couple of notational examples of those (preferably with all naked, hidden, and super-hidden subsets as rlcs). Even if SudoRules doesn't use them and you don't think they're important, many human solvers use them. I'd like to know how such logic maps to your notation. For example, how would you write my pseudo-braid above as a real one? It has both naked and hidden subsets as rlcs, though obviously not super-hidden ones (since Robert doesn't use even live fishes, much less almost-ones). And yes, it also has a set of UR guardians as a CSP-variable as you noticed. I have no idea how you'd notate that.

Variety in SudoRules can better be seen in Subset rules, Oddagons, special cases of whips (bivalue-chains, z-chains, t-whips, typed versions of all the chains, ...)

Yes, I can find examples of all of those.

forcing-whips (that I never use because they are inefficient and inelegant)

Why do you think they're inelegant? Those of us who like verity patterns would probably disagree. If I've understood forcing whips/braids correctly, they're much closer to methods that many advanced human solvers like to use. It's a common method in TDP (conjugate tracks), and it's also somewhat similar to what I do with coloring. With that style one doesn't have to assume anything. Mostly you look for agreements (verities) between the two parities, but it can also reveal a contradiction for one of them, so it can be fruitful in two ways. If you look for contradictions only, then you can find contradictions only -- and if you happen to try a true candidate, you'll never get one, which may take a while to realize.

Also, when you look for agreements for the two branches, you don't have to stop when you find the first result. You can keep going and find many more without losing any of the previous work. I think that's what Robert has been saying recently. Of course if you do that long enough, you'll eventually run into a contradiction for one of the parities (assuming no OR-branching is needed), and that solves the whole pattern, including the previously found agreements. The biggest benefit of the two-pronged approach is that the contradiction can happen for either parity, and even if you don't find one, you may still get useful results.

exotic (and very rare) patterns (sk-loops, J-Exocets), uniqueness rules (for those who like that),

Good to know SudoRules has those too, although I'm the most interested in the patterns that are unique to it. For example:

W*-whips for some extreme puzzles...

I guess those involve some kind of nesting. That would make them interesting, though possibly incomprehensible for me at this time. At some point I'd like to see an example. I think you used them for some hard puzzle recently, but chose not to display the full notation.

AND anyone can extend it to code his own rules; you should give that a try.

Not likely in the near future, but I'll keep that in mind. I've been avoiding any sort of sudoku coding so far, except for a basic solver I once did. But, I think I will at least try and run SudoRules in the not so distant future. I expect it to work well on a Mac, since you use that too.

SpAce wrote:For me a second miracle is that they have very different computational complexities, and to the whip's advantage. Why exactly is that?

No second miracle here, but something perfectly clear to me.
Before you get a whip/braid, you have to build partial-whips/braids, which have a pending rlc. Complexity arises at the time you extend them from length n to n+1.
And what counts here is the branching factor from the last rlc (i.e. the mean number of possible next llcs):
- in whips, it is constant (in the mean), i.e. independent of the partial-whip length
- in braids, it increases linearly (still in the mean) with the length of the partial braid.
As a result, the mean relative complexity of partial-braids wrt partial-whips (or, in simpler terms, their relative numbers) is exponential with length.

Ok. I think I can understand that, at least from a software point of view. Not sure how well it applies to human solving, but I guess it could. I have to do more testing. The couple of times I recently did, it did indeed seem simpler (but slower) to stick to a continuous path, and the contradictions were easier to spot with less coloring clutter. However, they were targets for which I knew a whip existed, and I got lucky with my routing choices.

I'm still wondering what you do when your partial whip runs into a dead-end. Do you backtrack to a previous choosing point (and erase all the chain elements from the dead-end part) and try a different route? With my coloring system that would be kind of tedious. It's easier to just leave it all there and continue from a different place, but that quickly loses any notion of continuity.

SpAce wrote:For me it would seem logical that you'd get many more dead-ends if you only looked for whips, because it's the more specific type.

It sounds sensible and it may play some role, but the fact is, it doesn't turn out to be as important as the branching factor.

Ok. I have to trust you on that.

I had (and still have) no convincing way of explaining in advance why it turns out to be that way. That's why I sometimes call it a (laïc) "miracle". It's also related (but not in a systematic way) to the fact that non-confluence is very rare for whips. Without such a gain, I would probably have given up developing SudoRules long ago.
And all this is true not only of Sudoku, but of all the other logic puzzles I've tried - in spite of their very different types of constraints. Which leads me to think there may be some general explanation, it keeps lurking in my mind, but it still eludes me.

Well, this is interesting indeed.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: Robert's puzzles 2020-10-26

Postby denis_berthier » Sat Oct 31, 2020 7:39 am

SpAce wrote: I didn't realize that S-whips weren't implemented in SudoRules. In that case I would just ask for a couple of notational examples of those (preferably with all naked, hidden, and super-hidden subsets as rlcs).

There are examples in PBCS (not many because I had to find them manually). And W*-Whips is just one among several possibilities toi deal with inner chains.
Basically, for inner right-linking patterns, the notation has two possibilities:
- either write a capital letter A in its place (and after the full whip is written give the details of A as if it was an independent pattern
- to write the full pattern in its place (with embedded { } - which may make it hard to read)

SpAce wrote: it also has a set of UR guardians as a CSP-variable as you noticed. I have no idea how you'd notate that.

I'd certainly choose the first option


SpAce wrote:
denis_berthier wrote:forcing-whips (that I never use because they are inefficient and inelegant)

Why do you think they're inelegant?

It's difficult to follow two streams of reasoning at the same time.
Moreover, they are inefficient: I've never found one that couldn't be replaced by whips (in a different path).
Notice that a forcing-whip with two branches of lengths p1 and p2 MUST be assigned length p1+p2+1 for consistency reasons. (In case one branch is reversible, it makes a whip of that length).
As I said, they are in CSP-Rules, so anyone can use them if he likes them.


SpAce wrote:
denis_berthier wrote:W*-whips for some extreme puzzles...

I guess those involve some kind of nesting. That would make them interesting, though possibly incomprehensible for me at this time. At some point I'd like to see an example. I think you used them for some hard puzzle recently, but chose not to display the full notation.

A full exemple is given in PBCS and yes, I've used them occasionally here, but I don't like this kind of patterns.
They are not included in the current public version of CSP-Rules. They require some manual work and I didn't feel like to write the details of it in a "BASIC User Manual".


SpAce wrote:
denis_berthier wrote:AND anyone can extend it to code his own rules; you should give that a try.

Not likely in the near future, but I'll keep that in mind. I've been avoiding any sort of sudoku coding so far, except for a basic solver I once did. But, I think I will at least try and run SudoRules in the not so distant future. I expect it to work well on a Mac, since you use that too.

CSP-Rules is machine independent.
It includes pre-complied versions of CLIPS for both Windows and Unix. On the Mac, due to safety reason, if you're running Catalina, you'll probably have to download it and recompile it: see the "README.md" on GitHub.


SpAce wrote:I'm still wondering what you do when your partial whip runs into a dead-end. Do you backtrack to a previous choosing point (and erase all the chain elements from the dead-end part) and try a different route? With my coloring system that would be kind of tedious. It's easier to just leave it all there and continue from a different place, but that quickly loses any notion of continuity.

Are you speaking of a manual solver or of SudoRules?
A manual solver can do as he wants - which may lead him to longer chains than necessary. However, as most puzzles can be solved with very short whips, it's not rational to pursue very long ones.
As for SudoRules, the internal workings are those of the CLIPS inference engine, guided by the priorities assigned to the rules. Apart from this last (strong) restriction, it's conceptually random. For efficiency reasons, it's essential not to change this randomness.
To make this more concrete, a usual solver will try r1c1, r1c2, ... in this order (or some other fixed order). There's no way to make SudoRules follow a fixed order. (There's however now a way to make SudoRules try a given set of candidates.)
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: Robert's puzzles 2020-10-26

Postby SpAce » Sat Oct 31, 2020 7:58 am

denis_berthier wrote:I define the length of a chain, or, more generally, the size of any pattern, as the number of CSP-Variables it involves. Notice that, as a result, g-candidates count only for 1.

I totally agree with that. It matches the number of truths in set logic.

Total: 14

That's what I thought, too. The 14x14 BTM makes it explicit.

A way of improving the readability of matrices would be to add a column on the left with the explicit names of the csp-vars.

I agree, and I quite often do that (also for columns). I normally use Allan Barker's notation (even though the Ns are weird) because it stands out and reminds that all chains and nets have counterparts in set logic:

10x10 TM: Show
Code: Select all
5B1  : 5r2c3 5r23c1
5R5  : . . . 5r5c1 . 5r5c9
2N38 : 5r2c3 . . . . . . . 47r2c38
12N3 : 5r2c3 . . . . . . . . . . . 47r12c3
4B7  : . . . . . . . . . . . . . . 4r78c3  4r9c1
9N7  : . . . . . . . . . . . . . . . . . . 4r9c7 8r9c7
29N5 : . . . . . . . . . . 4|7r2c5 . . . . 4r9c5 8r9c5 25r29c5
24R6 : . . . . . . . . . . . . . . . . . . . . . . . . 2r6c5 . 24r6c79
8B6  : . . . . . . . 8r5c9 . . . . . . . . . . . 8r5c7 . . . . 8r6c79  8r4c8
*UR  : 5r2c3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8r1c8  :UR(47)12N38
============================================================================
      +5r2c3

14x14 BTM: Show
Code: Select all
5B1 : 5r2c3 5r23c1
5R5 : . . . 5r5c1 . 5r5c9
2N3 : 5r2c3 . . . . . . . 7r2c3 4r2c3
2N8 : . . . . . . . . . . 7r2c8 4r2c8
2N3 : 5r2c3 . . . . . . . . . . . . . 7r2c3 4r2c3
1N3 : . . . . . . . . . . . . . . . . 7r1c3 4r1c3
4B7 : . . . . . . . . . . . . . . . . . . . 4r78c3  4r9c1
9N7 : . . . . . . . . . . . . . . . . . . . . . . . 4r9c7 8r9c7
9N5 : . . . . . . . . . . . . . . . . . . . . . . . 4r9c5 8r9c5 5r9c5 2r9c5
2N5 : . . . . . . . . . . 7r2c5 4r2c5 . . . . . . . . . . . . . 5r2c5 2r2c5
2R6 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2r6c5 2r6c7 2r6c9
4R6 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4r6c7 4r6c9
8B6 : . . . . . . . 8r5c9 . . . . . . . . . . . . . . . . 8r5c7 . . . . . . 8r6c7 8r6c9 8r4c8
*UR : 5r2c3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8r1c8  :UR(47)12N38
=============================================================================================
     +5r2c3

Of course the nrc-notation could be used too. The corresponding CSP-variables in the same order:

{b1n5, r5n5, r2c3, r1c3, r2c3, r1c3, b7n4, r9c7, r9c5, r2c5, r6n2, r6n4, b6n8, UR:r12c38}

PS./ can you check the last line (I mean the 5r2c3): 5r2c3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8r1c8

I'm not sure what you mean. Was it only the missing UR-reference or something else?

If there's an UR, it's not an S-braid.

Ah yes, of course. I would have guessed that but forgot the UR when I wrote it. What is it then?

My main objection to this notation (though it's much better than Robert's) is, it still misses the most important information: the sequence of csp-variables - which can't always be reconstructed from the llcs and rlcs (sometimes it could be a row or a bloc).

You're right. I tried to keep it as simple and readable as possible, but didn't quite think it through. When the z- and t-candidates aren't listed, the CSP-variable can't be reliably derived from just the llcs and rlcs. Not sure what the best fix is, as there are several forces at play.

As this information is necessarily available at the time each step is obtained, it would cost nothing more to make it explicit in the solution, which seems to lead to my notation.

I agree. It does lead to your notation, as it would be too redundant and verbose to add to the simplified (and already longer) version I suggested. Yet I'm not sure if Robert is willing to consider such drastic measures (but I don't want to assume anything). That's why I tried to keep it relatively close to his own.

As a side remark; I don't understand UR{8r1c8 .}. A UR lies on 4 rc-cells; all 4 should somehow appear in the notation.

Yes, that was just me being lazy. We're so used to specifying URs externally to keep notations shorter. I guess the full notation should be UR(47)r12c38{8r1c8 .}

SpAce wrote: If the last CSP-variable (i.e. the bottom row of the matrix) has only t-candidates besides the left-linking candidate (i.e. nothing in the first column), then the dot is the only option. (Denis, is that what you meant when you said that whips can catch more contradictions than chains?)

Yes, that's an example of it.

Ok! From that POV I agree with it.
Last edited by SpAce on Sat Oct 31, 2020 8:44 am, edited 2 times in total.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: Robert's puzzles 2020-10-26

Postby denis_berthier » Sat Oct 31, 2020 8:29 am

SpAce wrote:
denis_berthier wrote:I define the length of a chain, or, more generally, the size of any pattern, as the number of CSP-Variables it involves. Notice that, as a result, g-candidates count only for 1.

I totally agree with that. It matches the number of truths in set logic.

Except that, historically, it's the reverse. Allan introduced this absurd vocabulary of "Truths" because he apparently didn't want to refer to the existing vocabularies of that time: CSP-Variables or Base Sets (in the set covering approach).


SpAce wrote:
denis_berthier wrote:PS./ can you check the last line (I mean the 5r2c3): 5r2c3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8r1c8

I'm not sure what you mean. Was it only the missing UR-reference or something else?

the presence of 5r2c3


SpAce wrote:
denis_berthier wrote:If there's an UR, it's not an S-braid.

Ah yes, of course. I would have guessed that but forgot the UR when I wrote it. What is it then?

It's the result of T&E(S+UR, 1) applied to the target.
I'd never use a UR in T&E, because the result may not be uniquely defined (due to non-confluence when uniqueness rules are added).
I have no name for this. It's had oc reasoning with anything at hand. I'd call the whole chain butchering one's way to an exit. Well, in case there's a fire, you do whatever you can to get out, right?


SpAce wrote:
denis_berthier wrote:IMy main objection to this notation (though it's much better than Robert's) is, it still misses the most important information: the sequence of csp-variables - which can't always be reconstructed from the llcs and rlcs (sometimes it could be a row or a bloc).

You're right. I tried to keep it as simple and readable as possible, but didn't quite think it through. When the z- and t-candidates aren't listed, the CSP-variable can't be reliably derived from just the llcs and rlcs. Not sure what the best fix is, as there are several forces at play.

Even when all the- and z- candidates are present, there may be cases of ambiguity. Consider a pure bivalue-chain (no z- or t- candidate): how do you make a difference between c1n1{r1 r2} and b1n1{r1c1 r2c1} ?


SpAce wrote:
denis_berthier wrote:As a side remark; I don't understand UR{8r1c8 .}. A UR lies on 4 rc-cells; all 4 should somehow appear in the notation.

Yes, that was just me being lazy. We're so used to specifying URs externally to keep notations shorter. I guess the full notation should be UR(47)r12c38{8r1c8 .}

Yep, it's more explicit.
Last edited by denis_berthier on Sat Oct 31, 2020 10:50 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: Robert's puzzles 2020-10-26

Postby SpAce » Sat Oct 31, 2020 9:05 am

denis_berthier wrote:Except that, historically, it's the reverse. Allan introduced this absurd vocabulary of "Truths" because he apparently didn't want to refer to the existing vocabularies of that time: CSP-Variables or Base Sets (in the set covering approach).

Yeah, I never quite understood why it wasn't simply Base Sets and Cover Sets, especially since he uses those terms too. Well, it is what it is. Truths and Links is shorter, I guess.

the presence of 5r2c3

I still don't understand. It must be in the matrix even if it's not in the chain. It doesn't work otherwise, because the SIS does have both possibilities. If the matrix is read as a contradiction chain, then assuming the target (4 or 7 or -5 in r2c3) eliminates everything from the first column including this one, and following it from top down leaves the last row empty. Thus it works exactly as if there were a dot at the end of the chain. There's no reason to fix it as a contradiction chain, because that would remove other ways to read it (and it wouldn't make sense anyway). As written, the matrix supports all interpretations equally.

Even when all the- and z- candidates are present, there may be cases of ambiguity. Consider a pure bivalue-chain (no z- or t- candidate): how do you make a difference between c1n1{r1 r2} and b1n1{r1c1 r2c1} ?

Yes, but in that case it shouldn't matter much. Either one works, right? It's pretty much an arbitrary choice which one to use.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: Robert's puzzles 2020-10-26

Postby denis_berthier » Sat Oct 31, 2020 9:15 am

SpAce wrote:
denis_berthier wrote:Even when all the- and z- candidates are present, there may be cases of ambiguity. Consider a pure bivalue-chain (no z- or t- candidate): how do you make a difference between c1n1{r1 r2} and b1n1{r1c1 r2c1} ?

Yes, but in that case it shouldn't matter much. Either one works, right? It's pretty much an arbitrary choice which one to use.

Ah, right, bad example. Anyway, I don't like the idea of not specifying explicitly the main components of a whip (the csp-variables). If there are z- or t- candidates, only one of the two possibilities might work and the second almost work; you have to fully check the two if you don't guess the right one first. Multiply this by the length of the chain. It makes me tired, just thinking of it - especially if I know the information was available when the pattern was found.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: Robert's puzzles 2020-10-26

Postby yzfwsf » Sat Oct 31, 2020 11:13 am

Hi Denis:
I found that the chains in xsudo are very similar to yours, and the notation is also very similar. :)
yzfwsf
 
Posts: 845
Joined: 16 April 2019

Re: Robert's puzzles 2020-10-26

Postby denis_berthier » Sat Oct 31, 2020 1:09 pm

yzfwsf wrote:Hi Denis:
I found that the chains in xsudo are very similar to yours, and the notation is also very similar. :)


I never tried xsudo, because it runs only on Windows (and don't tell me that I can use Wine on my Mac; it doesn't work - Wine is 32-bit. BTW, I'd like to try your solver also, but I can't for the same reasons.)
I've seen enough of the solutions posted by Allan at that time; and we also had long talks about it. I've written somewhere a bilingual dictionary for translating back his vocabulary into mine.

What you say about the chains is not surprising at all: xsudo was largely inspired by the concepts in SudoRules - hidden by a change of vocabulary.
That being said, as far as I know, xsudo doesn't have explicit "chains". It only has covering sets (renamed Truths and Links). Some of these sets can be interpreted as chains, IF you choose some ordering of the "Truths". Doing this is not trivial.
But the real truth (and Allan almost admitted it) is, the underlying code relies on chains. This is indeed obvious if you consider his concept of "varying rank" (totally absurd if there is no underlying order). Unfortunately, no one has seen the code. But what we know is, xsudo doesn't even find all the chains (I gave a counter-example with g-whips). Nor does it find all the Truths-Links pairs of fixed length.

As for the notation, even when there's an interpretation as a chain, I don't see much in common between a set of "Truths" + a set of "Links" on his side, vs a sequence of triplets written as csp-var{llc rlc} on mine.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to Puzzles