The New Sudoku Players' Forum

[DonM]

I have never seen you solve a long, complex puzzle using your notation and that includes all those years when advanced solving was occurring on the Eureka forum and sometimes here. Unless I have missed it, it has always been for one-steppers or just where there are 2 or 3 lines of code. In other words, how can you fairly compare these two notations where just a few lines of code are required?

First you call me talented and gifted solver, and then you do not believe yourself ?
I have solved such puzzles before i even knew, what an AIC is. But i stopped it as a waste of time. Why should i spend 4 hours to solve it and 2 to write down a solution, which no one is interested in ? Bad for you.
My way of solving never changed with knowing AIC's. These "or", "then not", "then" (or should i say "equal", "minus", "equal" ? ) were natural for me - and self-detected, if you believe it or not.

Okay, let me rephrase: I was not suggesting you couldn't solve long, complex puzzles, I was saying that you haven't solved any that I have ever seen so I could tell how your notation compares to Eureka notation in efficiency and clarity. That's exactly why I challenged you to present a full solution of Gurth's puzzle so I could see such an example and comparison.

You said, ' Why should i spend 4 hours to solve it and 2 to write down a solution, which no one is interested in ? Bad for you.' Well, yes, that was bad for me and bad for everyone because I/we probably could have learned a lot from you. It's too bad that you so stubbornly resisted using the Eureka notation so we could benefit from your solutions of difficult puzzles.

[eleven]

It's too bad that you so stubbornly resisted using the Eureka notation so we could benefit from your solutions of difficult puzzles.

No, i am not a Steve K. or RW, who had really new ideas, independant of the notation.

[denis_berthier]

loop
   ...AIC notation... | ...manual solvers...
endloop

[DonM]

loop
   ...AIC notation... | ...manual solvers...
endloop

Appreciate the the compliment.

[David P Bird]

OK after some time considering the discussion here, these are the main points that I would like to make:

To the players who are trying to change the way we notate chains:
1) By all means define a new Forcing Chain notation but if you do there must be a reference source for it available. We have already seen that comments in the puzzles section aren't sufficient because they aren't followed by all and anyway they get forgotten.
2) However it would be better for the community as a whole if we continue to use a common compromise notation that will serve for both uni- and bi- directional logic.

Eleven
1) The biggest problem that new players face is understanding OR/NAND chains and recognising that OR is not the same as XOR. The notation issues are minor in comparison.
2) The endless discussions by and large are by people who want to tailor a compromise notation to exactly match their needs. The system itself is sound.
3) The example notation you provided does not translate into a straightforward and ordered set of logical statements that prove the elimination.

In general
1) We must make our work accessible to others otherwise the forum will slowly die.
2) Our lack of up to date reference sources is a hindrance, but anyone who tries to rectify that is in for a rough ride in the current climate.

[denis_berthier]

The biggest problem that new players face is understanding OR/NAND chains and recognising that OR is not the same as XOR. The notation issues are minor in comparison.

I can agree that notation is not the main problem, although AIC notation IS a problem in and of itself.
The main problem is to have the correct resolution model and the correct basic concepts.

Moreover, I consider it very misleading to speak of "OR/NAND chains".
You correctly point out that "OR is not the same as XOR".
But you should write that all the chains (whether reversible or not) are "XOR/NAND".

it would be better for the community as a whole if we continue to use a common compromise notation that will serve for both uni- and bi- directional logic.

But you will have to acknowledge the fact that a chain that is reversible in some abstract logical sense may not always be written in a reversible way. I suggest you have a look at chapter 9 (or just at Figure 9.1) of my last book "Pattern-Based Constraint Satisfaction ..." (1st edition freely available as a pdf).
As I can see from my random occasional looks at various threads in this part of the forum, trying to write some reversible chains in an explicitly reversible way is the cause of many illegible writings.

[David P Bird]

Denis, as I hope you appreciate, I was attempting to cut everything to the bare bone and focus on the key points. So I'm afraid my statements aren't all embracing but only relate to the methods employed by the contributors to this puzzles section.

But you should write that all the chains (whether reversible or not) are "XOR/NAND".

