The concept of a RESOLUTION RULE and its applications

Advanced methods and approaches for solving Sudoku puzzles

Postby denis_berthier » Wed Aug 20, 2008 3:53 am

Steve K wrote: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.

As I indicated at the end of my post, I have no counter-example if you put subsets in the matrix cells - and, as I already stated also, I'm not interested in so overly general structures.
Putting the sentences in separate lines doesn't make it clearer that cell contents are subsets.

Whichever way you try to write it, whichever way you change my vocabulary of left-linking, right-linking, z- and t- candidates, you need the explicit definition of an nrczt-chain before you can define your mapping and the corresponding subset of TMs.

If this can make you happy, it is likely that your extended TMs are more general than nrczt-chains - but that's completely besides the initial point, because more general doesn't mean you knew the interesting special case of nrczt-chains before it was defined. Otherwise, I can say that with my Universal Algorithm, I know everything that has or will ever be written.


Steve K wrote:It is common practice in mathematics, unless I am mistaken, that if something is not explicity forbidden, then it is acceptable.

I guess you don't have much practice of maths, so you shouldn't speak of common practice. In maths, you give a definition and you respect 100% of it, no more no less - you don't have to add or delete conditions.
In your "definition", Paris monuments are not explicitly forbidden in the cells. Should they be allowed?


Steve K wrote:Thus, I cannot see how your mapping and mine are equivalent. Did you intend your mapping to be equivalent to mine?

I devised my mapping before you wrote yours, when I still thought a cell entry was a candidate, and when I published it later I suggested that "they are more or less equivalent" (if cells are candidates and not subsets); I said "more or less" because rows are displaced by 1. If the entries are subsets, they are obviously not equivalent.

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

Obviously yes. Notice that this restriction on the types of subsets that can be used as entries was not stated in your extended definition of TMs. So that this is one more constraint you have to put on them in order to get them closer to nrczt-chains.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Wed Aug 20, 2008 4:27 am

This is for both Steve and Allan

As generealised TMs (with entries subsets of candidates) are closer to second order than first order structures (which nrczt-chains are fundamentally), does any of you two see any relationship with them and Allan's well defined second order rules?
It seems TMs are less general but that's not fully clear.

One thing that I don't like in TMs, and that may make my question meaningless, is that columns have no special meaning: they are neither sets nor linksets (in Allan's vocabulary).
But splitting the columns of the TMs into 4 directions (numbers, rows, columns and blocks) can't one translate any TM into an Allan structure (I don't know how to call it)?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby Allan Barker » Wed Aug 20, 2008 2:12 pm

Hi all,

I assume that informal matrix like diagrams go back to the beginning of fish, whether for sets, constraints, implications, etc. I've used them to visualize sets and linksets but only, really began to see the possibilities after reading Steve's pages on TMs, PMs, etc.

It had been my subliminal belief that at some level sets and matrices were two views of the same thing. I don't have anything formal however my software does display set/linkset matrices along with logic, so there is some definition there.

I had considered Denis's idea of adding a dimension to resolve r,c,n, and b but decided it didn't add anything logically so I just throw extra nodes into the same matrix square, although I agree, even a scale model of the Eiffel tower would hardly fit.

Below is the output from the abbreviated form of Denis's original example (that I posted above). Each row is a set and each column is a linkset. In most cases, the identity of a node does not matter so I print an 'o' for a unique node. If 2 nodes occur in the same square (because of a box/line link), there are 2 'o's in that square. However, if two linksets link to one set, then I use letters of the alphabet because identity does matter. I do the same for 2 sets and a linkset.

Code: Select all

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

Matrix:

    n76 7b7 9b7 n86 9r8 9r3
7R7  o   o                 
9R7      Ao  o   
8R7      oo  o   o   
8B8              o   o     
N93      A           o   o 
8B3  o                   o 

o = any unique node, appears once
A = node that appears twice.

n86 is the set of all digits in cell r8c6

Two vertical As make a 'set triplet' and two horizontal As make a 'linkset triplet'. I am not concerned initially whether the matrix is symmetric nxn or asymmetric mxn. Of course, if I can reduce it somehow to nxn then I know I have a rank 0 structure. Note that column 1 has no special definition, if the logic is a chain then the matrix will be 6x7, with a rank of 1, where 2 linksets would overlap (in the puzzle) to eliminate a candidate (not shown in the matrix). (this would be similar to the left colum of a TM that combins those nodes that see the target). The matrix is used mainly as an electronic scratch pad and is not part of any method or software algorithm. It has no predefined target.

