The New Sudoku Players' Forum

[denis_berthier]

Denis,

When you wrote your new version of SudoRules, all of the (h)xy(z)(t)-chains went away, and were replaced by nrc(z)(t)-chains (at least in the solutions I've seen). Of course, xyt, xyzt and hxy-chans are all subsumed by nrczt-chains (as I think you mentioned earlier), but what happens to hxyt and hxyzt chains? It seems that these should still be giving you something extra. Do you have any such examples? Are hxy(z)(t)-chains still implemented in SudoRules? And have you tried going one step further and implementing hnrc(z)(t)-chains?

SudoRules 13 is an extension of SudoRules 12. All that was in version 12 is totally unchanged. In version 13, only 3D chains (nrc-, nrct-, nrczt-) have been added.

For any puzzle, there are lots of possible solution paths.
SudoRules choices rely on the priorities ascribed to the rules.
2D chains are chains of cells in 2D spaces (rc-, rn-, cn-). All their links are in the same 2D space.
3D chains are chains of cells in 3D-space (nrc-space), i.e. chains of candidates.Their links are in 3D space, they are more complex.
When the two types of chains are mixed, some penalty should be put on the 3D chains wrt the 2D chains of the same length (unless one considers that spotting a bivalue is as easy as spotting conjugate candidates).

This penalty is a parameter in SudoRules. In all the examples I've given, it was set to 0, in order to illustrate the new rules. But, if you change the penalty, 2D rules will be applied more often. On the contrary, if you put a very high penalty, 3D rules will appear very rarely.
With penalty 0, as there are more possibilities with 3D chains than with 2D, 3D chains appear more often than 3D. But 2D chains also appear sometimes.

[denis_berthier]

And have you tried going one step further and implementing hnrc(z)(t)-chains?

I had missed that part of your post.
nrc(z)(t) chains are their own hidden (and super-hidden) counterpart.
This is because all the concepts used in their definition are super-symmetric.

[denis_berthier]

Here is the forum where your xyzt chain are under discussion. It is probably the best french forum investigating new tools.
http://www.sudoku-factory.com/forumsudoku/

I've looked at the http://www.sudoku-factory.com/forumsudoku/.
But I haven't been able to find anything about xyzt-chains. Only xyz-wings.
Looks like there's no discussion at all on any advanced topics.
Do you have a more precise reference?

I am personnaly working with a small group on the Figaro Sudoku forum mainly with puzzles at the level of step1.

I haven't been able to find any Figaro subgroup with any post of yours. I searched for "champagne". True, I didn't spend hours trying and I may have missed something. Or are you using another name there?
You said "I have a method widely disclosed in French forums, not only by me". Where exactly did you (or anybody else) post your algorithm ?

[champagne]

Denis wrote

I've looked at the http://www.sudoku-factory.com/forumsudoku/.
But I haven't been able to find anything about xyzt-chains. Only xyz-wings.
Looks like there's no discussion at all on any advanced topics.
Do you have a more precise reference?

The topic discussing some of your "rules" is
"hier hypothèse, aujourd'hui technique, la chaîne xyt".

But may be this is not the last "rule" you introduced.
This is the place where I found the link to your thread and, by the way, the list of puzzles gsf proposed as test of solving capabilities.

Denis wrote

champagne wrote:
I am personnaly working with a small group on the Figaro Sudoku forum mainly with puzzles at the level of step1.


I haven't been able to find any Figaro subgroup with any post of yours. I searched for "champagne". True, I didn't spend hours trying and I may have missed something. Or are you using another name there?
You said "I have a method widely disclosed in French forums, not only by me".
Where exactly did you (or anybody else) post your algorithm ?

Several questions.

1) Figaro forum
http://forums.lefigaro.fr/user/non-frames/list.asp?forumid=258

2) My pseudo on the Figaro Forum is gpenet (for gérard PENET). I found more fun using "champagne" outside of France.

3) full tagging method

You have a very good presentation of step one and some opening on step two in a thread prepared by PhB in

http://www.sudoku-factory.com/forumsudoku/.

The title is : Technique: Le coloriage pour les nuls.

Nearly at the same moment (end of September 2006), I published my own text on the Figaro forum under the title

"Marquage coloriage".

(We exchanged our drafts before publishing).

Extensions to step two and step three have been developped by me in autumn 2006. This has been explained on the Figaro Forum in several threads.

My Thread on the "full tagging method" summarize what has been done. Nevertheless, as the public is here supposed to be expert, I did not enter into details for step one. In case you would have difficulties with my wording, reading of anyone of the two detailed publication on step one should answer your questions.



===============