I've always considered that theoretically it's possible to start chains from an OR inference where both arguments could be true. These have been called strong-only links because it's impossible for both terms to be false. For example if two cells contain three candidate digits there is a strong-only link between two of them as they would both be true if the third one is false. (I know there is a far better example available involving pattern nodes but I'm blowed if I can remember it now.) So if a chain can contain a single OR it would be wrong to call it a XOR/NAND chain. Interestingly, omitting the 'passenger' digits from the almost naked set nodes is one of the items the advocates for change want to implement.

But you will have to acknowledge the fact that a chain that is reversible in some abstract logical sense may not always be written in a reversible way.

Just as you don't delve into subjects that aren't of direct interest to you, nor do I. Consequently I can't debate the properties of all possible chaining methods. At the birth of the Eureka system one of the requirements was that every inference had to be completely independent of any other assumptions. I believe this then guarantees the chains are bidirectional.

Some people do use 'memory chains' by adding asterisks to remembered candidates and the ones they affect later in the chain which simulates your approach to some extent. As these asterisks indicate the chains aren't Eureka AICs they don't cause a great problem, except in situations involving the distribution of the true digits in a pattern which aren't so easy to recognise.

BTW I would still love to see what you could achieve in finding the optimum solution path for a puzzle. There is a balance between the number of steps taken and their complexity to be considered which could provide interesting variations.

David

[denis_berthier]

But you should write that all the chains (whether reversible or not) are "XOR/NAND".

I've always considered that theoretically it's possible to start chains from an OR inference where both arguments could be true. These have been called strong-only links because it's impossible for both terms to be false. For example if two cells contain three candidate digits there is a strong-only link between two of them as they would both be true if the third one is false.

I can't see your point. For the two cells, say (r, c) and (r, c'), you have XOR(n1rc, n2rc, n3rc) XOR(n1rc', n2rc', n3rc'). I don't see how you turn this into a chain.
In any case, the fact that all the chains are XOR/NAND is the fundamental of AICs, or it should be if AIC is intended to mean anything.

Some people do use 'memory chains' by adding asterisks to remembered candidates and the ones they affect later in the chain which simulates your approach to some extent.

What I called above "pretending not to be aware of previous work and thus re-inventing the wheel", all this being dissimulated by a different vocabulary and obscure notation.
BTW, they provide additional examples that "my" oriented chains are used by manual solvers, contrary to DonM's claims.

BTW I would still love to see what you could achieve in finding the optimum solution path for a puzzle. There is a balance between the number of steps taken and their complexity to be considered which could provide interesting variations.

This is totally unrelated with the above discussion.

Unfortunately, in spite of the multiple tries about rating the global resolution path, nothing consistent has ever been written on this topic, and I'm no better than anyone else on this very difficult point. Moreover, as I have no reasonable idea of how to deal with it, I'm not at all working on it.

Given a resolution path, some post-processing can be considered in order to clean it: proceeding backwards from the end of the path, delete some eliminations not necessary for the subsequent parts of the path.
I have done this in PBCS2 when I used CSP-Rules as an assistant theorem prover to show that many "classical" rules of Slitherlink are equivalent to sequences of short whips. But this is purely cosmetic. Generally, I'm too lazy to do it manually.

To give you a slight idea of the basic questions that should be solved: how do you compare a path using 5 patterns of size 4 and a path using 3 patterns of size 6 (all the rest being singles, to make the question simpler)? (You can replace "pattern" by any fixed pattern, among your preferred ones.)

More generally, I'm not even sure the question is meaningful. I have shown in great detail that there cannot be a single hardest-step rating, but that one must choose a rating consistent with their resolution model and adapted to their purposes or personal preferences. I think this applies with still more strength to potential ratings of the global path.

As an illustration, I gave a very easy solution of the first puzzle in this thread, based on 4 or 5 elementary chains (the most basic AICs) plus a single whip[3]. Other people gave what they call "one-step" solution - using much more complicated and longer patterns. They are so artificial that I can't see by which rational standard they could be claimed simpler than mine. In any case, not just because they can be written in only one line of hermetic symbols in (pseudo-)AIC notation: this only line required pages of explanations to be understood (even by people supposed to be proficient in AIC notation).

[eleven]

Eleven
1) The biggest problem that new players face is understanding OR/NAND chains and recognising that OR is not the same as XOR. The notation issues are minor in comparison.