It seems that Denis's nrctz chain, when plotted in this general format, fits with the definition of a TM, whereas many of my matrices would probably not be TMs. In other words, this matrix looks like it would pass the rules for a TM, and the first column is also a strong inference set.

Here is another example which is a bit smaller with 4 sets and 6 linksets. It is a rank 2 kraken like single digit pattern. My 'general' matrix is shown below, I would be interested to see, is this also a TM and/or an nrctz chain? I don't know as I'm still learning TMs, nrctz-Cs, etc.

Code: Select all
-------------------------------------------------------
| 1    478  3458  | 3567 389  5678  | 3489 369  2     |
| 238  9    378   | 4    16   27    | 138  5    368   |
| 3458 248  6     | 1235 389  1258  | 7    139  3489  |
-------------------------------------------------------
| 2468 5    1478  | 9    126  3     | 128  167  678   |
| 389  126  389   | 126  7    4     | 3589 126  3589  |
| 2369 1267 1379  | 8    5    126   | 239  4   3-679  |
-------------------------------------------------------
| 7    148  4589  | 1235 348  1258  | 6    239  3459  |
| 456  3    145   | 1267 126  9     | 245  8    457   |
| 4589 468  2     | 3567 348  5678  | 3459 379  1     |
-------------------------------------------------------


                  +--6b5r4------6r2c5=6r2c9
                  |    ||               |
                  |    ||   +--->  X  <-+     X= r6c9<>6
                  |    ||   |
                  |  6b5r6--+--6r5c2=6r6c2=6r8c2
                  |    ||               |    |
                  |  6b5r5--------------+    |
                  |     |                    | 
                6r8c5=6r8c4=6r8c1------------+ 


    9c6 5c6 6r6 5r6 4c6 7b6
2R6  o   o   
5B6      o   o   A   A     
8R6          o       o   o 
2C6      o       o       o 

o = any unique node, appears once
A = node that appears twice.


In case of any problem with my diagrams, I attached pictures that will show the links, although you might need to read the rc coordinate from the shadows below.

ImageImage
Last edited by Allan Barker on Wed Aug 20, 2008 5:50 pm, edited 1 time in total.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby Steve K » Wed Aug 20, 2008 9:27 pm

Allan, by example first I suppose:
First glance, I see on candidate 6 an almost finned x wing r24 and an almost almost x wing c26 that are doubly linked.
One can easily write a TM using (6): r24, c26.
Similarly, one can use the SIS(6): r24, b9, c6
One can use the SIS(6): r2, c26, b5.
Finally, Allan uses SIS (6) r28, b5, c2. All can be expressed as a TM. Allan's is:
Code: Select all
r2  c9      c5   
b5  r6c6    r4c5  r5c4
r8          c5    c4    c1
c2  r6            r5    r1

All should express easily as zt type chains.

Denis and Allan: The temporary counting of excess columns versus rows available in the MBM, with rows limited to native SIS (plus uniqueness SIS), seems to be largely similar to linkset counts. I think one could finish the analogy, if one wished to do so.
TMs, with rows lmited to native SIS (plus uniqueness SIS) will not cover, imo, Allan's ideas. Certainly, one will need to add at least PMatrices.
Steve K
 
Posts: 98
Joined: 18 January 2007

Postby denis_berthier » Thu Aug 21, 2008 2:36 am

