The New Sudoku Players' Forum

[Steve K]

Denis, it is fairly clear that you have not read many examples whereas I use TM's. Unfortunately, if you had you would know that "grouping" of candidates within a Boolean is specifically addressed. Then, it would have been clear that the mapping expressed by me above does work, and is a proof.

Your invalid disproof ignores the fact that the mapping I show addresses your concerns. In other words, you need not have read anything other than what I wrote above in the mapping description. No where do I say that each TM entry is a single candidate. In fact, I cannot fathom why one would ever even think in such a fashion.

Denis B wrote:

Notice that the principles of this mapping entail lots of specific properties of the TM, not implied by their general definition, e.g., in addition to those already mentioned: there's no empty cell in the diagonal and sub-diagonal.

The default properties are rather clear: If the diagonal is empty (row i, column j+1), then there exists a TM. This is of course a natural result of the inductive nature of the proof. All the other cells are not required in the argument (we have an nxn TM already, why continue?)

[ronk]

Here is an example, in the full nrczt notation (all candidates displayed):
n7r7{c6 c1} – n7{r2c1 r1c3} – n7r9{c3 c7 c1#n7r7c1} – n7r8{c7 c6 c1#n7r7c1 c2#n7r7c1} – n8{r8c6 r9c4} – {n8 n3}r9c3 – n3{r9c5 r7c6} ==> r7c6 <> 5

For the many who can't read your nrczt notation, pencilmarks would have been nice.

[denis_berthier]

Denis, it is fairly clear that you have not read any examples whereas I use TM's. Unfortunately, if you had you would know that "grouping" of candidates within a Boolean is specifically addressed. Thus, it is clear that the mapping expressed by me above does work, and is a proof.
Your disproof ignores the fact that the mapping I show addresses your concerns.

I stated precisely what I proved and what I didn't.

I repeat what you called your "final definition of TMs", which you say "has never been in flux": http://www.sudoku.org.uk/SudokuThread.asp?fid=4&sid=9059&p1=3&p2=11

Tri-angular matrix definition:
nxn
Each row contains at least one truth
The top entry of each column is in conflict with each item below it.
For row i, items i+2 and greater are empty. This can be translated, in Booleans, as False.

In this "final definition", there's not the slightest indication of what the entry of a matrix cell is.
No one should be supposed to read the hundreds of mainly controversial posts on Eureka to know how to fill in the gaps of your vague "final definitions".
The least cooperative reading is "TMs are not even defined".
The most obvious and cooperative reading - which I did - is "an entry is a candidate".
You're now saying that it can be a group of candidates, thus contradicting the natural notion of a matrix as having one element per cell and widely generalising the obvious interpretation.


If we accept your unnatural interpretation with groups of candidates in each entry:
- the expressive possibilities of these extended matrices are so broad that your claim that TMs are a generalisation of nrczt-chains is no more meaningful than my claim that your TMs are a special case of my universal algorithm: for all n in increasing order, write all the sequences of 0s and 1s of length n;
- these TMs are still more abstract logical things and still farther away from any factual pattern on a real grid;
- this makes it clear why, having defined TMs, this didn't allow you to discover neither nrczt-chains nor even the most elementary special case of xyt;
- with such cheating with complexity matters, I've lost any interest in this discussion.

[denis_berthier]

Here is an example, in the full nrczt notation (all candidates displayed):
n7r7{c6 c1} – n7{r2c1 r1c3} – n7r9{c3 c7 c1#n7r7c1} – n7r8{c7 c6 c1#n7r7c1 c2#n7r7c1} – n8{r8c6 r9c4} – {n8 n3}r9c3 – n3{r9c5 r7c6} ==> r7c6 <> 5

For the many who can't read your nrczt notation, pencilmarks would have been nice.

Wouldn't a transcription into Eureka or NL notation be better than PMs? What is important in this example is only the cells appearing in the chain.
As I'm not very expert in any of these notations, may I ask you try to do it?

[Steve K]

Denis, I think perhaps you stretch the generalization of complexity a bit too far. The mapping I have provided above is accurate. That is enough to prove the case. The complexity for that mapping is no more/ no less than a t chain. Thus, any arguments about complexity regarding that specific mapping are not relevant.

In any event, I purposefullly made the original definition of TM's given by Andrei Zelevinsky (feel free to google his name) at http://sudoku.com.au/1V25-3-2006-sudoku.aspx more general. I have always indicated that he created the technique. Here is what he wrote on that date:

Here is another 'matrix elimination pattern' that I call Triangular. Again you need to produce a square matrix whose entries are some sets of candidates (maybe empty), such that the union of entries in each row is a strong set. Also the top nonempty entry in each column j = 2, 3, ... is in the row j-1, and this entry is in conflict ('weak link') with every other entry in the same column.
Then it is easy to prove that the union of entries
in the first column is a strong set.

At that time, a strong set at that site was understood to be a sis. A weak link was understood to be a weak inference.

This definition was quite specific enough for me. PM's were intoduced one week earlier at the same site.

Here is my complete definition from the location at Eureka referenced above:

Code: Select all

Tri-angular matrix definition:
nxn
Each row contains at least one truth
The top entry of each column is in conflict with each item below it.
For row i, items i+2 and greater are empty. This can be translated, in Booleans, as False.

The most general structure, therefor is:
 
A1   A2         
B1   B2   B3         
C1   C2   C3   C4         
etc               

Then, in the next post:
Darn it!
Editing time over. An ommision above:
The top entry of each column except the first column is in conflict with each item below it.


I suppose that Andrei left room for expansion of TM's into just Booleans within his definition.

Denis, if you have lost interest, that is good. I have long ago lost interest in the narrow interpretation that you affect upon TM's. I only responded to you here to correct your frequent misrepresentations of what I have written. However, you asked for a mapping of t chains into TMs. Such a mapping has been provided. To suggest that the resultant complexity is somehow greater with a TM limited in the same fashion as a t chain makes no logical sense. You also indicated that you could disprove the mapping, and you have not done so. In fact, you proved the mapping, as one need consider precisely the same information in precisely the same fashion.

[denis_berthier]

Denis, I think perhaps you stretch the generalization of complexity a bit too far. The mapping I have provided above is accurate. That is enough to prove the case. The complexity for that mapping is no more/ no less than a t chain. Thus, any arguments about complexity are not relevant.

You'd better not speak of what you don't know.
I'm not speaking of the complexity of your mapping but of TMs.
The computational complexity of your general TMs is far greater than the computational complexity of nrczt-chains.

In any event, I purposefullly made the original definition of TM's given by Andrei Zelevinsky [...] more general. I have always indicated that he created the technique. Here is what he wrote on that date

That's irrelevant. I worked with the definition you explicitely provided as "final" in the context of this discussion.

Denis, if you have lost interest, that is good. I have long ago lost interest in the narrow interpretation that you affect upon TM's. I only responded to you here to correct your frequent misrepresentations of what I have written.

Perfect. Even with my "narrow interpretation", I already thought TMs were overly general and useless in practice - but they are still more than I suspected.

[Steve K]

Denis, if they are as you describe- too general to use - then perhaps I have never used them. Guess I have been dreaming.

[Steve K]

Denis wrote

this makes it clear why, having defined TMs, this didn't allow you to discover neither nrczt-chains nor even the most elementary special case of xyt;

There was nothing to uncover/discover. I was using them. I just did not name them as you have. To suggest otherwise runs contrary to the evidence.

If you were speaking of computational complexity, that is of little relevance to the manual solver. The manual solver easily "chunks" that which a computer may only check according to its specific programming. Humans are not limited by such narrow programming.

[denis_berthier]

Denis wrote

this makes it clear why, having defined TMs, this didn't allow you to discover neither nrczt-chains nor even the most elementary special case of xyt;

There was nothing to uncover/discover. I was using them. I just did not name them as you have. To suggest otherwise runs contrary to the evidence.

So, that's a new instance of your bragging: you knew nrczt-chains even before they were defined. Can you give a reference? I mean a reference where the nrczt-pattern appears explicitly and not a reference where you a posteriori re-interpret your TM stuff as nrczt-chains???
Otherwise I can similarly claim that all your stuff is a mere special case of my Universal Algorithm.
All this is utterly stupid. Defining a new pattern is much more than naming it - although naming it is important, as it shows there is something we want to distinguish from the rest.
Once more, you're just trying to create a diversion so that you don't have to admit your approach didn't lead you to the well defined nrczt concept.

If you were speaking of computational complexity, that is of little relevance to the manual solver. The manual solver easily "chunks" that which a computer may only check according to its specific programming. Humans are not limited by such narrow programming.

As TMs are not at all player oriented, I wonder what the manual solver has to do here. Can you name anyone who solves puzzles using TMs?
And YOU mentioned candidate counting as the algorithm for finding TMs.
Anyway, human or machine, replacing an element by a subset in each entry of the matrix introduces an exponential number of possibilities that have to be checked.
That's why I've always avoided the strategy of defining the most general patterns.

[Steve K]

Denis B wrote:

Once more, you're just trying to create a diversion so that you don't have to admit your approach didn't lead you to the well defined nrczt concept

I have never said that my approach led me, or anyone, to the well-defined but narrower nrczt concept. Thus, there is nothing to admit.

The fact that a technique was not well publicized, nor well-used, is not relevant. I merely indicated that TM's existed, when they existed, and their logical equivalence, in restricted cases, to nrczt chains.

Regarding the counting technique: I have always indicated that I am not a big fan of using the technique. I mentioned it, from time to time, in hopes that someone will find a better way to humanly utilyze a similar approach. Matrix counting is not specific to TM's. However, it can be used. One can tailor the counting to specific matrix forms, and proceed with as restricted or as general a search as one wishes based upon both the matrix type(s) and tolerance of grouping.

The hpl in the Easter monster was uncovered using such a restricted form of counting, (a simple two dimensional per node count). This is not bragging, as the hpl is a symmetric PM which is therefor of minimal complexity. I was stunned to stumble upon such an easy elimination pattern in a famous and presumably oft analyzed puzzle.
The point here is that recognition of the matrix structure sometimes can uncover with relative ease that which both computer programs and other techniques may fail to uncover.

Finally, and I mean finally: we may best agree to have a vast difference of opinion regarding these issues. In the future, I shall modify my comments when I find a TM elimination that happens to parrellel a t chain as follows, unless you take exception:

Code: Select all

Here is an elimination. Here is the justification I found. This justification mirrors a t chain, but with the following exceptions (if any)

In the specific case which started this unfortunate discussion, I would mention something like: the chain is not strictly any type of t chain defined by Denis B. because it uses a "cell" derived from a uniqueness argument. Furthermore, it ignores the strict ordering of "cell" consideration.

Have a fine day!

[denis_berthier]

I have never said that my approach led me, or anyone, to the well-defined but narrower nrczt concept.

Glad to hear it. As you've done lots of interesting things, it would have been very painful for me to see you loosing any credit.

Regarding the counting technique: I have always indicated that I am not a big fan of using the technique. I mentioned it, from time to time, in hopes that someone will find a better way to humanly utilyze a similar approach. Matrix counting is not specific to TM's. However, it can be used. One can tailor the counting to specific matrix forms, and proceed with as restricted or as general a search as one wishes based upon both the matrix type(s) and tolerance of grouping.

You can say the same of my Universal Algorithm. One can tailor it to any specific purpose, such as finding the Odysseus in the output.

The hpl in the Easter monster was uncovered using such a restricted form of counting, (a simple two dimensional per node count). This is not bragging, as the hpl is a symmetric PM which is therefor of minimal complexity. I was stunned to stumble upon such an easy elimination pattern in a famous and presumably oft analyzed puzzle.

This is the worst example you could give. The visual form of Easter Monster is so specific that it can be used to prove the contrary of what you wanted.
If rows and columns had been permutted (in consistent ways), thus disrupting the obvious symmetries, you'd probably never have found this pattern. But the underlying matrix would have been the same. You can say the matrix transposition helped you prove that your eliminations were valid, but the matrix certainly didn't help you find the pattern.
Unless you've some implant in your brain ;)
This is not to lessen your merit in this beautiful discovery - for which I congratulated you as soon as you posted it in this thread.

This is the main difference between patterns and matrices: you can see patterns on the grid (it doesn't mean they're always easy to find); but you can never see a matrix on the grid: you have to extract information from the grid and copy it in some external matrix structure.

Finally, and I mean finally: we may best agree to have a vast difference of opinion regarding these issues. Have a fine day!

Hope that a few things are clearer now.
Have a nice day too.
For me, it's almost night.

[ronk]

For the many who can't read your nrczt notation, pencilmarks would have been nice.

Wouldn't a transcription into Eureka or NL notation be better than PMs?
[...]
As I'm not very expert in any of these notations, may I ask you try to do it?

I'm not familiar enough with nrczt notation to do that in this instance.

As I suggested, pencilmarks (PM) would be the most helpful. After all, isn't the PM the common basis for all the notations?

[Allan Barker]

Hi Denis,

n7r7{c6 c1} – n7{r2c1 r1c3} – n7r9{c3 c7 c1#n7r7c1} – n7r8{c7 c6 c1#n7r7c1 c2#n7r7c1} – n8{r8c6 r9c4} – {n8 n3}r9c3 – n3{r9c5 r7c6} ==> r7c6 <> 5

I notice that part of the chain (– n7{r2c1 r1c3}) is not related to the elimination and can be removed. The logic is now a rank 0 structure that contains 6 sets and 6 (weak)linksets. This would eliminate candidates in all linksets, except that the triplet formed by 7r9c3 now restricts eliminations to linksets in a rank 0 loop. I am not good at notaion so I will try a ttt type diagram:

Code: Select all

 
                    (3)r9c3---r9c3=r7c6    }
                        ||           |     } Rank 0 Loop
                        ||           |     }
    (7)r9c7====r9c1====r9c3---r7c6=r7c1    }
         |         \  / ||
         |          \/  ||
    (7)r8c7=r8c6=r8c12  ||
              |         ||     
         (8)r8c6=r9c4--r9c3