My chains aren't OR/NAND chains, but simple implication chains. Every school child should know what "if this then that" means.

You just have to be a bit careful with the starting point "A or B": at least one of them must be true.
The second hurdle then is to determine the eliminations. E.g. it is not obvious for everyone, that "1r1c1 or 2r1c2" implies r1c1<>2.
But these two points are independant of the notation again.

2) The endless discussions by and large are by people who want to tailor a compromise notation to exactly match their needs. The system itself is sound.

The logic is sound, but as said, not the definition of the notation.

3) The example notation you provided does not translate into a straightforward and ordered set of logical statements that prove the elimination.

??

[David P Bird]

Denis, given this AIC (1)r3c1 – (12=3)r1c13 – (3)r2c3, it's apparent that digit 2 in the middle node is a passenger and can be omitted when we get (1=3) as a OR relationship not an XOR one. In words: for a container that can only hold two objects to be full, with three possible candidate objects available, no two of them can be simultaneously absent. I'm sure I haven't expressed that as well as you would like but I hope it makes my point clear.

Omitting the (2) however means the expression fails to specify (by convention) that there are only three candidates available so needs to be supplemented by a grid diagram for that to be apparent, but the proponents for the change are quite happy about that.

The pattern based strong-only link I was trying to remember is between two possible disrupting candidates for a deadly pattern that would result in a contradiction (or – under my breath - two possible solutions).

Perhaps there is a mathematically precise way of defining these situations in strictly XOR terms but the question I and most other players would raise is would there any practical benefit from doing that?

I honestly think you are being over-sensitive about the memory chain issue. Taking a view that you will probably consider simplistic, memory chains are just another way of expressing net based deductions. At one stage on the Eureka forum I was calling them accumulating chains because as they passed through different cells they accumulated equivalent truths and the idea was far from new then. Memory chain users are using very simple forms of these in comparison to the extent I think you can extend yours. What your intellectual property right might cover is the way you have packaged the various elements you use together.

On the off-topic aside, when I was trying to find the shortest solution paths for moderately difficult puzzles I tried several techniques. The best results came from combining two strategies when very basic eliminations are considered to have zero cost.
1. Identify the most difficult step required when every easier elimination available is made first, and then attack the puzzle again enabling all methods up to that difficulty from the start prioritising those that made the most eliminations first.
2. Identify key candidate eliminations that could only be made one way and try to pave the way to make these as early on as possible.
We are agreed there is no one answer to this problem but I still think exploring the options is interesting.

David

[denis_berthier]

Taking a view that you will probably consider simplistic, memory chains are just another way of expressing net based deductions.

Not only simplistic but false, because based on a confusion between AND-branching and OR-branching.
Using t-candidates in subsequent deductions is a perfectly natural kind of AND branching (re-using what you already know from the previous parts of the chain). But in a real net, you have OR branching, i.e. bifurcation wrt several possibilities; it means following two (or more) independent streams of reasoning. Logically, it means allowing inference steps with disjunctive conclusions, i.e. of the type A...... => B OR C.
None of my chains have OR-branching.
Be it for a human or a computer, OR-branching introduces a very high computational cost. Surprisingly, it doesn't provide any clear advantage in Sudoku: my statistical analyses showed that forcing whips (that include a slight form of OR-branching) are not more powerful than whips.

At one stage on the Eureka forum I was calling them accumulating chains because as they passed through different cells they accumulated equivalent truths and the idea was far from new then.

I remember well. You introduced this "accumulating" word in one of my Eureka threads about what I called nrczt-chains at that time. Sure, considering all the reactions it provoked, the idea of allowing t-candidates in a chain was new at that time.
I'm sad to see that almost ten years later, the same OR vs AND branching confusion remains part of the AIC credo. Sad, but not really surprised: if you live in a world made of only reversible patterns, there can be no difference. AND and OR branching are pure evil and must both be excommunicated (also in the literal sense: excluded from any communication).