It is ironic that, while we had this discussion about whether TMs are a generalisation of nrczt-chains, I introduced grouped-nrczt-chains (which can also be seen a posteriori as a subset of Steve's generalised version of TMs) - at the bottom of this page: http://forum.enjoysudoku.com/viewtopic.php?t=5591&start=120 - but never did Steve mention before the possibility of such a natural generalisation of nrczt-chains.
This reminds me of the time when I introduced xy(z)t-chains (May 2007 in the first edition of my book, "The Hidden Logic of Sudoku", and 15 June 2007 on Eureka, "xyt-chains" thread). Steve already claimed that they were an obvious subset of his TMs. But didn't have the idea of introducing their "obvious" 3D generalisation (the nrczt-chains). The same can be said about lassos which I introduced after the nrczt-chains.

This is only to show that:
- having defined an overly general structure doesn't seem to be of much help for defining interesting special cases; one problem with TMs or PMs is they can represent lots of things which are not even chains in my strict sense and they can therefore hardly lead to finding anything precise; TMs or PMs have been used by Steve to re-prove chain rules that were easily proven without them; AFAIK, they've never been used to devise new chain rules;
- all the chain rules I've introduced were defined by generalising the xy-chain rule and analysing the way it can be proven - i.e. by studying the internal logic of the rule; history thus seems to show that diversions into other representations are of little help in this process. The same kind of progressive generalisation from previous patterns can also be observed in the history of NLs/AICs or in the Aquarium.

Although it is also very general (I think it covers all TMs and PMs, but this remains to be proven), I consider Allan's second order approach in a very different perspective: it has a sound mathematical grounding and it has been proven to generalise almost all the known rules (which is not the case of TMs or PMs). Indeed, I consider it as the second order counterpart of my first order framework and my notion of a resolution rule. The challenge Allan is now confronted to is, will this framework lead to generalisations of known rules or to specific new rules?
Last edited by denis_berthier on Fri Aug 22, 2008 8:09 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Thu Aug 21, 2008 2:38 am

Allan Barker wrote:Here is another example which is a bit smaller with 4 sets and 6 linksets. It is a rank 2 kraken like single digit pattern. My 'general' matrix is shown below, I would be interested to see, is this also a TM and/or an nrctz chain? I don't know as I'm still learning TMs, nrctz-Cs, etc.

Code: Select all
-------------------------------------------------------
| 1    478  3458  | 3567 389  5678  | 3489 369  2     |
| 238  9    378   | 4    16   27    | 138  5    368   |
| 3458 248  6     | 1235 389  1258  | 7    139  3489  |
-------------------------------------------------------
| 2468 5    1478  | 9    126  3     | 128  167  678   |
| 389  126  389   | 126  7    4     | 3589 126  3589  |
| 2369 1267 1379  | 8    5    126   | 239  4   3-679  |
-------------------------------------------------------
| 7    148  4589  | 1235 348  1258  | 6    239  3459  |
| 456  3    145   | 1267 126  9     | 245  8    457   |
| 4589 468  2     | 3567 348  5678  | 3459 379  1     |
-------------------------------------------------------


                  +--6b5r4------6r2c5=6r2c9
                  |    ||               |
                  |    ||   +--->  X  <-+     X= r6c9<>6
                  |    ||   |
                  |  6b5r6--+--6r5c2=6r6c2=6r8c2
                  |    ||               |    |
                  |  6b5r5--------------+    |
                  |     |                    | 
                6r8c5=6r8c4=6r8c1------------+ 


    9c6 5c6 6r6 5r6 4c6 7b6
2R6  o   o   
5B6      o   o   A   A     
8R6          o       o   o 
2C6      o       o       o 

o = any unique node, appears once
A = node that appears twice.



The underlying puzzle is
1.......2
.9.4...5.
..6...7..
.5.9.3...
....74...
...85..4.
7.....6..
.3...9.8.
..2.....1
SER = 11.3


Starting with the above PM, the first chain I get gives the same elimination as your pattern:
nrczt4-lr-lasso n6{r2c9 r1c8} - n6{r1 r9 r6*}c6 - n6{r8 r5 r1#n6r1c8 r9#n6r9c6}c4 - n6{r5 r9 r6#n6r1c8}c2 ==> r6c9 <> 6
but I can't see whether it corresponds to your pattern, although both are wholy based on digit 6.
(Notice that this is an nrczt-lr-lasso: the last right-linking candidate n6r9c2 is not nrc-linked to the target n6r9c6 but to a previous right-linking candidate n6r9c6.)
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Sat Aug 23, 2008 12:15 am


A mild example of an nrczt-net

(nrczt-nets were defined on p.7 of this thread)

Consider the following puzzle, copied from http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=934
(I've already mentioned this French forum, with puzzles provided by papyg and JPF, and several manual players using the nrczt-chains to solve them).

Code: Select all
+-------+-------+-------+
| . . . | 1 2 . | . . 3 |
| . . . | . . . | 4 . . |
| . . 5 | . . 6 | . . . |
+-------+-------+-------+
| . . . | . 7 . | . 2 1 |
| . 8 1 | . 4 . | 5 6 . |
| 2 5 . | . 8 . | . . . |
+-------+-------+-------+
| . . . | 8 . . | 3 . . |
| . . 6 | . . . | . . . |
| 4 . . | . 3 7 | . . . |
+-------+-------+-------+


The SER and NRCZT ratings are resp. 9.1 and 10. I've given the full SudoRules resolution path in the above mentioned sudoku-factory thread and you can check it there. From the nrczt-chain viewpoint it brings nothing new.
What I want to show here, only for illustrative purposes of the nrczt-nets, is an alternative solution found by Caravail. It is still based on the nrczt approach, but with a very special kind of nrczt-net.

After some eliminations, Caravail gets the following PM:

Code: Select all
  |   c1       c2       c3    |   c4       c5       c6    |   c7       c8       c9    |
--|---------------------------|---------------------------|---------------------------|
r1|789      679      4789     |1        2        48       |679      5        3        |
r2|1689     1269     238      |7        5        38       |4        189      2689     |
r3|1378     12347    5        |34       9        6        |127      178      278      |
--|---------------------------|---------------------------|---------------------------|
r4|36       346      34       |59       7        59       |8        2        1        |
r5|79       8        1        |23       4        23       |5        6        79       |
r6|2        5        79       |6        8        1        |79       3        4        |
--|---------------------------|---------------------------|---------------------------|
r7|1579     1279     279      |8        6        2459     |3        149      2579     |
r8|3589     2379     6        |2459     1        2459     |279      4789     25789    |
r9|4        129      289      |259      3        7        |1269     189      25689    |
--|---------------------------|---------------------------|---------------------------|

and proposes the following nrczt-net.
I transcript it in my notation, using a and b indices to indicate the two branches (these are only visual aids):
Notice that there can be no ambiguity in cell 6; as any cell has only one left-linking candidate, it has two right-linking: n7a n9b

Code: Select all
{n9 n5}r4c4 - n5r9{c4 c9} - n6r9{c9 c7} - n1{r9 r3}c7 - n2{r3 r8 r9#n6r9c7}c7 - {n2 n7a n9b n5#n5r9c9}r7c9 -
      a- n7{r5c9 r6c7} - {n7 n9}r6c3 - {n9 n2 n7#n7r7c9}r7c3 -a
      b- n9{r5c9 r6c7} - {n9 n7}r6c3 - {n7 n2 n7#n9r7c9}r7c3 -b
                  ab- n2{r7c6 r9c4 r8c4#n2r8c7 r8c6#n2r8c7} => r9c4<>9



As in any partial nrczt-chain, left- [resp. right-] linking candidates have a negative [resp. positive] valence (partial nrczt-chains theorem), in the context of the chain. This works upto cell #6.
In the 6th cell, one can see two right-linking candidates n7a and n9b instead of only one. Positive valence for the right-linking candidates here means that one (and of course only one) of these two candidates must be true in the context of this chain.
Each of these candidates gives rise to a 3D chain which appears to be a fragment of an nrct-chain (these 2 chains, a and b, are here based on the same rc-cells):
a- n7{r5c9 r6c7} - {n7 n9}r6c3 - {n9 n2 n7#n7r7c9}r7c3 -a
b- n9{r5c9 r6c7} - {n9 n7}r6c3 - {n7 n2 n7#n9r7c9}r7c3 -b
and which ends with a positive valence for n2r7c3
Both chains converge on left-linking candidate n2r7c6, in conformance with the general definition of an nrczt-net.

This example also illustrates why in my definition of nrczt-nets I introduced the concept of oriented 2D-cells. If I had defined the structure based merely on candidates instead of oriented 2D-cells, the convergence of the two branches would occur incorrectly on n2r7c3 instead of the left-linking n2r7c6.

As this puzzle has a solution using only nrczt-chains, such nets are not necessary here. But Caravail thus provides a good illustration of a mild kind of nrczt-nets (although slightly less mild than the grouped-nrczt-chains defined in the "fully supersymmetric chains" thread, p.9).

There may be an alternative way of understanding this pattern, as a combination of partial nrczt-chains and of remote pairs, but that's another matter.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby ttt » Sat Aug 23, 2008 12:31 pm

Hi Denis,
For above puzzle from French Forum (I can’t read & speak French…:D ), I found a path to eliminate r1c7=7 based on cell r2c3, but I drawn it as diagram too ugly… (sorry, I have to present my way by Eureka notation...)

Code: Select all
   -----------------------------------(8)r1c1
  /                                    ||
(8-3)r2c3=(3-4)r4c3=(4-6)r4c2=(6)r4c1-(6)r1c1
 ||                                    ||
 ||                                 (hp79)r15c1-(7)r378c1=(7’s:r1c1=r5c1-r6c3=r6c7)   
 ||                                    ||                               
(2-3)r2c3=(3-4)r4c3=(4-6)r4c2=(6)r4c1-(6)r1c1
 || \                                  ||
 ||  -------(3)r2c3=(3-8)r2c6=(8)r1c6-(8)r1c1                  -------(7)r7c8
 ||                                                           /        ||
(3)r2c3--(3=8)r2c6-(8=4)r1c6-(4)r78c6=(4)r8c4-(4)r8c8=(4)r7c8-(1)r7c8  ||
       |                                                       ||      ||
        ----------------------------(2)r2c3                    ||      ||
       |                             ||                        ||      ||
        -(3=4)r4c3-(4)r4c2=(4)r3c2--(2)r3c2                    ||      ||
                                  |  ||                        ||      || 
                                  | (2)r2c2--(1)r2c2           ||      ||
                                  |           ||               ||      ||
                                   ----------(1)r3c2           ||      ||           
                                  |           ||               ||      ||
                                  |          (1)r23c1---------(1)r7c1  ||
                                  |                            ||      ||
                                  |                           (1)r7c2-(7)r7c2 
                                  |                                    ||
                                   -----------------------------------(7)r3c2
                                                                       ||
                                                         (7’s: r1c2=r8c2-r8c8=r3c8)


=> r1c7<>7

My way meant:
- If r2c3=2 or 8 => pair 79 at r15c1 => r378c1<>7=> coloring 7’s: r1c1=r5c1-r6c3=r6c7=> r1c7<>7
- If r2c3=3 => r3c2=4, r7c2=1 & r7c8=4 => coloring 7’s: r1c2=r8c2-r8c8=r3c8 => r1c7<>7
Please correct me if something’s wrong… Thanks!
ttt
ttt
 
Posts: 185
Joined: 20 October 2006
Location: vietnam

Postby denis_berthier » Sat Aug 23, 2008 1:21 pm

ttt wrote:For above puzzle from French Forum (I can’t read & speak French…:D ), I found a path to eliminate r1c7=7 based on cell r2c3,

Hi ttt,
Are you starting from the PM I gave with the puzzle?
I'm not sure about what you're asking. Are you suggesting that this could be an nrczt-net built on candidate n7r1c7? But then how is this candidate linked to other candidates in the pattern?


ttt wrote:My way meant:
- If r2c3=2 or 8 => pair 79 at r15c1 => r378c1<>7=> coloring 7’s: r1c1=r5c1-r6c3=r6c7=> r1c7<>7
- If r2c3=3 => r3c2=4, r7c2=1 & r7c8=4 => coloring 7’s: r1c2=r8c2-r8c8=r3c8 => r1c7<>7

From these lines and the fact that (apart from the first column) your diagram is split into two independent pieces (r2c3=2 or 8, r2c3 = 3), I wonder if you are not doing some T&E. Things would be clearer if you could put the target somewhere on the diagram and show its links with all the relevant candidates.

From the general structure of the diagram, I think it should be much more familiar to Allan than to me.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby ttt » Sat Aug 23, 2008 2:18 pm

Hi Denis,
I edited my diagram and my path start from as below.

Code: Select all
*--------------------------------------------------------------------*
 | 6789   679    4789   | 1      2      48     | 679    5      3      |
 | 1689   1269   238    | 7      5      38     | 4      189    2689   |
 | 1378   12347  5      | 34     9      6      | 127    178    278    |
 |----------------------+----------------------+----------------------|
 | 369    3469   34     | 59     7      359    | 8      2      1      |
 | 379    8      1      | 239    4      239    | 5      6      79     |
 | 2      5      79     | 6      8      1      | 79     3      4      |
 |----------------------+----------------------+----------------------|
 | 1579   1279   279    | 8      6      2459   | 3      1479   2579   |
 | 35789  2379   6      | 2459   1      2459   | 279    4789   25789  |
 | 4      129    289    | 259    3      7      | 1269   189    25689  |
 *--------------------------------------------------------------------*


   -----------------------------------(8)r1c1
  /                                    ||
(8-3)r2c3=(3-4)r4c3=(4-6)r4c2=(6)r4c1-(6)r1c1
 ||         |                          ||
 ||          ---------------(3)r5c1=(hp79)r15c1-(7)r378c1=(7’s:r1c1=r5c1-r6c3=r6c7)   
 ||         |                          ||                               
(2-3)r2c3=(3-4)r4c3=(4-6)r4c2=(6)r4c1-(6)r1c1
 || \                                  ||
 ||  -------(3)r2c3=(3-8)r2c6=(8)r1c6-(8)r1c1                  -------(7)r7c8
 ||                                                           /        ||
(3)r2c3--(3=8)r2c6-(8=4)r1c6-(4)r78c6=(4)r8c4-(4)r8c8=(4)r7c8-(1)r7c8  ||
       |                                                       ||      ||
        ----------------------------(2)r2c3                    ||      ||
       |                             ||                        ||      ||
        -(3=4)r4c3-(4)r4c2=(4)r3c2--(2)r3c2                    ||      ||
                                  |  ||                        ||      || 
                                  | (2)r2c2--(1)r2c2           ||      ||
                                  |           ||               ||      ||
                                   ----------(1)r3c2           ||      ||           
                                  |           ||               ||      ||
                                  |          (1)r23c1---------(1)r7c1  ||
                                  |                            ||      ||
                                  |                           (1)r7c2-(7)r7c2 
                                  |                                    ||
                                   -----------------------------------(7)r3c2
                                                                       ||
                                                         (7’s: r1c2=r8c2-r8c8=r3c8)

I only solved this puzzle, nothing for asking… (sorry, if it’s not right here). As knowledge on my level now (English & Sudoku:D ), I think that yours nrczt-chains, Steve’s matrixes or my diagram above as ways to present deductions. I don’t know how can find Steve’s matrixes… for me find X-wing or above deduction is the same way, I have to scan all candidates…

Thanks
ttt
ttt
 
Posts: 185
Joined: 20 October 2006
Location: vietnam

Postby denis_berthier » Sun Aug 24, 2008 2:35 am

Hi ttt
Your PM shows you are attacking the puzzle from an earlier point than the one I was mentioning.
ttt wrote:I think that yours nrczt-chains, Steve’s matrixes or my diagram above as ways to present deductions. I don’t know how can find Steve’s matrixes…

I don't know enough about your diagrams to have any opinion about them (except that they look very complex and they vaguely evoke for me Allan's well grounded approach). I think you should open a thread to explain them in more detail. That's guaranteed to be more interesting than some existing threads. I'd also like to have Allan's opinion on them.
I agree that Steve's matrices are a way to present deductions (and I add only a way to that effect).
nrczt-chains are different: they define precise patterns one has to look for on a grid. In this respect, they are exactly like pairs or fish. Both are resolution rules: they are defined at the "factual level", not at the "inference level".


ttt wrote:for me find X-wing or above deduction is the same way, I have to scan all candidates…

The difference is that X-wing is a pre-defined pattern whereas your example is dynamically created during your search. That's also the reason for my question about T&E.
(Incidentally, for X-wing or any fish, there's a way to find it without any search: use my extended Sudoku board, where it will appear as a naked set).
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby Allan Barker » Sun Aug 24, 2008 10:58 pm

Human solutions, ttt diagrams, etc..

Steve and ttt are human solvers both of who are pushing the limits of what human's can solve. ttt has not revealed his "thinking secrets" but Steve seems happy to use just about anything including TMs and PMs, which are easily scratched on paper. I only recently saw his full human solution to EM, which will push me to unveil, yes, GN!

Nrctz chains, etc. are a set of precisely defined rules for building logic based on a progressive, chain like algorithm where pattern = precise algorithm. They are very powerful Sudoku methods.

Set logic, expressed as rules or as matrices, is a logical framework that can be used as a tool to help solve or analyze logic e.g., they may "explain" why nrctz chains work the way they do. I have been writing something along these lines, which I'll try to finish so we can debate.

As for ttt's or any human solutions, they are interesting to analyze and compare to other things like nrctz chains and even my "natural logic". When I say natural logic, I mean output from my solver, which is not restricted to any logical form, even cover sets and strong/weak links. These are all "outputs" of the solver process.

In comparing, the human would say "here is what I did". The nrctz system would say this is what a precisely defined method would do and the natural logic would say this is what's possible.

As for ttt's diagrams, I think they are great and we need something better than chain based notation if human and method solutions continue to evolve and go after the monsters. I don't know the answer but one thing about diagrams is that they are basically dimensionless, just like logic.

In passing, let me congratulate you on the release of your grouped nrctz chains, as I await mutant super-antisymetric nrctzpsn-mace. As Occam's nemesis the devil said with a smile, "Welcome to complexity...."
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby denis_berthier » Mon Aug 25, 2008 2:18 am

Allan Barker wrote:Nrctz chains, etc. are a set of precisely defined rules for building logic based on a progressive, chain like algorithm where pattern = precise algorithm. They are very powerful Sudoku methods.
Set logic, expressed as rules or as matrices, is a logical framework that can be used as a tool to help solve or analyze logic e.g., they may "explain" why nrctz chains work the way they do.

Your set logic shouldn't be compared wit nrczt-chains but with the general concept of a resolution rule - of which nrczt-chains are just an example.
Resolution rules are a first order logical framework, your set logic is a more general second order logical framework.
nrczt-chains are fully explained in the resolution rule framework - and, as a result, they can also be re-explained in your more general framework, at the cost of losing their linear structure.
I can't agree with your assimilation of a pattern and an algorithm. As a mathematician, you should know better. A pattern is a logical, not an algorithmic, notion. Given the nrczt pattern or any other, e.g. triplets, there may be lots of very different algorithms to find them. This is one of the main themes of this thread.

Allan Barker wrote:As for ttt's or any human solutions, they are interesting to analyze and compare to other things like nrctz chains and even my "natural logic". When I say natural logic, I mean output from my solver, which is not restricted to any logical form, even cover sets and strong/weak links. These are all "outputs" of the solver process.

Defining "natural" as "output of a specific computer process" is very unnatural.

Allan Barker wrote:In comparing, the human would say "here is what I did". The nrctz system would say this is what a precisely defined method would do and the natural logic would say this is what's possible.

Again, you are restricting resolution rules to nrczt-chains and your comparison thus loses much relevance:
- resolution rules say what's possible using first order logic,
- your set logic says what's possible using second order logic.

Allan Barker wrote:As for ttt's diagrams, I think they are great and we need something better than chain based notation if human and method solutions continue to evolve and go after the monsters. I don't know the answer but one thing about diagrams is that they are basically dimensionless, just like logic.

I don't understand what "dimensionless" means here. What's not "dimensionless" in a chain pattern???
BTW, you didn't answer the precise question about ttt's diagram: do you think it can be given a formal interpretation as one of your structures?

Allan Barker wrote:In passing, let me congratulate you on the release of your grouped nrctz chains, as I await mutant super-antisymetric nrctzpsn-mace. As Occam's nemesis the devil said with a smile, "Welcome to complexity...."

The world of complexity is not so manichean.
From basic xy-chains to nrczt-chains, there is a progressive increase in complexity - on an as yet mostly undefined scale of complexity, but in any intuitive sense of this word. Grouped-nrczt-chains define a new higher grade. As for "mazes", I've already sort of defined them: nrczt-nets - but I've always said they were not for human players in their most general form.
My approach is opposed to yours on the following point: as I'm very concerned with complexity, I'm generalising my rules progressively, after analysing carefully what my current set of rules can't solve. There are so few puzzles that it can't solve that I consider it worth not jumping to overly general rules. I'd say my approach is bottom-up in a general first order framework, whereas yours is top-down in a general second order framework.
My problem is finding the interesting generalisations, yours is finding the reasonably complex specialisations.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby Allan Barker » Mon Aug 25, 2008 11:14 pm

BTW, you didn't answer the precise question about ttt's diagram: do you think it can be given a formal interpretation as one of your structures?


Sorry, I guess my comment was more of a rambling answer to where ttt's (and other human solutions) fit in the scheme of things. In a single sentence, I would summarize, "Although the various approaches to Sudoku may differ, they all benefit by comparison to human solutions in various ways". Although I included nrctz chains as symbolic of one approach, the comparison is mainly human solutions to Sudoku methods.

I should have considered that comments are framed by a thread's subject and your clarifications are correct. I'm not qualified on my own to compare the methodology of resolution rules to other methods, however I have always enjoyed discussions along the line, from which I do most of the learning. And yes, algorithm is the wrong word, a pattern is defined by a rule, an algorithm is an implementation of a rule, and that's a main point of the thread. I was thinking of the rule inside.

ttt's graph like drawings are dimensionless as opposed to 2D 'grid' diagrams, and even my 3D diagrams. I only suggest that NL and Eureka chain notation is not so good for complex interconnections, not that they are dimensioned any more than ttt's drawings (both of which use rcn to identify nodes).

To answer the original question, yes I think so, but to get one unified piece of logic, I first must perform a work around for the T&E. This raises a question that might also apply to resolution rules. Given a proof like ttt's where a series of assumptions are made on a cell, each leading to the same conclusion. Given also that the logic for each assumption overlaps the logic of the others but differs, i.e., some require strong links where others require weak links, etc. What happens when you simply combine the logic together? Could it lead to illegal combinations, or is there a guaranteed equivalent 'unified' logic?
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby denis_berthier » Tue Aug 26, 2008 12:45 am

Allan Barker wrote:
BTW, you didn't answer the precise question about ttt's diagram: do you think it can be given a formal interpretation as one of your structures?

yes I think so, but to get one unified piece of logic, I first must do a work around for the T&E. That raises a question, which might also apply to resolution rules. Given a proof like ttt's where a series of assumptions are made on a cell, each leading to the same conclusion. Given also that the logic for each assumption overlaps the logic of the others but differs, i.e., some require strong links where others require weak links, etc. What happens when you simply combine the logic together? Could it lead to illegal combinations, or is there a guaranteed equivalent 'unified' logic?

Difficult question, whose answer depends on what one accepts as condition patterns. The major formal conditions on resolution rules (and also, as far as I can see, on your rules) are that the "condition part" is a pattern and the "action part" has no disjunction. But there are also informal subjective conditions one is not ready to give up, such as "homogeneity" of the patterns (whichever meaning one gives to "homogeneous").

In terms of resolution rules, T&E is characterised by the fact that the elimination of a target z is the result of several tentative successive resolution rules based on assuming z globally (in an artificially created common scope), instead of a single rule integrating z locally (I mean in the scope of the rule itself) in its condition pattern.

One could then translate your question into:
"given a resolution path A1 -> B1,..., An -> Bn (where A1 has z in its conditions and Bn concludes on a contradiction), can one always define a resolution rule that somehow combines their conditions and concludes on the elimination of z?"
First obvious tentative answer: A1 & A2 & .... An -> Bn
(I'm aware all this should be written more carefully).
One problem is, the set of resolution rules we have to accept is then made of very inhomogeneous patterns of length potentially unlimited. Any combination of any number of any patterns has to be accepted as a potential condition for an elimination.

Suppose now one accepts only "homogeneous" patterns.
To take an example, assume basic interaction rules + basic subset rules + nrczt-chains and lassos, together with T&E limited to depth 1, can solve all the puzzles (I take this case because I have no counter example).
As basic interactions are subsumed by nrczt-chains one can forget them. As almost all, but not all, subset rules are subsumed by nrczt-chains, one can't forget them and nrczt-chains are not the good homogeneous structure for combinations.
As nrczt-nets (and, as of now, no known simpler strcuture) subsume basic interactions, basic subset rules and nrczt-chains, one has to accept nrczt-nets as the basic "homogeneous" building blocks for the above combinations. (I think nrczt-nets can indeed be combined that way and thus can solve any puzzle without T&E, but I never even tried to prove it. Notice that this wouldn't contradict my T&E theorem, because the nrczt-net RuleOfEverything wouldn't be a single rule but a set of rules.)
Conclusion: the notion of an "homogeneous" pattern one has to accept must include very complex patterns (that won't look so homogeneous from an intuitive POV).
(That's why I've always tried to define patterns of progressively increasing complexity instead of looking for a RuleOfEverything).

About your 3D-diagrams (and the logic behind them), I think you can also combine them. I don't think you will get illegal (in the sense of logically unsound) combinations, but you're likely to meet the same kind of more informal problems as above. Anyway, I'm eager to read the result of your work on this. I think it is at the heart of understanding ttt's patterns and providing a logical grounding for them.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to Advanced solving techniques