Need advanced method to solve

Post the puzzle or solving technique that's causing you trouble and someone will help

Re: Need advanced method to solve

Postby yzfwsf » Fri May 08, 2020 2:12 am

AIC Type1:(5=4)r4c1-(4=2)r2c1-r2c4=(2-5)r3c4=5r5c4 => r5c1<>5 r5c3<>5 ;stte
aic.png
aic.png (33.58 KiB) Viewed 295 times
yzfwsf
 
Posts: 247
Joined: 16 April 2019

Re: Need advanced method to solve

Postby SpAce » Fri May 08, 2020 3:52 am

Hi yzfwsf,

yzfwsf wrote:AIC Type1:(5=4)r4c1-(4=2)r2c1-r2c4=(2-5)r3c4=5r5c4 => r5c1<>5 r5c3<>5 ;stte

That's the same chain I used. It's most likely the simplest solution available. Thanks for posting a picture of it!

4x4 TM: Show
Code: Select all
 5r4c1 4r4c1
       4r2c1 2r2c1
             2r2c4 2r3c4
 5r4c4             5r3c4
------------------------
-5r5c13

--
Edit. Typo corrected, thanks to yzfwsf.
Last edited by SpAce on Fri May 08, 2020 4:14 am, edited 1 time in total.
User avatar
SpAce
 
Posts: 2559
Joined: 22 May 2017

Re: Need advanced method to solve

Postby yzfwsf » Fri May 08, 2020 4:06 am

SpAce wrote:
Code: Select all
 
5r4c1 4r4c1
       4r2c1 2r2c1
             2r2c4 2r3c4
 5r4c4             5r3c4
------------------------
-5r4c13

I think there should be a typo here -5r4c13 => -5r5c13
yzfwsf
 
Posts: 247
Joined: 16 April 2019

Re: Need advanced method to solve

Postby SpAce » Fri May 08, 2020 4:14 am

yzfwsf wrote:I think there should be a typo here -5r4c13 => -5r5c13

Of course, thanks! Fixed.
User avatar
SpAce
 
Posts: 2559
Joined: 22 May 2017

Re: Need advanced method to solve

Postby denis_berthier » Fri May 08, 2020 4:25 am

SpAce wrote:
ghfick wrote:I tried your puzzle with each of these solvers. They each give essentially the same solution path.

Of course, because by default they all use the "simplest first" strategy, just like Denis' solver.

Same paths, really? Have you looked at the solutions?


SpAce wrote:
ghfick wrote:For me, learning the XY Chain was so valuable. It is definitely usable by humans and it is arguably 'easier' than many steps.

Yes, we know you love them. I almost never use them because nicer options are usually available. XY-Chains are usually long, tedious to read and write, and mostly actually less easy to find than other AIC-types (if you have a good technique to find any AICs). .

xy-chains are the most basic type of chains one can imagine. They were the starting point for all my more complex chains. They are very easy to find, even the long ones. Well, I guess it depends on what you are looking for.
I don't understand your point about the length of xy-chains. A few days ago, you said length didn't matter (no weird innuendo here).


SpAce wrote:Btw, in this case, the SudokuWiki's XY-Chain (9 strong links!) is one of the most inefficient chains I've seen in a long time. Most XY-Chains are inefficient anyway but this one is especially dumb:
(2=4)r2c1 - (4=5)r4c1 - (5=4)r4c8 - (4=5)r9c8 - (5=4)r9c9 - (4=5)r6c9 - (5=7)r6c6 - (7=5)r3c6 - (5=2)r3c4 => -2 r2c4,r3c2.

I hadn't tried to restrict SudoRules to xy-chains, but if I do, it finds a solution with two short ones: just one xy-chain[3] plus one xy-chain[6]:
Code: Select all
(solve ".....1289....695719.1.8.463...9127.8.9...8.26...6...9.3598246178..1569326127938..")
;;; starting from the PM
biv-chain-rc[3]: r2c1{n4 n2} - r3c2{n2 n7} - r8c2{n7 n4} ==> r1c2 ≠ 4, r2c2 ≠ 4
biv-chain-rc[6]: r3c2{n7 n2} - r2c1{n2 n4} - r4c1{n4 n5} - r4c8{n5 n4} - r6c9{n4 n5} - r6c6{n5 n7} ==> r6c2 ≠ 7, r3c6 ≠ 7
stte

Your conclusion should be that SudokuWiki is especially dumb here, not that xy-chains are.
Of course, less powerful techniques generally require longer chains and what we get here is indeed longer than my previous solution with 3D bivalue-chains (max length = 4). But the point is, for players who prefer working in the rc-space alone, disregarding bilocation (and this is a normal stance for beginners), this puzzle has a simple solution in it.


SpAce wrote:That's still 7 strong links and 4 digits. We can further streamline it by mixing in bilocal links:
(2=4)r2c1 - (4=5)r4c1 - r4c8 = r6c9 - r6c6 = r3c6 - (5=2)r3c4 => -2 r2c4,r3c2
That's 5 strong links and 3 digits -- clearly simpler, except for the mixed link types (but that shouldn't be a problem for anyone who uses chains regularly). Easier to read too without so many unnecessarily flip-flopping digits. Yet it's still a bit longer than my chain that had four strong links.
compressed variants: Show
Using the "3D" notation it can be written a bit shorter still (though the number of links remains the same):
(2=4)r2c1 - (4=5)r4c1 - b6p2=9 - r6=3c6 - (5=2)r3c4 => -2 r2c4,r3c2
With ALS-compression we can reduce it to three strong links:
(2=45)r24c1 - b6p2=9 - r6c6 = (52)r3c64 => -2 r2c4,r3c2
That's more than 60% shorter than the original XY-Chain in both characters and strong links.

I will not go into the details here. The purpose of any language (natural or artificial as in a notation for chains) is communication. This always implies some amount of redundancy and your goal of "compactness before all" seems to result from a misunderstanding of the higher purpose. The AIC notation is already illegible because it deals differently with the 4 types of CSP-Variables, but your "compression" makes it still worse.
As for your extrapolation that the resulting chain is "shorter", it's only a redefinition of length; nothing is shorter for real.
denis_berthier
2010 Supporter
 
Posts: 1672
Joined: 19 June 2007
Location: Paris

Re: Need advanced method to solve

Postby SpAce » Fri May 08, 2020 9:37 am

denis_berthier wrote:
SpAce wrote:
ghfick wrote:I tried your puzzle with each of these solvers. They each give essentially the same solution path.

Of course, because by default they all use the "simplest first" strategy, just like Denis' solver.

Same paths, really? Have you looked at the solutions?

Why do you quote me? It was Gordon who said that, and I didn't feel compelled to check his claims. Besides he didn't even mention your solver (which does have a much longer and thus considerably different path). My point stands: they all use the "simplest first" strategy, just like yours, even if their paths are different. The differences are due to different hierarchies and somewhat different techniques available, not different strategies. Simplicity is not an objective concept, obviously. Yours is the only one that uses the length of the chains as a measurement of simplicity, which makes it the most different (and the least efficient by far).

