The New Sudoku Players' Forum

[denis_berthier]

I've made a new try at the loopy-whips and tried them on the Mauricio puzzle.
I get a different whip[29]:

Code: Select all

whip[29]: r7n4{c1 c2} - r1n4{c2 c4} - r6n4{c4 c3} - b4n8{r6c3 r4c1} - r4n7{c1 c2} - b4n5{r4c2 r5c1} - c2n5{r4 r9} - r9c4{n5 n1} - r5c4{n1 n3} - r5n1{c4 c3} - r6c2{n1 n6} - r6c9{n6 n3} - r6c4{n3 n8} - r7c4{n8 n5} - r2c4{n5 n7} - b2n5{r2c4 r1c5} - c8n5{r1 r8} - b9n7{r8c8 r9c9} - c9n1{r9 r7} - b7n1{r7c1 r8c1} - c1n7{r8 r1} - r3n7{c2 c8} - r3n3{c8 c2} - r1c2{n3 n9} - c8n9{r1 r5} - r5n6{c8 c7} - b9n6{r9c7 r7c8} - r1n6{c8 c3} - b7n6{r8c3 .} ==> r3c1 ≠ 4


But the computation times and memory requirements are much larger than with my standard no-loop whips, which I'll stick to in CSP-Rules.

[DEFISE]

Hello Denis,

I get like you for the target 4r3c1.
My only possibility is this: loops allowed on left-linkings and loops prohibited on right-linkings.
So I can't compare run times as you do.
Anyway I have no problem of run time with this p137 puzzle (8s for whips and 19s for braids) because the number of right-linking sequences is less than 10 000 for each target.
(I have a laptop with a processor intel core i5 2,30 Gz).
No memory problem either : the sequence max = 29 candidates => 29 x 2 bytes = 58 bytes => total memory < 580 000 bytes.
However I can have problems of run time with braids of length >= 11 or 12, because the number of right-linking sequences can exceed 100 000, so I limit this number to 25000.
For the Extreme5 puzzle, I found B=11 in 5mn but the capacity of 25000 sequences was exceeded and I therefore neglected possibilies. So I'm not sure that B = 11 but I don't want to run my machine for more than 5 minutes (my goal is just to have a little fun).

[yzfwsf]

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.

Matt,

Unfortunately, the nrc_bfs function is just a teaser for the whole enchalada, so it might lead to more questions than answers. Denis Berthier has encouraged/challenged me to present my implementation of his nrczt-whips/braids and I don't want to hi-jack your thread, so I'll have to open a new topic when I have sufficient material to warrant publishing. Unfortunately, or fortunately depending upon point of view, I'm on vacation for another month so my sudoku time is strictly limited per family decree.

In the meantime, you might want to search for threads on strong links or strong inferences. There's an interesting topic on the Player's forum regarding using URs in chains: http://www.sudoku.com/boards/viewtopic.php?t=6648

Also, Denis has numerous topics in this forum and the Player's forum regarding nrczt chains. I'll admit up front that I'm a convert and I would dearly love to have another programmer implement nrczt chains. Nudge, nudge...

Cheers,
Paul

For those who want to play around with nrczt and nrczt-(pseudo)-braids, I've uploaded my test project pascal code. You need Free Pascal 2.2.4 to recompile.
Download and unzip into a directory: http://pisaacson.fileave.com/Sudoku/sudoku.zip

He is PIsaacson, maybe there is a copy of his program in your computer, because I found that he uploaded his solver when interacting with you.

[denis_berthier]

For those who want to play around with nrczt and nrczt-(pseudo)-braids, I've uploaded my test project pascal code. You need Free Pascal 2.2.4 to recompile.
Download and unzip into a directory: http://pisaacson.fileave.com/Sudoku/sudoku.zip

He is PIsaacson, maybe there is a copy of his program in your computer, because I found that he uploaded his solver when interacting with you.

Hi yzfwsf,

Unfortunately, the links lead to error 404. There has been a big crash of The Player's Forum, resulting in half of the content being lost. (The forum manager of that time didn't make backups.)
Where's the original place of the first post (to Matt)?

If Paul's program was indeed in Pascal and if I had a copy on my Mac, it'd be easy for me to find it. But I could find only a few files with the ".pas" ending and none was related to Sudoku.
However, I have some doubts that the Pascal version you mention is the right reference. As far as I can remember, what we talked about with Paul was written in C or C++. We did exchange and compare our W ratings (called nrczt-chains at that time), which resulted in validating his program for whips.
I know he also worked on braids but couldn't make them work (which of course made the program less interesting for me compared to SudoRules). And then he disappeared without a word. I can't remember if I ever downloaded, compiled and ran his code.

I have about 15 GB of source code, docs and data related to Sudoku and CSP-Rules (not including my books and related documentation). (This is not very large, but it contains almost no compiled code.) Most of it is my own developments. But a small part of it is a "solvers" folder, where I have SE, Hodoku and a few minor ones that I never use. It doesn't contain Paul's solver. I'm generally quite systematic in organising my files; if it is not there, it is unlikely to be anywhere else. I have no additional external files.

If you're interested in coding whips, I think it can be done from nought and it's not a particularly hard challenge if you have the right data structures.

[yzfwsf]

