The New Sudoku Players' Forum

Website · by **denis_berthier** » Sat May 16, 2020 3:33 pm

DEFISE wrote:Hello Denis,
I wonder about braids and whips.
In your PBCS document (Nov 2012) you said p108, in the definition of braid :
« for any 1< k ≤ n, Lk is linked either to a previous right-linking candidate (some Ri, i < k) or to the target; this is the only (but major) structural difference with whips (for which the only linking possibility is Rk-1) »
I deduce that in a whip Lk must not be linked to the target nor to a Ri , i < k-1.
Is this right ?

Yes. And you can see it written explicitly in the definition of a whip, before that of a braid.

Whips enjoy the continuity condition. Every candidate in the sequence Z LLC1 RLC1 LLC2 RLC2 ... is directly linked to the previous one. It's a major structural difference with braids. It's the reason for a much lower computational complexity. And the miracle is, whips are, most of the time, an excellent approximation of braids. Why this is so remains rather mysterious to me, even years after I defined both.

by **DEFISE** » Sat May 16, 2020 4:51 pm

Hello Denis,

Yes, I noticed that whips are much faster to find than braids.
In your definition of whip I did not find this clarification “Lk must not be linked to the target nor to a Ri , i < k-1 ».
Perhaps you have change it since 2012. I found it only in braid’s definition.

On the other hand, by checking your whip resolution (see the beginning below), in the whip [9] you can see that the 4th CSP variable c9n1{r6 r5} contains Lk = 1r6c9 which is linked to the target 1r6c2.
So I don’t understand: either your definition is not precise enough, or there is a problem in your program.

Hidden Text: Show

Website · by **denis_berthier** » Sat May 16, 2020 5:22 pm

DEFISE wrote:HIn your definition of whip I did not find this clarification “Lk must not be linked to the target nor to a Ri , i < k-1 ».
Perhaps you have change it since 2012. I found it only in braid’s definition.

I never wrote to what Lk must NOT be linked, but to what it MUST be linked.

PBCS1 p.101 wrote:Definition: in a resolution state RS, a chain is a finite sequence of candidates (it is thus linearly ordered) such that any two consecutive candidates in the sequence are linked (we call this the “continuity condition” of chains; it implies that consecutive candidates are different).

PBCS1 p.104 wrote:Definition: in a resolution state RS, given a candidate Z (which will be the target), a zt-whip (in short a whip) of length n (n ≥ 1) built on Z is a regular chain (L1 , R1 , L2 , R2 , …. Ln ) [notice there is no Rn ] associated with a sequence (V1 , … Vn ) of CSP variables, such that: ...

As you can see, a whip is a chain and therefore Lk must be linked to Rk-1. That doesn't forbid it to be linked, in addition, to anything else.

by **DEFISE** » Sat May 16, 2020 6:13 pm

Hello Denis,
Ah, now it’s clear, thank you !
So I’ll modify my program.

by **DEFISE** » Sun May 17, 2020 2:21 pm

Hello Denis,

I changed my programs according to your last answer.
Then I checked your W resolution step by step (see the beginning below).
I think I can replace your 6th whip (a whip [11] which eliminates 7r2c1) with this one:
whip[10]: r2n9{c1 c3} - c3n2{r2 r7} - r7n7{c3 c6} – c3n7{r7 r4} - r4n1{c3 c4} - r4n6{c4 c6} - r4n8{c6 c1} - r7n8{c1 c4}
- c6n8{r9 r1} - r1c3{n8 .} ==> r2c1 ≠ 7
Knowing that you apply the principle "simplest first", I deduce that there must be an error in my whip [10], but which one ?

Hidden Text: Show

by **Ajò Dimonios** » Sun May 17, 2020 3:21 pm

Perhaps the mistake may be in the fact that, (- r7n7{c3 c6} – c3n7{r7 r4} - ) is in contradiction with what is written on page 101 ”Definition: in a resolution state RS, a chain is a finite sequence of candidates (it is thus linearly ordered) such that any two consecutive candidates in the sequence are linked (we call this the “continuity condition” of chains; it implies that consecutive candidates are different).”

Paolo

Website · by **denis_berthier** » Sun May 17, 2020 5:08 pm