Now that I did look at the paths of Hodoku and SudokuWiki in detail (I don't know how to find any default path in Phil's solver, and unfortunately can't use the YZF-solver for the same reason as you), both of them start with the XY-Wing and XYZ-Wing and end with the same XY-Chain (Hodoku using the smarter version, of course). The differences in between are a result of Hodoku having UR earlier in the hierarchy, and not having WXYZ-Wing as a named pattern, while on the other hand having Sue-de-Coq ridiculously early in the hierarchy. If SDC is disabled, both use four moves (one different) to solve this, otherwise Hodoku uses six. In all cases only the last step is needed, so all the "simpler" techniques are unnecessary.

Btw, Hodoku's SDC actually uses the same cells as SudokuWiki's WXYZ-Wing, making it the smarter option because it yields many more eliminations with the same pattern (SudokuWiki misses that it's a loop / rank 0 pattern) -- however, in this case those extra eliminations make it spend two more unnecessary steps because of gaining access to techniques earlier in the hierarchy (an extra cost of "simplest first" strategy). Unlike SudokuWiki, it's actually impossible to make Hodoku solve this with just one XY-Chain (using the 'Next hint'), because it will report the useless XY-Wing as an XY-Chain first. It appears that SudokuWiki doesn't find XY-Wings as XY-Chains, which is illogical (like many other things in that solver and site) though somewhat useful. Hodoku does solve this with one AIC if XY-Chains are disabled (along with SDC and URs).

Like I said, your solver's path is very different from those. Not in a good way, imo, but that's a matter of taste.

xy-chains are the most basic type of chains one can imagine.

Then you should imagine harder ;) X-Chains are the simplest by far, using only a single digit and rcb-houses (no cells) for both strong and weak links, and having quite limited lengths. For a manual solver who's equally skilled in all chain types, they're also by far the easiest to find. I can usually see at a glance if X-Chains (or any single-digit techniques, i.e. fishes) are possible or not for each digit, so the search is quickly limited to potential digits only. Any capable software helper can highlight the candidates of a digit, which makes spotting the bilocal links and thus actual chains trivial in most cases. In p&p solving it takes a bit more effort to know where the bilocals are, but it's not difficult either (I learned all chaining stuff with p&p solving). The only advantage of XY-Chains is that, without digit highlighting or special pencil marks, bivalue cells are somewhat easier to spot than bilocal links, but even that advantage is gone if one solves without pencil marks.

They were the starting point for all my more complex chains. They are very easy to find, even the long ones.

They're easy to find if you look for them specifically, but why do that? If there are no XY-Chains available, you've just wasted time looking for them. Why limit yourself to a single chain type when you can find all with a single process just as easily? That's my point.

Well, I guess it depends on what you are looking for.

I rarely look for anything specifically, except maybe X-Chains if it's obvious those might be around. My process usually gives me many chain options with the same effort. Then I choose which ones I like to use and in which order. It all depends on my goals at the time (simplicity vs efficiency vs elegance...). If an XY-Chain fits the bill, I use one, but generally I end up with other options.

I don't understand your point about the length of xy-chains. A few days ago, you said length didn't matter.

No, I definitely didn't say that. I said: "there's no real difference in the difficulty of finding chains of various lengths", and I stand by that. However, length is surely a factor in determining the efficiency and elegance of a chain. If I can choose between a short and a long chain that do the same job, of course I choose the shorter one, unless it's way more complex otherwise.

SpAce wrote:Your conclusion should be that SudokuWiki is especially dumb here, not that xy-chains are.

I'm happy to conclude both ;) The length 9 chain was clearly SudokuWiki's mistake, but even the corrected one is still length 7, which is two more than my mixed-type version of length 5 (using the same cells).

Of course, less powerful techniques generally require longer chains and what we get here is indeed longer than my previous solution with 3D bivalue-chains (max length = 4). But the point is, for players who prefer working in the rc-space alone, disregarding bilocation (and this is a normal stance for beginners), this puzzle has a simple solution in it.

Normal perhaps, but it's a very poor stance for beginners too. Since X-Chains are the simplest type, it's best to start with them. Once the player understands and is able to find them, they can move on to multi-digit chains, starting with XY-chains as the simplest type of them. Once they understand those too, it's relatively simple to combine both into mixed-type chains. That process, combined with a good coloring system, pretty much guarantees that all of those chain types are equally easy in no time. Or at least it worked for me extremely well.

(And no, it certainly doesn't require playing on three or even four simultaneous grids in different spaces, though it's an educating exercise too. Btw, thanks for that idea. I rarely do that, and even more rarely use more than one space, but it's sometimes fun to solve purely in nr- or nc-space. Boxes are actually easier to use in those once you figure it out. All three spaces have exactly the same solving powers, just through different points of view. I have no idea what you need the bn-space for.)

On the other hand, it appears that some others who've clearly concentrated on XY-Chains since the get-go, keep struggling with other chain types even after many years. So understandably they keep telling everyone how great XY-Chains are. All that really tells is that they've never learned to find anything else very well. Does it prove that XY-Chains are the easiest to find? No. It only indicates that those players have probably missed proper chaining education early on, possibly because they've listened to bad advice.

I will not go into the details here. The purpose of any language (natural or artificial as in a notation for chains) is communication. This always implies some amount of redundancy and your goal of "compactness before all" seems to result from a misunderstanding of the higher purpose.

No, there's no misunderstanding :) Of course I know my compressed chains aren't the easiest to understand. Do you think you're the first one to point that out? They're not even meant to be. That's why I often provide multiple versions, including the language-agnostic matrix form. So, take your pick of those if you don't like my compressed chains. I write them mostly for myself, because it's more challenging thus more fun. It's also better for my own learning, and for those too, who'd like to learn the more intricate AIC nuances from correct examples.

FYI: there aren't that many even on this forum who can consistently write perfectly correct AICs no matter their complexity. I'm one of them, and it's exactly because I practice finding and writing complex chains even when they're not necessary. For that reason I'm not going to dumb them down just because someone doesn't like them. I can provide easier options, though, which I also frequently do.

The AIC notation is already illegible...

For you perhaps. The rest of us read it just fine :) I'm the first to admit that Eureka could be improved (or rather, it could have been designed a bit differently), but please try not to let your own biases exaggerate everything. Your own notations are probably far from perfect too, but I refrain from making comparisons until I've learned more about them. I'd recommend the same to you. Your criticism would be more interesting and to the point if you were as proficient with AICs as you are with your own system. I doubt you are. Truth is, for most practical purposes AICs and their more complex derivatives work extremely well, and their active users love them. Your bashing of them doesn't change those facts.

On the other hand, I don't see anyone using your system here, even though you've presented and marketed it heavily many years ago. Have you ever wondered why, if it's so superior? I don't have an answer, because like I said, I don't know your system well enough to have a strong opinion of it. One thing is for sure, though: it must be much harder to learn from free sources because I haven't yet (except for the simple biv-chains), despite seeing it around. It didn't take me much time at all to learn the principles of AICs (+ AIC-like krakens and nets) and then several languages to express them (Eureka, Nice Loop notation, implication chain notation, memory chain notation, net diagrams, matrices, boolean logic expressions, and conversions to/from set logic expressions). Of course there's been less incentive to learn your system because no one uses it here, but I've been known to learn even useless things just for fun -- unless it takes too much effort. So, it would be nice if it could be made more approachable, especially for us who already know AICs well.

As for your extrapolation that the resulting chain is "shorter", it's only a redefinition of length;

If you're talking about the compressed chains, I totally agree (which I already made clear in an earlier post). They were hidden for a reason, as they're not exactly comparable with anything. However, if you refer to the more relevant [7]XY-Chain vs [5]mixed-type-AIC question, there's of course no doubt that the latter is shorter. Hope you agree with that.

nothing is shorter for real.

That's false, of course. The actual text of the chain is definitely shorter, yet it contains the same amount of information. That has some value in most contexts. Personally I prefer not only to write but to read shorter chains as well. It's often much easier to see the big picture quickly from a shorter chain, even if it's more complex. That's one reason why I hate XY-Chains (and typically compress them mercilessly, if I have to use them).
User avatar
SpAce
 
Posts: 2559
Joined: 22 May 2017

Re: Need advanced method to solve

Postby denis_berthier » Fri May 08, 2020 11:32 am

SpAce wrote:
denis_berthier wrote:xy-chains are the most basic type of chains one can imagine.

Then you should imagine harder ;) X-Chains are the simplest by far, using only a single digit and rcb-houses (no cells) for both strong and weak links, and having quite limited lengths. For a manual solver who's equally skilled in all chain types, they're also by far the easiest to find. [...]The only advantage of XY-Chains is that, without digit highlighting or special pencil marks, bivalue cells are somewhat easier to spot than bilocal links, but even that advantage is gone if one solves without pencil marks.