I think I covered your points. Just to have a feeling of the power of your method, how do you solve the puzzle I proposed.

More important to me : do you have a solution for one of the puzzles (unsolved on my side) I extracted from the gsf's list.

[denis_berthier]

do you have a solution for one of the puzzles (unsolved on my side) I extracted from the gsf's list.

My computing ressources are limited and I haven't yet had time to check this.
You must understand that my priority is not solving any puzzle (which anybody can do using uncontrolled propagation of constraints) but solving puzzles with a sequence of well defined resolution rules (as defined in my posts).
Look at my examples to have a clear idea of what I mean.
Even with such constraints on what I consider acceptable, I can solve at least 99.99% of the random puzzles.

[ronk]

You must understand that my priority is not solving any puzzle (which anybody can do using uncontrolled propagation of constraints) but solving puzzles with a sequence of well defined resolution rules (as defined in my posts).

Denis, any resolution rule is derived from the over-arching rule that each number exist in each row, column and box exactly once. Restricting oneself to one set of derived resolution rules is, to my mind, like volunteering to put on a strait-jacket.

[champagne]

Denis wrote


My computing resources are limited and I haven't yet had time to check this.
You must understand that my priority is not solving any puzzle (which anybody can do using uncontrolled propagation of constraints) but solving puzzles with a sequence of well defined resolution rules (as defined in my posts).

Frankly, Denis, we have to stay zen. I am following resolution rules and resolution process to solve puzzles. My computer can not work without precise rules..

When I started developing “full tagging” late 2005, my target was to stick to process workable without a computer.

It happened that, trying to pass resisting puzzles, I solved nearly all puzzles (to be honest, another guy did it before me, based on the same “step one”, but he gave up before disclosing in detail the “rules”).

For sure, having reached such a score, I am willing to jump the final fence and solve some more puzzles.

It’s a kind of game. My main goal is still to coach experts in “hand solving” (I am not).


As far as rules are concerned, I am certainly very restrictive. For me, “forced chains” and any derived form of it is a form of T&E. This is not the common agreed border.

Denis wrote

Even with such constraints on what I consider acceptable, I can solve at least 99.99% of the random puzzles

I have some hundreds of identified unsolved puzzles. I don’t know what it means in terms of percentage.

Most of these puzzles have been published late 2006 beginning of 2007.

Anyway, I think that the most important is “what can be handled without a computer”.

This excludes for sure all puzzles needing step 3 on my side, and most likely a significant part of puzzles requesting step 2.

I think the puzzle I proposed is still to day out of the scope for hand processing. I am convinced that next year it will not be the case.

For puzzles out of gsf’ list, I have no idea. Nobody came with a non T&E proposal.

[denis_berthier]

Denis, any resolution rule is derived from the over-arching rule that each number exist in each row, column and box exactly once.

The difference is that these "over-arching rules" are not resolution rules but constraints. They don't tell you: in such situation, do this. As you read my book, you know the difference.
Any resolution rule is derived from these constraints, in the sense that it is a Sudoku theorem. That's the only thing that can guarantee its validity.
But, as you must know, a theorem is not known before being formulated.

Restricting oneself to one set of derived resolution rules is, to my mind, like volunteering to put on a strait-jacket.

I never said I restricted myself to my current set of resolution rules. The best proof is that I've recently introduced the whole family of the nrc(z)(t) rules.
But I'm definitely restricting myself to resolution rules (I've introduced a tagging algorithm, but it's only a marginal illustration of one among many possible ways of spotting chains).
Resolution rules are the only guarantee that we are not using disguised forms of T&E.
Strangely enough, my thread on "the notion of a resolution rule" as not generated replies (contrary to what happened in the Eureka forum). But, in this thread, I explain how this concept allows one to make the difference between T&E (as a well defined resolution technique) and a logical solution (a sequence of valid resolution rules).

[denis_berthier]

Champagne
As of now, you have described a recursive tagging algorithm that uses well known rules.
I'd say you have an implementation of these rules.
You say it is efficient in terms of computation time. Congratulations. How efficient is it in terms of memory?