Ajò Dimonios wrote:Perhaps the mistake may be in the fact that, (- r7n7{c3 c6} – c3n7{r7 r4} - ) is in contradiction with what is written on page 101 ”Definition: in a resolution state RS, a chain is a finite sequence of candidates (it is thus linearly ordered) such that any two consecutive candidates in the sequence are linked (we call this the “continuity condition” of chains; it implies that consecutive candidates are different).”

This doesn't contradict the continuity condition, but the difference is indeed at this place.
There's a technical condition on whips in SudoRules (see section 5.8 of PBCS): no loops. r7n7c3 and c3n7r7 are the same candidate and this part of the whip makes a loop.

by **DEFISE** » Sun May 17, 2020 6:53 pm

Hello Denis,
Sorry, I had not read §5.8. It's clear now.

by **Ajò Dimonios** » Sun May 17, 2020 7:30 pm

Hi Denis,
I too have not read chapter 5.8. Now everything is clear.

Paolo

Website · by **denis_berthier** » Mon May 18, 2020 6:23 am

Hello Defise, Paolo,

I don't know if this can be of any help for your implementations, but anyway you may be interested to know there have been previous implementations of whips/braids... (I mean other than SudoRules). All this was some 5+ years ago and I haven't been present on this forum for a long time, so I lost track of many things. Also, after the crash of the Sudoku Player's forum, many things were lost.

One implementation was by Paul (I can't remember his full name). I think his whips were ok: we had the same results (i.e. W ratings) for the 1,000 puzzles we tried. Unsurprisingly, his solver directly coded in C (or C++, I can't remember) was faster than SudoRules. He tried to code braids, but didn't succeed. I have had no news of him for a long time. I don't know if his code is still available or has been lost in the crash and I'm too lazy for this kind of things to search the whole forum.

Another implementation came from Mauricio (this was his full name on this forum). He had a longer presence on this forum than Paul and he contributed to very interesting examples, including one with the longest whip I know (I have a sub-section in PBCS where I mention him with this example). As far as I can remember, he correctly implemented whips and g-whips (in javascript); I'm not sure about braids and g-braids. His program was also faster than SudoRules.

by **DEFISE** » Mon May 18, 2020 4:42 pm

Hello Denis,
Thank you for these precisions, but I can test my program from your examples, that’s not bad.
Especially, I checked the whip[18] and the whip[31] in your doc. Instead of whip[31] I got a whip[29] which must contain a loop, I suppose (I will check it).

by **DEFISE** » Tue May 19, 2020 6:44 pm

Hello Denis,

My program allows loops only on the left-linking candidates (not on the righ-linking).
With it, I checked the value of W and B of all the examples from your doc (CSP Nov 2012), up to page 261.
I have only three remarks:

1) Puzzle p133
9817.325.752..19..364.9...8.173...92.43..9.6..9...7...4..1...29.29..8......9..5..
I also noticed the non-confluence of W4 whip.

2) Puzzle p137
.....1..2....3..4...52..1....36...1..2..7...89....57....9..7....8.9....43...4..8.
I found W = 29 instead of 31. The reason is that my whip [29] contains 2 loops.

3) Puzzle p184
1....6..9..........8.1..56..3.6..8.1........7.....8246.4.9...2.56.841.....7..3...
I found B=6 instead of 7. You probably made a typo because braids have the confluence property and loops should have no influence on them.

Website · by **denis_berthier** » Wed May 20, 2020 3:08 am

Hi Defise,

DEFISE wrote:My program allows loops only on the left-linking candidates (not on the righ-linking).
With it, I checked the value of W and B of all the examples from your doc (CSP Nov 2012), up to page 261.
I have only three remarks:
1) Puzzle p133
9817.325.752..19..364.9...8.173...92.43..9.6..9...7...4..1...29.29..8......9..5..
I also noticed the non-confluence of W4 whip.

Great! I like this example; it's very simple.

DEFISE wrote:2) Puzzle p137
.....1..2....3..4...52..1....36...1..2..7...89....57....9..7....8.9....43...4..8.
I found W = 29 instead of 31. The reason is that my whip [29] contains 2 loops.

That could make an interesting example of loops in whips.