OK for X-chains being simpler than xy-chains. This is one pattern I might add to SudoRules some day.
Actually, I was thinking of generic chains only (i.e. meaningful in any CSP). X-chains are not generic.

SpAce wrote:
denis_berthier wrote:They were the starting point for all my more complex chains. They are very easy to find, even the long ones.

They're easy to find if you look for them specifically, but why do that? If there are no XY-Chains available, you've just wasted time looking for them.

This is one thing you could say for any pattern. Why look for XWYZWings if there are none? And why look for kites? One just doesn't know in advance.

SpAce wrote:Why limit yourself to a single chain type when you can find all with a single process just as easily? That's my point.

Supposing one uses PMs, it's obvious to spot the potential components (bivalue rc-cells)
But which single process common to all the chain types are you referring to? If you mean colouring (as I guess), it's not the same process for whips and for braids. Whips have the immense advantage of continuity.
And it's not the same process either if you look only for bivalue chains or for xy-chains. You can't extend them if the next cells is not bivalue (res. rc-bivalue); this drastically limits the number of possible extensions.
Sure you can say it's all colouring, but there are great variations in the details and the complexity of the process.

SpAce wrote:
denis_berthier wrote:I don't understand your point about the length of xy-chains. A few days ago, you said length didn't matter.

No, I definitely didn't say that. I said: "there's no real difference in the difficulty of finding chains of various lengths", and I stand by that. However, length is surely a factor in determining the efficiency and elegance of a chain. If I can choose between a short and a long chain that do the same job, of course I choose the shorter one, unless it's way more complex otherwise.

That's what I meant.

SpAce wrote:
denis_berthier wrote:Of course, less powerful techniques generally require longer chains and what we get here is indeed longer than my previous solution with 3D bivalue-chains (max length = 4). But the point is, for players who prefer working in the rc-space alone, disregarding bilocation (and this is a normal stance for beginners), this puzzle has a simple solution in it.

Normal perhaps, but it's a very poor stance for beginners too. Since X-Chains are the simplest type, it's best to start with them. Once the player understands and is able to find them, they can move on to multi-digit chains, starting with XY-chains as the simplest type of them. Once they understand those too, it's relatively simple to combine both into mixed-type chains. That process, combined with a good coloring system, pretty much guarantees that all of those chain types are equally easy in no time. Or at least it worked for me extremely well.

Different people have different learning paths. I (and SudoRules) make no assumption about that. The player can choose what he wants.

SpAce wrote:And no, it certainly doesn't require playing on three or even four simultaneous grids in different spaces,

Where did I say that? The player chooses what he wants.

SpAce wrote:I have no idea what you need the bn-space for.

In practice, the bn-space isn't very useful. But if you look at some of the resolution paths I gave in the 2D-chains thread, some chains do appear in it.
In theory, it represents the contents of the CSP-Variables of type bn.

SpAce wrote: I don't see anyone using your system here, even though you've presented and marketed it heavily many years ago.

So, that's it. When someone uses the AIC notation, he merely uses it. But when I use my nrc-notation I market it. The good question should be why should everyone be pressured to use the AIC notation, as has always been the case in the three dead main forums?
Do you think this forum represents the real players? Many real players don't even know what a Triplet is. They use some form or another of T&E. And bickerings about notation is the last thing they care about.

SpAce wrote:
denis_berthier wrote:nothing is shorter for real.

That's false, of course. The actual text of the chain is definitely shorter, yet it contains the same amount of information. That has some value in most contexts.

I was not speaking of the text, but of the chain.
denis_berthier
2010 Supporter
 
Posts: 1672
Joined: 19 June 2007
Location: Paris

Re: Need advanced method to solve

Postby SpAce » Sun May 10, 2020 11:28 am

Hi Denis,

Sorry it took a while to get back to this.

denis_berthier wrote:OK for X-chains being simpler than xy-chains. This is one pattern I might add to SudoRules some day.

I'm really surprised that you don't already have it. So, how do you find even the simplest Turbot Fishes, i.e. Skyscrapers, Kites, and Cranes? Do you have them programmed as special patterns or finned mutant fishes or what? Or don't you use them at all (which would seem weird considering how prevalent and effective they are in simpler puzzles)? Of course you never need X-Chains as chains if you have an excellent fish finder (because those patterns can always be seen as fishes), but fishes are almost always more complicated points of view than simple chains, imo. (Similarly you never need any chains at all if you have an excellent generic set logic engine, but those are even more complicated and less intuitive points of view.)

Actually, I was thinking of generic chains only (i.e. meaningful in any CSP). X-chains are not generic.

What does that mean? How are XY-Chains any more generic? Sorry, but I'm not an expert in generalized CSP thinking.

SpAce wrote:They're easy to find if you look for them specifically, but why do that? If there are no XY-Chains available, you've just wasted time looking for them.

This is one thing you could say for any pattern.

Yes, but it's not equally relevant to all patterns. Some are relatively easy to spot without much effort, and those are worth looking for specifically. Others generally aren't worth it, unless they can't be found with generalized methods and yet would be very helpful or even practically required to solve a puzzle (e.g. JExocet, MSLS, SK-Loops in very hard puzzles; non-chain fishes sometimes).

Why look for XWYZWings if there are none?

Well, I never do. There's hardly a reason to look for WXYZ-Wings specifically. They're too varied and complicated patterns to spot easily and consistently, and not often enough available anyway. Thus I don't waste time on them. Instead I find them as ALS chains (like any other ALS-XZ pattern) using my normal process if need be (the same with Sue-de-Coqs which I find as ALS loops, like any other doubly-linked ALS-XZ). I rarely look for any of the simpler "wings" either, except X-Wings (which is a misnomer anyway). The only exceptions are W-Wing, Y-Wing, and rarely XYZ-Wing, and only in the simplest non-basic puzzles where I've failed to spot URs, X-Wings, and Turbots, and I'm expecting that at least one of those above is likely available and a key to solving the puzzle. Even then I'd probably find the solution faster with a generalized chain, but sometimes I just want to practice my pattern recognition skills.

And why look for kites?

That's actually one of the patterns that are so easy to spot (often even without pm) that it's definitely worth checking, along with the other Turbot Fishes and even longer X-Chains. Even though my generalized process will find them too, it's usually more efficient to first check the availability of X-Chains specifically. The only things even easier than X-Wings and Turbot Fishes (including Kites) are URs, BUGs, and most BUG-Lites (which I usually check before them). It would be a sin to not check those first before any more elaborate methods. (Yes, I know you don't generally use uniqueness methods. Yet for a typical manual solver they're invaluable, and there's no objective reason to avoid them if you trust your puzzle provider. That said, anyone is free to choose whatever they want for whatever reasons they like, so no need to debate that.)

One just doesn't know in advance.

Half true. It's true that you can't know in advance if there's a Kite around, but you can know which digits even have that possibility. That speeds up the checking process immensely, especially in simpler puzzles where many (or all) digits can usually be discarded immediately. There's a neat trick to see very quickly which digits definitely can't have any single-digit eliminations. It was originally invented by Keith and introduced to me by Yogi. In practice it's very easy and fast, though it's not necessarily obvious if you look at Yogi's elaborate ways to use it. I use it in almost all puzzles whether I need it or not, because there's practically no overhead if you do it while solving. Even if you do it as a separate check, it only takes a couple of minutes.

For example, in this puzzle it took me less than two minutes to see that 4 and 7 were the only digits that had any potential for single-digit eliminations (including complete template checks). Then another minute of staring at the candidates of those two digits convinced me that neither had any X-Chains available (including grouped variants). Thus no Kites or Skyscrapers either, of course. If I bothered, I could also check relatively quickly if they had any (non-chain) basic Swordfishes or Jellyfishes, but I rarely do because it takes more effort (especially for finned variants) and is seldom productive.