Where's the original place of the first post (to Matt)?

http://programmers.enjoysudoku.com/www.setbb.com/sudoku/viewtopic966f.html?mforum=sudoku&t=1795&postdays=0&postorder=asc&start=0&mforum=sudoku

If you're interested in coding whips, I think it can be done from nought and it's not a particularly hard challenge if you have the right data structures.

I think the dynamic chain in my program should be equivalent to the Braid you mentioned, but at this stage I only use singles to dynamically expand. And whips should be a limited version of this dynamic chain, that is, the current node must inherit from the previous A node, and the dynamic part must be a direct ancestor (Z, T...candidate number in your words?), I would call it a memory chain.

[denis_berthier]

If you're interested in coding whips, I think it can be done from nought and it's not a particularly hard challenge if you have the right data structures.

I think the dynamic chain in my program should be equivalent to the Braid you mentioned, but at this stage I only use singles to dynamically expand. And whips should be a limited version of this dynamic chain, that is, the current node must inherit from the previous A node, and the dynamic part must be a direct ancestor (Z, T...candidate number in your words?), I would call it a memory chain.

To use your words, whips and braids "use only Singles to dynamically expand". The difference with your "dynamic chains" is not there. It is in the way you define their complexity. As far as I understand it, you use the same definition as Sudoku Explainer (SE), i.e. the number of "nodes", i.e. the number of inferences before a contradiction is reached. Whips and braids use the number of CSP-Variables, which in the present case should be equal to the number of times Singles are used before the contradiction (+1).
If you use the SE definition, I can see no reason to give them another name. If you use my definition of length, they are braids or whips and calling them by another name would be mere plagiarism.

[yzfwsf]

In fact, my purpose of writing the solver is not to rate the puzzle, but to provide users with as many perspectives as possible to solve the puzzle, so the chain is just a technique in my solver. It has the same status as other techniques. For this purpose, the length of the chain is not deliberately limited when writing the chain, and the only exit condition is to find a reasonable elimination or set number.
You use length to express the difficulty, I think it is not accurate too, the same length of whips, the subsequent node n, your Ln link to z or k (0<k<n-1) times are not the same, I think the difficulty Should be different.

[denis_berthier]

In fact, my purpose of writing the solver is not to rate the puzzle, but to provide users with as many perspectives as possible to solve the puzzle, so the chain is just a technique in my solver. It has the same status as other techniques. For this purpose, the length of the chain is not deliberately limited when writing the chain, and the only exit condition is to find a reasonable elimination or set number.
You use length to express the difficulty, I think it is not accurate too, the same length of whips, the subsequent node n, your Ln link to z or k (0<k<n-1) times are not the same, I think the difficulty Should be different.

Should I conclude you use the number of "nodes"/inferences. Then why would you use a different name for your "dynamic chains" as the usual one? "Memory chains" is a recent invention with no precise meaning. (Indeed, it was introduced with the explicit purpose of creating confusion).

You cannot expect to have a rating that gives a different value to each puzzle. Whether you choose the number of inferences as in SE or my definition of length, a rating can never be accurate. Indeed, the word "accurate" has no meaning in this context. Accurate wrt what?

[yzfwsf]

At this stage, my solver contains 2 types of dynamic chain categories, Dynamic Verity Chain and Dynamic Contradiction Chain. I haven’t written whips yet, but it seems that your whips does not support continuous loops. If you let it support continuous loops, I don’t know if it can be called whips.

[denis_berthier]

At this stage, my solver contains 2 types of dynamic chain categories, Dynamic Verity Chain and Dynamic Contradiction Chain.

I don't know what you call "Dynamic Verity Chain". Aren't they dynamic forcing chains (in SE terminology)? If yes, calling these chains (as SE does) is very misleading, when the starting point is a big OR branching and you have to follow two (or 3 or more) streams of inferences.

I haven’t written whips yet, but it seems that your whips does not support continuous loops. If you let it support continuous loops, I don’t know if it can be called whips.

I'm not sure what you call continuous loops, but if they are bivalue chains (= basic AICs), as Hodoku defines them, then they are obviously a special case of whips.
A bivalue-chain can be called a whip, though this is a very imprecise naming for it.

[yzfwsf]

The same conclusion can be obtained by set a certain number and delete a certain number in one cell, it is called Dynamic Verity Chain.
The dynamic continuous loop can contain different types of nodes, such as ALS, Almost Fish, Almost UR, etc.

[denis_berthier]

The same conclusion can be obtained by set a certain number and delete a certain number in one cell, it is called Dynamic Verity Chain.

It's not exactly what I was thinking of, but my remark still applies: you start with an OR-branching and you have to follow 2 streams of reasoning in parallel.

The dynamic continuous loop can contain different types of nodes, such as ALS, Almost Fish, Almost UR, etc.

Now, you have a big problem of terminology. Who can guess that "dynamic" means the inclusion of such patterns - especially when it means something totally different in SE?

[yzfwsf]

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

I think there are some backwards in the chain.Same as: A(False) -> B(True) -> A(False)
Is this happening by design?

[DEFISE]

Hi yzfwsf,
To avoid this kind of loop Denis used a whip[11] instead of a whip[10].
This is what he explained to me here:
extreme-puzzle-no-5-t37866-45.html#p290790