On the off-topic aside, when I was trying to find the shortest solution paths for moderately difficult puzzles I tried several techniques. The best results came from combining two strategies when very basic eliminations are considered to have zero cost.
1. Identify the most difficult step required when every easier elimination available is made first, and then attack the puzzle again enabling all methods up to that difficulty from the start prioritising those that made the most eliminations first.
2. Identify key candidate eliminations that could only be made one way and try to pave the way to make these as early on as possible.
We are agreed there is no one answer to this problem but I still think exploring the options is interesting.

Exploring this on particular puzzles is one thing and I have no doubt you can find interesting examples.
However, there is a huge gap between finding interesting examples and formulating any consistent general theory/method/idea/whatever, which is the only thing that could motivate me.

[DonM]

David, I see a futility in your attempts at diplomacy when the other party is entrenched in a belief system that may work in a math logic theory and related computer programming classroom, but makes absolutely no noticeable contribution to manual sudoku solving (which, as much as db wants to ignore it, is still presumably, the main purpose of this forum) and is not making any practical suggestions that would help the solvers on this forum. Do you see any evidence of the slightest constructive compromise above?

Not to mention that: How can there be any common ground in a situation where one party is recognizing that the problem isn't the notation itself, but how the notation is being used (and is trying to address that problem) while the other party would rather see the standard notation replaced with his own? To cut to the chase: If db would rather torpedo the Eureka/AIC notation entirely, then what's the point of all this?

Further, much as db wishes to denigrate my repeated emphasis on 'manual' solving', IMO manual solving is as much a part of this subject as the notation is. The problem with a notation created by a computer programmer is that a) sudoku's original creation was for human manual solving and b) the presence of a computer-created notation would likely mean that it could or would eventually solve all/most puzzles using that notation which would remove the challenge of manual solving altogether. The computer and the programmer would be the 'mother' of the entire creation and result.

Unfortunately, we're already half way (or more) there when it comes to the intrusion of computer solving into the human solving of puzzles except that it occurs to me that it is the very presence of the Eureka notation that still allows for manual solving challenges with more difficult puzzles because the current main 2 computer solvers fall flat in attempts to notate them.

[ronk]

DonM,

Readers here, including me, would better understand your reason for conflating the subjects of manual solving and notation if you provided an example or two where, as you say, the Eureka notation provides an advantage. The complexity of the examples should be consistent with the solutions being posted here, by near-beginners in some cases.

[JasonLion]

But you should write that all the chains (whether reversible or not) are "XOR/NAND".

I've always considered that theoretically it's possible to start chains from an OR inference where both arguments could be true. These have been called strong-only links because it's impossible for both terms to be false. For example if two cells contain three candidate digits there is a strong-only link between two of them as they would both be true if the third one is false.

I can't see your point. For the two cells, say (r, c) and (r, c'), you have XOR(n1rc, n2rc, n3rc) XOR(n1rc', n2rc', n3rc'). I don't see how you turn this into a chain.
In any case, the fact that all the chains are XOR/NAND is the fundamental of AICs, or it should be if AIC is intended to mean anything.

An AIC alternates between strong and weak links.

A weak link means that the two ends can not both be true, which corresponds to NAND.
A strong link means that the two ends can not both be false, which corresponds to OR.

Thus an AIC is an OR/NAND chain.

In practice, most strong links are also weak, and thus correspond to XOR. However this is not always true, and is not required for the logic of an AIC to work.

For more detail, see http://sudopedia.enjoysudoku.com/Inference.html or http://sudopedia.enjoysudoku.com/Alternating_Inference_Chain.html.

[David P Bird]

The example notation you provided does not translate into a straightforward and ordered set of logical statements that prove the elimination.

??

Eleven, by refusing to even try to work out what I am saying in my third point you are making this exchange between us far more painful than it need be. Previously I even gave you an example of a notated chain segment translated into English to help you which I wonder if you even looked at.

Your English is very good, so please tell me what part of my sentence you don't understand and I will reword it if necessary.

When we have worked this through I hope that you will see that your example notation does not qualify as being a stream but is more a whirlpool of different facts.

David