Besides those larger basic fishes, the two digits might still have complex fishes (probably not finless ones, though, because most of them would have been revealed as (grouped) X-Chains already), or no-fish template eliminations, available. Naturally I don't even try to find those manually (unless there's some very obvious pattern that hints towards Frankens or Mutants). In fact, it turns out that this puzzle state is completely dry of any single-digit potential. That I can only know for sure by asking Hodoku, but for all practical purposes, I'd already determined it manually in 3-4 minutes. That saves a lot of time and effort because I wouldn't need to even consider such patterns for now (until further eliminations of digits 4 or 7 which might yet reveal single-digit patterns; all the other digits are dead for good).

Supposing one uses PMs, it's obvious to spot the potential components (bivalue rc-cells)

Yes, like I said, that's the one advantage XY-Chains have, but it only matters if you're using the most basic pencil marks. If you're solving on paper and have to add pencil marks manually, you can just as well mark the bilocals while you're at it. They come as a byproduct when you search for hidden singles and pairs anyway. Or if you're solving with a software helper, it should be able to highlight the candidates of a digit, or even better, mark the bilocals directly (like Robert Mauriès' solver seems to do). In any serious solving you simply have to know the bilocals so it pays off to learn to see them early, one way or another.

Furthermore, in my experience it's best to check for XY-Chains specifically if there are relatively few bivalue cells around, because it limits the possible paths (at least you know sooner if none exist). Otherwise the (weak) linking possibilities explode, and it's probably more productive to search for generic chains right away. It's a bit ironic, actually, since in the latter case XY-Chains are almost certainly available, but the productive ones might be harder to find. Mixed-type chains probably yield results faster, partly because (at least my) coloring methods work better with them.

But which single process common to all the chain types are you referring to? If you mean colouring (as I guess),

Yes, I mean coloring, more specifically my implementation of David Bird's GEM. I wrote a tutorial of the basic concepts here. It also has a link to David's original documentation. I'm quite convinced that it's the most powerful humanly-applicable coloring system to find chains and nets in sudoku.

My GEM coloring for this puzzle: Show
gemsimple.png
gemsimple.png (74.42 KiB) Viewed 251 times

Choosing the bilocal/bivalue 45s as the seed (par candidates) was obvious, and the rest was just as easy after that. The coloring could still be continued, but there's no need. In fact I could have stopped earlier when the relevant eliminations were found.

it's not the same process for whips and for braids. Whips have the immense advantage of continuity.

I still don't know what whips and braids are. I'm hoping you could give a simple explanation that I could hopefully relate to what I already know. Please don't tell me to read PBCS again. It's great that you've published it for free, and I'm sure it has lots of good information, but my head starts to ache with all those mathematical symbols :) I told the same to Robert about TDP (which is very a simple system, though it wasn't obvious by looking at the complicated documentation). I lose my interest quickly if I have to go through tons of mathematical theory just to see that the actually relevant bits could have been explained in a few paragraphs and a couple of illustrative pictures. What I really need is the big picture in plain language, the hierarchy of related components, and explained examples of each of those components.

For example, to get into your system I'd need to understand the overarching philosophy behind it, and how the various components (the zillion chain types) are related to each other and what value each one adds. Otherwise it just looks like a huge mess to me, and I wouldn't really know where to even start. Details are irrelevant to me until I have a grasp of the big picture. For example, that's why I delayed studying MSLS until I understood what it really was and how it was related to other patterns. After I did, it was a piece of cake. I'm pretty sure most if not all of the concepts and chain types you're using have counterparts on the AIC side of things, and understanding those relationships would be the fastest track for me to learn your system. I guess you can't really help with that directly, but I probably don't need a whole lot of guidance to be able to draw the mappings myself -- unless the concepts are in fact much more different than I suspect.

Of course the greatest discovery would be to see that your system actually has some useful concepts and techniques for which we don't have equivalent counterparts. I don't think either of us can know that at the moment, because it requires very intimate understanding of both systems, and we both are experts in one or the other only (though you obviously know more about AICs than I know about your system). I'd like to change that by learning yours as well. Like I said, I just really don't know where to start.

In practice, the bn-space isn't very useful. But if you look at some of the resolution paths I gave in the 2D-chains thread, some chains do appear in it. In theory, it represents the contents of the CSP-Variables of type bn.

Ok, I'll take a look at those. Btw, I've reconsidered my position about the box coordinates. I think I mostly agree with what you said in an earlier post:

At the time of HLS, I hesitated about writing b4n3{r4c1 r5c3} or b4n3{s1 s6} . The second seems to be simpler. However, it makes it very difficult to see the link with the previous and next CSP-Variables. In the notation I finally chose, you have the 3 coordinates.
Another reason is that the p or s coordinate is of no use. There's no bs (bp for you) duality, contrary to the rc duality.

You're right that the box coordinates and rc-coordinates are difficult to use together. In our system the bp-coordinates are the most useful for describing box-based ALS-nodes, but if your system doesn't use ALSs, I guess that doesn't help there. An advantage of your notation is that it always makes it clear when a box-based strong link (sorry, I have to use terms I understand) is being used even though the actual coordinates are rc. That's probably optimal for linking purposes, though it would still be nice to visualize the box positions. In our system the box is only implied (r4c1 = r5c3) unless the link is written b4p1 = b4p6 (which no one does). Your system could, however, combine the best of both worlds. You could for example write it: b4n3{s1:r4c1 s6:r5c3} (if you insist on using 's' which is not exactly intuitive; what does it stand for?). That way it would have both coordinates, one for internal use and the other for external linking.

So, that's it. When someone uses the AIC notation, he merely uses it. But when I use my nrc-notation I market it. The good question should be why should everyone be pressured to use the AIC notation, as has always been the case in the three dead main forums?

I think you're missing the point. I'm not pressuring you to do anything. I'm glad you've become active lately and have started posting solutions with your notation! That gives me at least a chance to learn it eventually (and not just the simple biv-chains).

My point was just that there must be a reason why one notation has become popular and another hasn't, and suggested it could have something to do with approachability. Perhaps you could do something about that to level the playing field? Since you're posting chains with your notation, wouldn't it be better that others could actually read them? The same thing with your terms, such as 'whips' and 'braids'. You can't just expect people to know what they mean. Perhaps once upon a time people were more familiar with them, but I doubt many here are now. At least I'm not.

For example, the first thing I asked about was 'whips', which is probably a pretty central concept in your system, and got pretty much a non-answer back. I still don't know what they are. Yeah, I could see that they were used for intersections, but then for something entirely different too. In neither case do I understand how the syntax should be interpreted nor how they're related to our techniques nor what they are conceptually. I tried to look it up (btw, how did you expect me to know what PBCS meant or how to find it?), but couldn't find a simple enough explanation that I'd have actually bothered to read through (sorry).

I seriously doubt it's that complicated, but the theoretical presentation just doesn't work for me. So, is there a way to explain it without a whole bunch of mathematical symbols, possibly even giving some hint to how it might be related to our techniques? That would be really helpful. If no such explanation exists or can be produced, I'm not sure I care enough to bother, and that would be a pity.
User avatar
SpAce
 
Posts: 2559
Joined: 22 May 2017

Re: Need advanced method to solve

Postby denis_berthier » Mon May 11, 2020 3:55 am

SpAce wrote:
denis_berthier wrote:OK for X-chains being simpler than xy-chains. This is one pattern I might add to SudoRules some day.

I'm really surprised that you don't already have it. So, how do you find even the simplest Turbot Fishes, i.e. Skyscrapers, Kites, and Cranes? D

X-chains are a special case of bivalue-chains.

SpAce wrote:
denis_berthier wrote:Actually, I was thinking of generic chains only (i.e. meaningful in any CSP). X-chains are not generic.

What does that mean? How are XY-Chains any more generic? Sorry, but I'm not an expert in generalized CSP thinking.

Generic means that they can be expressed in terms of a general CSP, i.e. CSP-Variables, candidates for them, (direct contradiction) links between candidates and that's all. No rows, no columns, no blocks, no integers.


SpAce wrote:I still don't know what whips and braids are.

Probably, if you had spent as much time trying to understand them as you spend saying you don't know what they are, by now you'd know.

SpAce wrote:For example, to get into your system I'd need to understand the overarching philosophy behind it

No, the logical foundations of my approach are not necessary for understanding whips. You can start PBCS at chapter 5 on whips if you are not interested in logical foundations.
PBCS was not intended as an introduction to Sudoku solving. It is a higher level sequel to HLS. In HLS, all the chains are largely illustrated with multiple examples.

SpAce wrote: and how the various components (the zillion chain types)

There are a few different types of chains, because, unlike AICs that can be anything, my chains have precise definitions and they fit in a clear hierarchy of complexity.
And when you start reading one, the first thing you read is its name and you know in advance what you must expect.

SpAce wrote:Of course the greatest discovery would be to see that your system actually has some useful concepts and techniques for which we don't have equivalent counterparts.

I can easily claim whips, g-whips ,... satisfy these conditions. Now, some people use what they call "memory chains"; those are nothing else than whips... disguised under another name and without the proper notation. In the same way, TDPs are no more than forcing braids without the proper notion of length and the proper notation.
The advantages of whips in terms of resolution power are clear and they are clearly proven in the statistics of PBCS.


SpAce wrote:I don't think either of us can know that at the moment, because it requires very intimate understanding of both systems

I don't know any "other system". In terms of logical approach, there is no other system. Before HLS, nobody had ever tried to explicit the logical foundations of solving.
If you mean AICs vs my rules, then the main difference is clearly reversibility (restricted use of knowledge) vs non-reversibility. As I said before, knowledge is not depleted by being used.
denis_berthier
2010 Supporter
 
Posts: 1672
Joined: 19 June 2007
Location: Paris

Re: Need advanced method to solve

Postby creint » Mon May 11, 2020 7:03 pm

Well I added pasting the resolution path of SudoRules into my solver.
Some thing are now clear to me:
-Whips are some sort of X-sudo like structures. You can draw the truths/links in x-sudo and you get the same exclusions (sometimes more). Other structures are probably the same. Only a subset of all the truth+link combinations are defined, for example hidden pair (2 digit truths + 2 cell links). Maybe this makes it easier to understand.
-SudoRules outputs a single elimination while the structure gives more. This is probably because the solver only gives the easiest structure for one digit.

I could not find any braids/sk-loop notations.

How fast is SudoRules?
How does the solver find the resolution steps?
Can your solver find more resolution steps for the same exclusion?
I still don't understand CSP, searching in your book with 486 pages is probably an option.
creint
 
Posts: 210
Joined: 20 January 2018

Re: Need advanced method to solve

Postby denis_berthier » Tue May 12, 2020 4:54 am

creint wrote:Well I added pasting the resolution path of SudoRules into my solver.

Guess what? Many people have done this before you, including Allan.
I Introduced whips in HLS2 (Nov. 2007). They were then named nrczt-chains. Much later, when Allan introduced what is clearly a modified set covering approach, he explicitly referred to nrczt-chains, to set covering and to this kind of mapping in his very first posts.
But anyway, it's good if it helped you better understand whips.

creint wrote:Some thing are now clear to me:
-Whips are some sort of X-sudo like structures.

No, whips are not XSudo-like structures. A whip is a chain, i.e. a continuous sequence of candidates. An Xsudo structure is made of two sets:
1) a set of CSP-Variables (that Allan renamed as Truths, a totally absurd name, per se and in the context of a set covering approach, where it should be "base set")
and 2) a set of coverings.
What you have done is only map one linear structure to a more complicated one, as others before you, mainly by forgetting the linear structure.