As I'm not really interested in implementation details, my main question is:
do you have any new resolution rules?
(I mean not necessarily in the formal sense I've defined, but something like Quads or xy-chains, that everybody can understand and use independently of your implementation)
Of course, if such is the case, can you give an example?

[champagne]

Denis wrote

Champagne
As of now, you have described a recursive tagging algorithm that uses well known rules.
I'd say you have an implementation of these rules.
You say it is efficient in terms of computation time. Congratulations. How efficient is it in terms of memory?

As I'm not really interested in implementation details, my main question is:
do you have any new resolution rules?
(I mean not necessarily in the formal sense I've defined, but something like Quads or xy-chains, that everybody can understand and use independently of your implementation)
Of course, if such is the case, can you give an example?

Hello Denis,

Several questions in few lines. Let me try to answer properly.

Preliminary statement, for me Sudoku is a pure hobby among others. I do not intend to cover the entire field. Opposite, I am trying to use the smallest possible number of rules, eliminating all subsets of the main rule. I came to post my process to share what seems to be interesting results.


Now your points:

1) Computation time and memory

I am not sure that with today's PCs this is really a topic but I will answer.

For me absolute values for computation time is not the point. More important is the scale from step 1 to step 3. This is the reason why I gave average values. I don’t know what other solvers do.


Regarding memory, needs are increasing from step one to step three. I gave a rough idea in my thread. In step one, the number of layers is about 15. In step two, it jumps to about 150 to 200.

The number of relevant weak link follows the same path. Let me take an example at the start of the puzzle I proposed.

Step one: 57 relevant weak links, 45 layers;
Step two: 1869 relevant weak links, 230 layers.

For sure, these data are in memory.

2) New rules!!!

I described the rules I am using in my post. May be you have difficulties to figure out that with such a small number of rules you can solve nearly all puzzles.

Anyway, I will add to my post a summary of the “rules”

As I stated in the beginning, the key rule is “alternate chain”. It’s a well known process. Ronk and Re’born had no problem to crack my solution for the puzzle I proposed.

Step one is not more than giving an easy way to find out existing Alternate chains.

Complementary rules are shown in step two:

- ALS an “Almost cell” extension (which is not exactly a rule),
- ‘Choice’s rules.

Sorry, but there is nothing more. After having added the new stuff, and ‘choice’s multi-chains effects, no new code is needed.

To answer your remark on ‘reuse of my rules’, multi chains associated with a choice are often shown as nets of alternate chains.

In fact, all I am doing can be done without tagging. The question is “How can you identify the efficient alternate chains”. In hardest puzzles, tags are just an internal way to handle the logic. Prints are made showing alternate chains in a standard form.



As I mentioned, I am working on creating a reduced step two to stay within hand solving capabilities.

What about new rules. I have to implement a fourth step to solve resisting puzzles. I have some ideas. Again, I do not want to cover the entire filed, so I am in priority thinking on rules easy to integrate in “full tagging”.

I have some doubt that such extensions could be of any use in hand processing.

[denis_berthier]

CLASSIFICATION RESULTS FOR 3D CHAINS, or fully supersymmetric chains or nrc(z)(t)-chains

Although there is no reason for this, chains remain frightening for some people.
This problem may be the result of the language often used to speak of them ("weak" and "strong" links, …), confusing a factual presence of a pattern on a grid and the way a theorem allowing to draw conclusions from it has been proven once and for all.
Chains are no more and no less patterns than any other pattern (e.g. fish or pairs).
The following results show that most of the time, chains needed to solve a puzzle can be of very limited length.

Definitions
Basic resolution rules (the L4_0 level in my book) are defined as:
- Subsets of length 1 to 4: Naked + Hidden + Super Hidden (fish)
- Basic Interactions
- XY-Wing, XYZ-Wing

Levels L4,… Ln are defined as:
Ln = basic rules + 2D chains, i.e. (h)xy(z)(t)- and c- chains, of length no more than n; the length of a 2D chain is defined as the number of cells on which it lies (in its base space: rc-, rn- or cn- ), target not included;

Levels M4,… Mn are defined as:
Mn = Ln + 3D chains, i.e. nrc(z)(t)-chains, of length no more than n; the length of a 3D chain is defined as the number of cells on which it lies when considered as a chain of cells (i.e. half the number of its linking candidates), target not included.

This convention amounts to considering bilocation links as equivalent to bivalue links, i.e. to putting no penalty on 3D chains wrt 2D chains of the same length. This is the stance usually adopted by adpets of AICs. But SudoRules could be used with other conventions.

Collection of puzzles used for these results
The Sudogen0 collection has been used.
Remember that it is a randomly generated collection of minimal puzzles; it was generated with the suexg / suexco generator from Magictour. It is available on my web pages.
(Remember that "minimal" means that if a clue is deleted, then the resulting puzzle has more than one solution).

Classification results
The following table gives the number of puzzles solved at each level, in the L and M classifications.

level.......4..........5............6...........7
L.........8271.....8959......9326.......9472
M........9638.....9893......9964.......9984

(Notice that all the remaining 16 puzzles are also solved by SudoRules, but with longer chains).