However, this remaining piece would also be an nrczt chain, correct? and should still produce the elimination?

[denis_berthier]

Hi Denis,
I notice that part of the chain (– n7{r2c1 r1c3}) is not related to the elimination and can be removed.
However, this remaining piece would also be an nrczt chain, correct? and should still produce the elimination?

Hi Allan,
You're right that part of the chain, as I gave it, can be deleted and this still allows the elimination. And it still provides a counter-example.

However, SudoRules would never produce an elimination that it could justify with a shorter chain. So I must have made an error in writing the additional candidates (Remember SudoRules doesn't output them and I have to re-build all the chains manually when I want to display these candidates).
After checking again, the real full chain is (I had forgotten 2 additional candidates at the end of the chain - that wasn't relevant for the example):

nrct7-chain n7r7{c6 c1} – n7{r2c1 r1c3} – n7r9{c3 c7 c1#n7r7c1} – n7r8{c7 c6 c1#n7r7c1 c3#n7r7c1} – n8{r8c6 r9c4} – {n8 n3 n7#n7r1c3}r9c3 – n3{r9c5 r7c6 r8c6#n7r8c6} ==> r7c6 ≠ 5



This is a complex example. Let me take this opportunity to add that there are also much shorter counter-examples to the embedding of nrczt-chains into TMs with candidates as entries: e.g. any nrczt-chain whose first cell has an additional z-candidate (here n1r1c2):

n1r1{c1 c5 c2*} - ...

where the target is e.g. n1r3c3

In my mapping, the first cell of the second row of the TM should contain both n1r1c1 (the first left-linking candidate) and n1r1c2 (the z-candidate).

[Steve K]

Denis, I understand that you can provide numerous counter examples to your mapping. Do you have one for my mapping of nrctz into TM written above?

Code: Select all

A chain of n "cells" maps into an nxn TM.
"cell" m maps into TM row m.
Right-most "cell" content for all "cells" except "cell" n maps into TM row m, column m+1.
"Cell" content that "sees" the target are placed in TM column 1.
"Cell" content for row j (j>m)that is "linked" to right-most "cell" content for "cell" m is placed in TM column m+1.
TM entries which have not been filled are left empty.

I have placed each sentence on a new line, for clarity. Admittedly, I should have used symbols more judiciously. However, I think each line is clear by itself in directing the mapping.

It is common practice in mathematics, unless I am mistaken, that if something is not explicity forbidden, then it is acceptable. Thus, I cannot see how your mapping and mine are equivalent. Did you intend your mapping to be equivalent to mine?

IMO, all counter examples to your mapping employ the use of a candidate box/row or a candidate box/column intersection. Is this correct?