creint wrote:You can draw the truths/links in x-sudo and you get the same exclusions (sometimes more).

How many whips/g-whips/braids... have you tried to map that way?
Nobody knows about the inner workings of XSudo, but Allan admitted that it is not complete and that it relies on some hidden chains that are used for more eliminations than whips. "Not complete" means that it doesn't find all the XSudo structures of any fixed size. And I'm sure you know why: computational complexity. That's why he had to choose some "XSudo structures" based on chains. The underlying hidden chains nevertheless appear in his otherwise totally nonsensical notion of "varying degree".
SudoRules is complete at each level (at least for sets of rules with the confluence property, i.e. braids, ...). That's why I could develop a real theory and a purely logical rating system. XSudo doesn't have any of these.

creint wrote:Other structures are probably the same. Only a subset of all the truth+link combinations are defined, for example hidden pair (2 digit truths + 2 cell links). Maybe this makes it easier to understand.

All the classical Subsets (Naked, Hidden and Super-Hidden), plus their finned variants are in both SudoRules and Xsudo and they are exactly the same thing in both. Subsets are the most typical set covering pattern. (Just in case you thought it was limited to chains, SudoRules can have any pattern, provided one takes time to code it as a resolution rule).

creint wrote:SudoRules outputs a single elimination while the structure gives more.

This was true for chain patterns in previous versions of SudoRules, because it was directly related to PBCS and it was simpler to make this assumption from a theoretical point of view.
However I have now introduced "blocked" versions of some of the rules (all the Subsets, the bivalue-chains and the t-whips), so that they can eliminate more than one candidate at a time. I didn't consider worth it to do the same with whips (except whips[1 or 2]).

creint wrote:I could not find any braids/sk-loop notations.
because you din't look at the right place. There's a full chapter in PBCS about sk-loops (indeed, not for their interest per se, but as an example of modelling)

creint wrote:How fast is SudoRules?

Probably not as fast as a C programmer would like it to be. But fast enough for having solved and rated millions of puzzles.

creint wrote:How does the solver find the resolution steps?

Pattern-matching plus simplest-first strategy. The CSP-Rules engine is based on the CLIPS inference engine. It contains only logical rules (the rule described in PBCS, adapted to the CLIPS syntax); they are interpreted by CLIPS. There's no "program" in the usual sense. The resolution rules are the program.
Errr, not exactly "only" logical rules: I need some input functions to feed the CSP-Rules core engine with the general structures defining Sudoku (rows, columns, ...) plus puzzle data. But these are used only for input and output.

creint wrote:Can your solver find more resolution steps for the same exclusion?

Yes, we can. See above, about "blocked" rules.

creint wrote:I still don't understand CSP, searching in your book with 486 pages is probably an option.

You must have stopped searching rather fast. See section 1.1


Now the good question about your mapping: was XSudo able to find by itself any of the whips in the resolution path, before you fed it with it?
denis_berthier
2010 Supporter
 
Posts: 1672
Joined: 19 June 2007
Location: Paris

Re: Need advanced method to solve

Postby SpAce » Thu May 14, 2020 6:59 am

After wasting time with less interesting topics and pure nonsense elsewhere, let's get back to this...

denis_berthier wrote:X-chains are a special case of bivalue-chains.

Okay, so you do find them as such (as I thought you must)? In that case I misunderstood what you meant. Of course X-Chains are a special case of biv-chains just like they're a special case of AICs. I still don't understand what you meant by adding them as a pattern, if they're already found as biv-chains. Doesn't that require just labeling them as x-chains?

SpAce wrote:I still don't know what whips and braids are.

Probably, if you had spent as much time trying to understand them as you spend saying you don't know what they are, by now you'd know.

You're probably right. Then again, it all goes back to where this discussion started: rationality. I don't think it's rational for me to spend a lot of time on something I don't particularly enjoy, unless someone pays enough for it (or I can expect a high payoff in other ways) :) I love to learn, but I also love optimizing, i.e. to find the shortest and the most enjoyable (or the least painful) path to the goal at hand. If I know or even suspect that someone could easily shorten my learning time considerably by giving a few targeted hints, why shouldn't I ask for help?

In fact I find it a bit interesting that you're not exactly eager to help, even though it should be in your own interest. If I learn and happen to like your system, I'll probably start spreading the gospel. Considering my undeniable expertise in AICs (and pretty much any other sudoku notation except yours), I could also easily teach yours to anyone who's interested, because I could in most cases relate it to whatever techniques they already know. Obviously you don't seem to be in a position (or willing) to do the same despite being the best expert in your own system.