Comments
As can be seen from these tables,
- ~99% of the randomly generated minimal puzzles can be solved with 3D chains of length no more than 5;
- almost all (99.84%) the randomly generated minimal puzzles can be solved with 3D chains of length no more than 7.

3D chains are harder to discover than 2D chains, but they allow to consider only short chains, compatible with the idea taken from psychology that a human being's short term memory has size 7 (+-2).

[champagne]

Hello Denis,

Generally speaking, I feel comfortable with your post. Applying “full tagging” process, I have different views on some points I’ll comment.

I have a preliminary question:

Denis wrote:

This problem may be the result of the language often used to speak of them ("weak" and "strong" links),

I am using these two concepts as they have been created and named in MEDUSA

Here what I wrote in my post.

- Strong Link: An exclusive couple of 'group's having the following properties
- If one is part of the solution, the other is not,
- At least one is part of the solution.

- Weak link: only the first statement of the previous definition is valid.
as a matter of fact, a strong link can replace a weak link in a chain

After one year experience solving thru alternate chains thousands of puzzles, I can’t figure out what problem can raise from these precise definitions.


Denis wrote:

Although there is no reason for this, chains remain frightening for some people.

This is true and “full tagging” offers a way to find them. Some don’t like the preliminary tagging task.


Denis wrote:

The following results show that most of the time, chains needed to solve a puzzle can be of very limited length.
….
3D chains are harder to discover than 2D chains, but they allow to consider only short chains, compatible with the idea taken from psychology that a human being's short term memory has size 7 (+-2).

With “full tagging”, we see things differently:

- No difference locating 2D and 3D chains. May-be, if the pattern is very simple, you’ll have evidence of a chain during the tagging process.
- The length of a chain can be significantly reduced with “full tagging”. From my experience, a closed chain with more than 5 steps is uncommon.
- I know you don’t like closed chains, but with “full tagging “, they are much easier to apply. Open chains (-./…/._) require additional search to see whether they have capacity to eliminate candidates. In ‘full tagging’ such chains are normally in the range of one to three components.

[denis_berthier]

Champagne
I've already described a tagging algorithm associated to my nrc(z)(t)-chains. I know that, for many players, tagging is not a very exciting perspective.
Moreover, an algorithm is only an algorithm.
What players want is a set of independent rules that can be applied individually.

Your claims about chains of length 3 solving almost anything in the context of your tagging algorithm seem very unrealistic and you don't provide the smallest piece of evidence for it. It is contrary to all known evidence about all patterns of length 3 (not only chains).

Your claims about making no difference about 2D and 3D chains merely amount to saying that 3D chains subsume 2D chains, which has always been obvious. Saying that 3D chains are no more complex than 2D chains is a progarmmer's POV, not a player's.

I repeat the question you never answered: can you describe any resolution rule that could be used by any player without taking your whole algorithm?

[champagne]

Hello Denis,

I am highly surprised by your answer.


Denis wrote

I repeat the question you never answered: can you describe any resolution rule that could be used by any player without taking your whole algorithm?

I don't understand. Step one of my process is the answer. You can find hundreds of puzzles solved using only step one on the "Figaro forum".

They have been solved by guys who did it without help of a computer.




Denis wrote

Your claims about chains of length 3 solving almost anything in the context of your tagging algorithm seem very unrealistic and you don't provide the smallest piece of evidence for it. It is contrary to all known evidence about all patterns of length 3 (not only chains).

Let's try, propose a puzzle and we will see how the solver behave. As I told you, a pattern of lenght 3 in "full tagging" can have longer corresponding patterns out of "full tagging".

My claim for closed chains is precisely

- The length of a chain can be significantly reduced with “full tagging”. From my experience, a closed chain with more than 5 steps is uncommon.


denis wrote

Your claims about making no difference about 2D and 3D chains merely amount to saying that 3D chains subsume 2D chains, which has always been obvious. Saying that 3D chains are no more complex than 2D chains is a progarmmer's POV, not a player's

.

For sure, 2D is a subset of 3D. The fact is that when you start tagging as in step one, it's not a big difference doing it immediatly in 3D. Finally, you are working on a 3D tagged puzzle, and, then, your have a blind search for both 2D and 3D.

As far as I know, nobody does it in two steps: 2D then 3D. My solver can do it optionnaly, but I rallied the most commun way to handle puzzles manuallly, stepping directly in 3D.

[Ruud]

What players want is a set of independent rules that can be applied individually.

Did you conduct a survey to arrive at this conclusion?

After spending more than 2 years amongst Sudoku players, I still don't know what they really want, besides a continuous supply of challenging puzzles.

Ruud