DEFISE wrote:3) Puzzle p184
1....6..9..........8.1..56..3.6..8.1........7.....8246.4.9...2.56.841.....7..3...
I found B=6 instead of 7. You probably made a typo because braids have the confluence property and loops should have no influence on them.

Thanks for noticing. I don't know if it was a typo, because I didn't write the resolution path in PBCS as the B rating was irrelevant to the example. I checked again and SudoRules finds 6 (see below). (I'll write an erratum on my website.)
Loops are irrelevant in braids, not because of the confluence property, but because a loop can always be excised.

Hidden Text: Show

by **DEFISE** » Wed May 20, 2020 4:19 pm

Hello Denis,

All right ! About puzzle p137 of your CSP book, here is my whip[29] with 2 loops (the first 9 CSP variables are like yours):

whip[29] : b3n8{r1c7 r2c7} – c1n8{r2 r4} – c6n8{r4 r3}- b2n4{r3c6 r1c4} – b2n7{r1c4 r2c4} –
b2n5{r2c4 r1c5} – b3n5{r1c8 r2c9} – r4c9{n5 n9} – r4c5{n9 n2} – c5n9{r4 r3} – r2c6{n9 n6} -r9c6{n6 n2} – r4c6{n2 n4} – r4c7{n4 n5} – r4c2{n5 n7} – b4n5{r4c2 r5c1} – r8n5{c1 c8} – b9n7{r8c8 r9c9} – r9n9{c9 c7} – b3n9{r1c7 r1c8} – r1n7{c8 c1} – r8n7{c1 c3} – c3n2{r8 r2} – r2c1{n2 n1} – r8n1{c1 c5} – c5n6{r8 r7} – b9n6{r7c7 r8c7} – r1n6{c7 c2} – c1n6{r3.} => r1c3 # 8

There is a 2nd possibility, ending with: -c1n6{r8 r3} – r1n6{c2.}

Website · by **denis_berthier** » Thu May 21, 2020 5:45 am

DEFISE wrote:Hello Denis,

All right ! About puzzle p137 of your CSP book, here is my whip[29] with 2 loops (the first 9 CSP variables are like yours):

whip[29] : b3n8{r1c7 r2c7} – c1n8{r2 r4} – c6n8{r4 r3}- b2n4{r3c6 r1c4} – b2n7{r1c4 r2c4} –
b2n5{r2c4 r1c5} – b3n5{r1c8 r2c9} – r4c9{n5 n9} – r4c5{n9 n2} – c5n9{r4 r3} – r2c6{n9 n6} -r9c6{n6 n2} – r4c6{n2 n4} – r4c7{n4 n5} – r4c2{n5 n7} – b4n5{r4c2 r5c1} – r8n5{c1 c8} – b9n7{r8c8 r9c9} – r9n9{c9 c7} – b3n9{r1c7 r1c8} – r1n7{c8 c1} – r8n7{c1 c3} – c3n2{r8 r2} – r2c1{n2 n1} – r8n1{c1 c5} – c5n6{r8 r7} – b9n6{r7c7 r8c7} – r1n6{c7 c2} – c1n6{r3.} => r1c3 # 8

There is a 2nd possibility, ending with: -c1n6{r8 r3} – r1n6{c2.}

Thanks; it's interesting to see loops in action. I didn't try with this puzzle. In the early versions of SudoRules, I didn't eliminate loops in whips, but I found that they rarely made things simpler - and, of course, they can be caught as braids. So, I finally chose to eliminate them. I'll keep it this way in CSP-Rules, but I don't have hard opinions about this choice.

The New Sudoku Players' Forum

Extreme Puzzle No.5

Re: Extreme Puzzle No.5

Re: Extreme Puzzle No.5

Re: Extreme Puzzle No.5

Re: Extreme Puzzle No.5

Re: Extreme Puzzle No.5

Re: Extreme Puzzle No.5

Re: Extreme Puzzle No.5

Re: Extreme Puzzle No.5

Re: Extreme Puzzle No.5

Re: Extreme Puzzle No.5

Re: Extreme Puzzle No.5

Re: Extreme Puzzle No.5

Re: Extreme Puzzle No.5

Re: Extreme Puzzle No.5

Re: Extreme Puzzle No.5