No, the logical foundations of my approach are not necessary for understanding whips. You can start PBCS at chapter 5 on whips if you are not interested in logical foundations.

I started at chapter 5 but gave up pretty soon. Like I said, its theoretical approach didn't work for me, and I'm not eager to go back.

PBCS was not intended as an introduction to Sudoku solving. It is a higher level sequel to HLS. In HLS, all the chains are largely illustrated with multiple examples.

So, HLS is like the 'Berthier's Sudoku System for Dummies'? That would probably work better for me :) I presume HLS is not available online for free, unlike PBCS?

There are a few different types of chains, because, unlike AICs that can be anything, my chains have precise definitions and they fit in a clear hierarchy of complexity.

Do you have a current picture of that hierarchy? That's exactly what I'd need to grasp the big picture. What is also a bit confusing is that your chains have changed names throughout the years, so it would be great to get an update on which chain types/names are current and which ones are obsolete (and any synonyms between them).

And when you start reading one, the first thing you read is its name and you know in advance what you must expect.

Yeah, but for that you need to know what each of those names means, which is a considerable burden for the reader (and the writer). With a correctly written AIC or any extension of it, the chain itself contains all the necessary information to interpret it as long as you know the syntax. For example, a correctly written memory chain is very easy to recognize, so there's no need to label it specifically. (That said, there could be much better standards for many features.)

SpAce wrote:Of course the greatest discovery would be to see that your system actually has some useful concepts and techniques for which we don't have equivalent counterparts.

I can easily claim whips, g-whips ,... satisfy these conditions.

Well, once I understand what they are, I'll tell you whether I agree with that or not :) At the moment I'm not even close to making such judgements. Of course I could take your word for it, but that's not generally what I do (don't take it personally).

Now, some people use what they call "memory chains"; those are nothing else than whips... disguised under another name and without the proper notation.

From the very little I've maybe understood about whips so far, I can see that some whips might be easiest to write as memory chains but I don't think it's their defining feature (I think some of your other advanced chain types are more directly aligned with memory chains). That said, I could be wrong since you refuse to explain in simple terms what whips are :) Funny thing is, I've now seen three different people give three different descriptions for whips. You relate them to memory chains, creint to XSudo structures, and Robert recently called them contradiction chains. Seems pretty obvious to me that I really must try to look under the hood myself in order to find the truth.

Now that I did take another very very brief look at the couple of simple whips you gave for this puzzle, and some others, I think Robert's assessment might be closest to the truth. It seems that the defining feature is indeed that whips are contradiction chains (instead of verity chains like biv-chains), though there's possibly memory involved too (but not necessarily). I think I mostly understand the syntax too, except for the whip[1] intersections:

Code: Select all
whip[1]: r4n3{c3 .} ==> r6c3 ≠ 3, r5c3 ≠ 3, r6c2 ≠ 3
whip[1]: r3n5{c6 .} ==> r1c4 ≠ 5
whip[1]: b5n3{r6c5 .} ==> r1c5 ≠ 3

(The first two are claiming and the last one is a pointing operation, in our terms.) If I've understood anything (and it's possible I haven't), I would think that the '.' in place of a right-linking candidate represents a contradiction. In other words, if any of the targets is assumed, the left-linking candidate(s) will get killed making the right-linking candidates true, but since the last (and in this case only) CSP variable has no right-linking candidate it's a contradiction. Hence the target(s) can be eliminated. Is that anywhere close? If so, I still find the syntax very unintuitive. I'd rather write those like this:

Code: Select all
whip[1]: r4n3{c23 .} ==> r6c3 ≠ 3, r5c3 ≠ 3, r6c2 ≠ 3
whip[1]: r3n5{c46 .} ==> r1c4 ≠ 5
whip[1]: b5n3{r56c5 .} ==> r1c5 ≠ 3

Now they'd have even a chance of being understandable to me (since the intersections have more than one candidate).

The longer whip (representing an XYZ-Wing) is actually easier to understand using that contradiction interpretation:

Code: Select all
whip[3]: r4c1{n4 n5} - r5c3{n5 n7} - r8c3{n7 .} ==> r6c3 ≠ 4

Again, that looks very weird at first glance, because if you look at the grid, r5c3 has three candidates instead of two. Thus, the "strong link" {n5 n7} makes sense only if we first assume the target 4r6c3 which eliminates 4r5c3 allowing the chain to continue. Similarly the '.' in the last node makes sense only with the same assumption: if the 4r8c3 is assumed eliminated, the cell becomes empty if the 7r8c3 is killed too, hence a contradiction. So, there's indeed some implied memory there, though it's not necessary to write as a memory chain in our system.

Am I anywhere close? If so, the concept is just like I suspected: very simple (primary keyword: contradiction; optionally: memory). How hard would it be to explain it like that? ;) So how does it relate to our system? First of all, we'd never use either contradiction chains or memory chains for such simple operations, but if someone really wants, it's perfectly possible of course. They're undeniably simple and powerful but usually considered inelegant (not always, see eleven's chain below), so they're normally reserved for the very last resort techniques only, and even then some of the best solvers refuse to use them.

If I were to write the last XYZ-Wing as a contradiction chain, it would look like this (for example):

Code: Select all
(4)r6c3 - (4=!)r4c1,r58c3 => -4 r6c3

('!' represents a contradiction.) Or to mimic your way more closely:

Code: Select all
(4)r6c3 - r4c1,r58c3 = [(4=5)r4c1 - (5=7)r5c3 - (7=!)r8c3] => -4 r6c3

(No memory needed in either case.) I think that's much more intuitively understandable than yours (even considering my obvious bias), because the assumption of 4r6c3 and its effects are explicit. However, we can also drop the first terms in both cases (and I would), which makes them quasi-valid AICs (strong link at both ends, though one of them linking to a contradiction) and perhaps more similar to your whip:

Code: Select all
(!=4)r4c1,r58c3 => -4 r6c3

(4)r4c1,r58c3 = [(4=5)r4c1 - (5=7)r5c3 - (7=!)r8c3] => -4 r6c3

I've actually used that style in many situations, since the '!' can represent any deadly pattern (I usually write it 'DP', though some might not like it for other than uniqueness patterns). For example, my first suggestion to write eleven's May 6, 2020 logic was exactly that, because such a quasi-AIC was the easiest (and probably the best) way to write his logic:

Code: Select all
(DP=1|6)r4c6,r5c5 - (16=3|5)r2c56 - (35=6)r2c1,r3c4 => -6 r2c5,r3c1; stte

Just like a normal AIC it proves that one or the other end must be true. However, since one end is a DP (i.e. a contradiction) it can't be true, which means the other must be, justifying the eliminations. No direct contradiction (or memory) needed. Would that be a (rather complicated) whip logically (forgetting the different notation)?

Anyway, why would I do something like that in this case? An XYZ-Wing is very easy and more elegant to write as a normal AIC (with a simple ALS node):

Code: Select all
(4=5)r4c1 - (5=74)r58c3 => -4 r6c3

That's also an ALS-XZ pattern (like all (UVW)XY(Z)-Wings). Such wings can also be written as a shorter ALS-Z pattern (my term):

Code: Select all
(45)b4p16 = (74)r58c3 => -4 r6c3

Thus, since there are so many more elegant options, why would I ever use a contradiction chain or even a quasi-AIC here? I do understand the power of contradiction (and memory) chains, and I have nothing against using them in some much more complicated situations, but why waste such power on these kinds of elementary problems? Seems like an overkill to me. (More importantly, like I said, I still don't understand the whip[1] syntax in the intersection examples as it seems like they're missing candidates.)

In the same way, TDPs are no more than forcing braids without the proper notion of length and the proper notation.

I'll get back to the braids once I've understood whips. (If you confirm my interpretations above, then I think I'm pretty close.)

The advantages of whips in terms of resolution power are clear and they are clearly proven in the statistics of PBCS.

I don't doubt that. Contradiction (and memory) chains are simple and powerful, obviously. But, unless whips are actually much more than those, I don't see how they're unique to your system.

I don't know any "other system". In terms of logical approach, there is no other system. Before HLS, nobody had ever tried to explicit the logical foundations of solving.

That might be (I wouldn't know), but in any case, I'm just talking about the practical aspects of manual solving. I don't much care about theoretical superiority or who invented and what. All I care about is knowing which tool is the best for each task.

If you mean AICs vs my rules, then the main difference is clearly reversibility (restricted use of knowledge) vs non-reversibility. As I said before, knowledge is not depleted by being used.

That's a restriction of valid AICs only. Pretty much any piece of logic can be written with valid AICs, but it takes a lot of skill, and the result is not always very readable. Thus, most of us are quite happy to accept extensions that break that rule if it produces simpler and more legible chains. (David Bird is pretty much the only one I know who refused to use anything but valid AICs.) For that reason, extensions like krakens, memory chains, contradiction chains, network diagrams, and possibly even matrices should be included as parts of "our system", because almost all of the advanced solvers use at least some of them even if valid AICs are their preferred tool.

There are also things that can't practically be represented with chains at all, such as (some) fishes and things like MSLS and other Rank 0 patterns. For that, there are the fish and more generic set logic notations, as well as matrices. As far as I know, the only useful pattern that can't be easily represented (or at least understood) with any of the previous notations, is (J)Exocet, so it deserves its own treatment (JE logic can be expressed with set logic, a netword diagram, or a matrix, but it's hard). Deadly patterns, especially complex uniqueness patterns, are also a bit special cases.

Does your system have capabilities that go beyond all of the previously mentioned techniques and notations? That's the real question instead of how it compares to mere AICs.
User avatar
SpAce
 
Posts: 2559
Joined: 22 May 2017

Re: Need advanced method to solve

Postby denis_berthier » Fri May 15, 2020 5:43 am

SpAce wrote:
denis_berthier wrote:X-chains are a special case of bivalue-chains.

Okay, so you do find them as such (as I thought you must)? In that case I misunderstood what you meant. Of course X-Chains are a special case of biv-chains just like they're a special case of AICs. I still don't understand what you meant by adding them as a pattern, if they're already found as biv-chains. Doesn't that require just labeling them as x-chains?

They cannot be identified by SudoRules as x-chains if the x-chain pattern is not defined in SudoRules. Of course, on seeing a bivalue-chains that uses a single digit, we can say afterwards it's an x-chain.

SpAce wrote:
denis_berthier wrote:There are a few different types of chains, because, unlike AICs that can be anything, my chains have precise definitions and they fit in a clear hierarchy of complexity.

Do you have a current picture of that hierarchy? That's exactly what I'd need to grasp the big picture. What is also a bit confusing is that your chains have changed names throughout the years, so it would be great to get an update on which chain types/names are current and which ones are obsolete (and any synonyms between them).

Th hierarchy is clearly defined in PBCS. A mapping of names from HLS to PBCS is already written in the CSP-Rules user manual.


SpAce wrote:
denis_berthier wrote:And when you start reading one, the first thing you read is its name and you know in advance what you must expect.

Yeah, but for that you need to know what each of those names means, which is a considerable burden for the reader (and the writer). With a correctly written AIC or any extension of it, the chain itself contains all the necessary information to interpret it as long as you know the syntax. For example, a correctly written memory chain is very easy to recognize, so there's no need to label it specifically. (That said, there could be much better standards for many features.)

Sure, the AIC notation is so clear and universal that half of the talks in the Puzzles forum are about what it means.


SpAce wrote:
denis_berthier wrote:Now, some people use what they call "memory chains"; those are nothing else than whips... disguised under another name and without the proper notation.

Seems pretty obvious to me that I really must try to look under the hood myself in order to find the truth.

That seems to be the right conclusion indeed.

SpAce wrote: I think I mostly understand the syntax too, except for the whip[1] intersections:
Code: Select all
whip[1]: r4n3{c3 .} ==> r6c3 ≠ 3, r5c3 ≠ 3, r6c2 ≠ 3
whip[1]: r3n5{c6 .} ==> r1c4 ≠ 5
whip[1]: b5n3{r6c5 .} ==> r1c5 ≠ 3

(The first two are claiming and the last one is a pointing operation, in our terms.) If I've understood anything (and it's possible I haven't), I would think that the '.' in place of a right-linking candidate represents a contradiction.

The "." itself doesn't represent a contradiction, but the absence of a candidate for this CSP-Variable. The contradiction is only the logical consequence of this factual absence.

SpAce wrote:In other words, if any of the targets is assumed, the left-linking candidate(s)

There's only one target and one left-liking candidate, the other candidates are t- or z-or right-linking candidates
SpAce wrote:the left-linking candidate(s) will get killed making the right-linking candidates true, but since the last (and in this case only) CSP variable has no right-linking candidate it's a contradiction. Hence the target(s) can be eliminated.

Yes

SpAce wrote:
denis_berthier wrote:The advantages of whips in terms of resolution power are clear and they are clearly proven in the statistics of PBCS.

I don't doubt that. Contradiction (and memory) chains are simple and powerful, obviously. But, unless whips are actually much more than those, I don't see how they're unique to your system.

Where can you see any definition of "contradiction (and memory) chains" or any theory about them?
denis_berthier
2010 Supporter
 
Posts: 1672
Joined: 19 June 2007
Location: Paris

Re: Need advanced method to solve

Postby SpAce » Fri May 15, 2020 1:26 pm

denis_berthier wrote:They cannot be identified by SudoRules as x-chains if the x-chain pattern is not defined in SudoRules. Of course, on seeing a bivalue-chains that uses a single digit, we can say afterwards it's an x-chain.

Ok. I thought that was the obvious implementation, unless SudoRules has some weird restriction that prevents relabeling a chain after finding it. I guess that's not a good enough fix anyway if one wants to search for x-chains specifically (like before more complicated chains).

SpAce wrote:Th hierarchy is clearly defined in PBCS.

On what page? If you mean that it becomes clear if one reads and internalizes all 480 pages, then we have a different definition of clarity :) What I asked for was a single image which clearly visualizes the hierarchy, i.e. something like this.

A mapping of names from HLS to PBCS is already written in the CSP-Rules user manual.

And where might I find such a user manual?

Sure, the AIC notation is so clear and universal that half of the talks in the Puzzles forum are about what it means.

I just said it would be nice to have better standards, so no disagreement there. Besides, you can blame me for most of those talks in recent years, both because I've tried to standardize notations and best practices, and also because I've experimented with several "new" (mostly just rare) and controversial features which have raised eyebrows. You can avoid those kinds of discussions with your own system because you can dictate its standards. There's no one person who can do the same for Eureka, so it just has to evolve naturally (*). I try to speed up the process but not everyone likes it very much (to put it mildly).

That said, there's rarely if ever a question whether the intent of a particular chain/net written in Eureka is understood by the regular users (except for some of my own extreme compressions, lol). I can't remember the last time it was even hard for me to see what the player wanted to communicate, even if the chain didn't adhere to any standards or was blatantly incorrect. The real debates are about exact correctness, style, and proposed new features.

Writing a fully correct complex AIC is not trivial, as it basically requires understanding how it maps into boolean logic. Many have not bothered to work it out for themselves, so they're bound to make (usually harmless) mistakes. You might say that it's a weakness of AICs, and you wouldn't be wrong, but on the other hand it's what makes playing with AICs fun (at least for me, and I'm not the only one). Trivial things aren't very interesting. Most of the daily Puzzles are so easy to solve that at least for me the most interesting part is often optimizing the notation (but what seems optimal for me isn't always optimal for the readers, lol).

(*) About the evolution of your own notations... I just looked at some of your old chains and thought they were much more readable than the modern ones. The reason is clear too. Why did you switch from the "natural" n-first coordinates to the horrible r/c/b-first style? In other words, why r4n3{c3 .} instead of n3r4{c3 .}??? The latter style I could probably learn to read almost as easily as Eureka but no chance with the mangled coordinates. Also, since you call them nrc-chains, shouldn't it be logically reflected in the default order of the coordinates too?

The "." itself doesn't represent a contradiction, but the absence of a candidate for this CSP-Variable. The contradiction is only the logical consequence of this factual absence.

I understand. Yet for all practical purposes my interpretation works too, right? I think it's simpler to understand and to explain that way, but I accept that it's not precisely what was intended.

Btw, now that I apparently understand what a whip is, I must say that I really like the name! It's actually very descriptive.

There's only one target

Yet you sometimes have multiple eliminations with a single chain/whip, so doesn't that imply multiple targets (or do they form a single target together)?

and one left-liking candidate, the other candidates are t- or z-or right-linking candidates

Ok. Are t-candidates those that I would be tempted to see as extra left-linking candidates that are hit by previous, non-adjacent right-linking candidates (i.e. what we call memories)? Are z-candidates extra right-linking candidates that link directly to the target (i.e. what I would call alternate end-points)?

If so, both of those can be used within a memory chain (that's how they differ from AICs), so that's a direct mapping between your system and ours. Personally I think ours is more readable because it shows exactly what remote right-linking candidates are linked with what left-linking candidates. It's more intuitive too because the remote left-linking candidates are written to where they belong: to the left.

That said, I see advantages in yours too, so don't be offended by my observations and opinions. Nothing's perfect. I could also imagine the possibility that those features might have been nabbed from your system, but unfortunately I don't know anything about the history of memory chains. What I do know is that I've seen some horrible implementations on our side (like storing what I call "negative memories") and sometimes still do.

The way I use memory chains, and what I naturally think is the only right way to do it, works exactly like your t- and z-candidates (if I now understand them correctly) despite the different syntax. I also have little to no problem reading them both ways, which is why I don't quite accept the conventional view that they're unidirectional. I guess our way of marking both remotely linked candidates helps, as well as the correct use of '|' (boolean OR) in the remote left-linking nodes (which is one of the hardest things to get right for many even in regular AICs).

Where can you see any definition of "contradiction (and memory) chains" or any theory about them?

Nowhere, but personally I don't need it for any practical purposes (not anymore at least). They're very simple concepts, and I know exactly how they work (or should work) without a whole lot of theoretical background. The only problem is that some people seem to have very different and weird definitions for the same concepts, so yeah, I can see the wider problem. But again, you have the advantage of being able to dictate what definitions are used in the context of your system. I can only wish.

If you're interested (probably not), here's my idea of correct memory chain syntax:

Normal AIC (no memory):

Code: Select all
(a=b) - (b=c) - (c=d) => -x (seen by a and d)

Memory chain (one stored memory, used once):

Code: Select all
(a=b*) - (b=c) - (c|*b=d) => -x (seen by a and d)

b* represents a stored memory and *b its weakly-linked victim (or vice versa if read the other way). In other words, if I understood your t-candidates correctly, *b would be one.

Memory chain (one stored memory, used twice):

Code: Select all
(a=b*) - (b=c) - (c|*b=d) - (d|*b=e) => -x (seen by a and e)

Memory chain (two stored memories, used once each):

Code: Select all
(a=b*) - (b=c^) - (c=d) - (d|*b|^c=e) => -x (seen by a and e)

Thus, each stored memory is marked (on their right side) with a different symbol which is also marked on the left side of the corresponding victim(s). There's no real standard on the symbols but those two are probably the most common in that order; everything goes as long as it can't be confused with other meanings.

Lastly, what I call "alternate end points", i.e. apparently your z-candidates (I guess):

One alternate end point:

Code: Select all
(a=b) - (b=c@|d) - (d=e) => -x (seen by a, c, and e)

Two alternate end points:

Code: Select all
(a=b) - (b=c@|d) - (d=e@|f) - (f=g) => -x (seen by a, c, e, and g)

An alternate end point is similar to a memory except that it's ORed and linked to the target (which allows the chain to continue linearly despite the OR). If there's more than one, the same symbol (I use '@') is used for them all (always on the right side, because they're not linked to each other). Of course both these and normal memories can be used in the same chain (not shown). (I sometimes use the same symbol in normal AICs to mark extra endpoints that give additional eliminations with an embedded chain. They're not ORed. Extra endpoints don't imply a memory chain (but it could be for other reasons.))

Personally I find that very easy and intuitive. Not exactly pretty, but readable. You probably don't agree with that, but would you agree that those match the functionality of your t- and z-candidates?
User avatar
SpAce
 
Posts: 2559
Joined: 22 May 2017

Re: Need advanced method to solve

Postby denis_berthier » Fri May 15, 2020 5:17 pm

SpAce wrote:
denis_berthier wrote:A mapping of names from HLS to PBCS is already written in the CSP-Rules user manual.

And where might I find such a user manual?

Until now, only on my Mac

SpAce wrote:About the evolution of your own notations... I just looked at some of your old chains and thought they were much more readable than the modern ones. The reason is clear too. Why did you switch from the "natural" n-first coordinates to the horrible r/c/b-first style? In other words, why r4n3{c3 .} instead of n3r4{c3 .}??? The latter style I could probably learn to read almost as easily as Eureka but no chance with the mangled coordinates. Also, since you call them nrc-chains, shouldn't it be logically reflected in the default order of the coordinates too?

There can't be any fixed order. CSP-Variables come first, then their value, so that you will always have some rn{c... and some cn{r... and some bn{xx.. So, the order rn or nr is irrelevant. As someone else (maybe Red Ed) said of it someday, it is the inventor's prerogative (and he did mean me).

SpAce wrote:
denis_berthier wrote:The "." itself doesn't represent a contradiction, but the absence of a candidate for this CSP-Variable. The contradiction is only the logical consequence of this factual absence.

I understand. Yet for all practical purposes my interpretation works too, right? I think it's simpler to understand and to explain that way, but I accept that it's not precisely what was intended.

Simplifications that distort the meaning are never simpler to understand in the end. They put you on the wrong track.
A whip is a pattern you can physically see on a PM. It's not a chain of inferences; it can be the support for inferences but, I repeat, it is a physical thing. :idea: ??


SpAce wrote:
denis_berthier wrote:There's only one target

Yet you sometimes have multiple eliminations with a single chain/whip, so doesn't that imply multiple targets (or do they form a single target together)?

Each one is a target in turn. (They are never used simultaneously in the chain.)

SpAce wrote:
denis_berthier wrote:and one left-liking candidate, the other candidates are t- or z-or right-linking candidates

Ok. Are t-candidates those that I would be tempted to see as extra left-linking candidates that are hit by previous, non-adjacent right-linking candidates

That's where different types of chains have different conditions for the llc. But in any case, only one llc is needed to ensure the condition. The rest are only parasitic.
For whips a llc can only be linked to the previous rlc, so even if there are several possibilities, there will also be candidates linked to farther rlcs, and they can't be considered as possible llcs.


SpAce wrote:(i.e. what we call memories)? Are z-candidates extra right-linking candidates that link directly to the target (i.e. what I would call alternate end-points)?
If so, both of those can be used within a memory chain (that's how they differ from AICs), so that's a direct mapping between your system and ours.

Who is "we" and "ours"? There was no "memory chains" before I introduced whips, braids and all my menagerie. Some people pretend not to understand them and propose "new" chains" and new names for them or for related concepts as if they had invented anything.
There is no "our" system. There is just an alternative notation that tries to hide the total absence of new ideas or plagiarism.

SpAce wrote:
denis_berthier wrote:Where can you see any definition of "contradiction (and memory) chains" or any theory about them?

Nowhere,

That settles the question for me. I need no "but".

SpAce wrote:If you're interested (probably not),

I'm not interested at all in talking about notation. It's pure waste of time.
The nrc-notation has clear foundations, is more readable than anything I've seen and it perfectly serves its purpose.
denis_berthier
2010 Supporter
 
Posts: 1672
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to Help with puzzles and solving techniques