Fully supersymmetric chains

Advanced methods and approaches for solving Sudoku puzzles

NRCZT-BRAIDS

Postby denis_berthier » Fri Sep 26, 2008 1:04 am


NRCZT-BRAIDS


Just a little time after the nrczt-whips, which synthesise in a single chain pattern the nrczt-chains and nrczt-lassos, here is a generalisation of them, the nrczt-braids. I'll soon show that they have very interesting properties.

In a previous post, I've defined nrczt-nets by generalising nrczt- chains and lassos (or nrczt-whips, in my new perspective) with the possibility of having several right-linking candidates in the same rc-, rn-, cn- or bn- cell as a left-linking one. See near the bottom of this page: http://forum.enjoysudoku.com/viewtopic.php?t=5600&postdays=0&postorder=asc&start=90. These nets include grouped nrczt-chains, which are a relatively mild special case. But the most general nrczt-nets are very hard to use, because their structure is complex and the conditions of the associated elimination theorem are very hard to check.


In this post, I'll introduce nrczt-braids, a much milder kind of nets, with an easier elimination theorem.

Informally, given a target candidate z, an nrczt-braid built on z is, as an nrczt-whip, a linear sequence of candidates, alternatively called left-linking and right-linking. Its precise definition is obtained from that of an nrczt-whip by merely changing the condition "any left-linking candidate is nrc-linked to the previous right-linking one" by "any left-linking candidate is nrc-linked to a previous right-linking one or to the target".
As any nrczt-whip, an nrczt-braid can also be considered as a sequence of rc, rn, cn or bn cells.
And, still as any nrczt-whip, an nrczt-braid produces a contradiction on its target when its last cell has no right-linking candidate compatible the previous ones and with the target.
Now the formal definition.

Definition: an nrczt-braid of length n for a target z is a sequence of candidates L1, R1, L2, R2, .... Ln-1, Rn-1, Ln, alternatively called left-linking and right-linking, such that:
- for any 1<= k <= n, Lk is nrc-linked to the target or to a previous right-linking candidate (some Ri, for i < k);
- for any 1 <= k < n, Lk and Rk are in some well defined rc, rn, cn or bn cell (which entails they are nrc-linked) such that each of the other candidates in this cell is nrc-linked to the target or to a previous right-linking candidate; Rk itself is not nrc-linked to any of these;
- in at least one of the four rc, rn, cn or bn cells containing Ln, each of the other candidates is nrc-linked to the target or to a previous right-linking candidate.



Notice that, as nrczt-whips, nrczt-braids still have one and only one right-linking candidate per cell but the last one, but they may have several left-linking candidates branching off the target or off any right-linking candidate - with the restrictive condition that the set of candidates must be totally ordered. Their branching structure is thus severely restricted.
There are therefore two complementary views of nrczt-braids: sequential (a sequence of candidates) or as a net with a restricted form of branching. Both of them are useful.
The following definitions are used:
- an additional z-candidate in a cell is defined as usual: it is nrc-linked to the target);
- an additional t-candidate in a cell is defined as usual: it is nrc-linked to a previous right-linking candidate (one could add: in the same branch OR in any other branch; but such a distinction is pointless as "previous" refers to the total ordering of the right-linking candidates induced by the total ordering of all the candidates);
- a terminal right-linking candidate is one which sprouts no left linking candidate.

Pruning useless parts of branches: we may add the condition that the any terminal right-linking candidate is nrc-linked to a t-candidate in a cell after his own (in the global ordering). Otherwise, its cell can merely be eliminated from the nrczt-braid, thus leaving a smaller one with the same target. Doing this as many times as necessary, we can reach an nrczt-braid with no useless cell; we'll call this a minimal nrczt-braid. Unless otherwise stated, all nrczt-braids will be minimal (but this is only for efficiency reasons).

Any branch of an nrczt-braid starting from the first llc and ending with the last llc is thus almost an nrczt-whip; it only has a few additional candidates (other than the usual t- or z-) in some of its cells, candidates which must be dealt with by considering additional branches.
Notice that this is nevertheless very different from accepting to take left-linking candidates among already deleted candidates: when we progressively build our nrczt-braid, we don't have to consider all the missing candidates anywhere in the grid as potential left-linking ones for the next cell. We can only consider those that are nrc-linked to an already chosen previous right-linking candidate. Said otherwise, this definition sticks to the idea that deleted candidates play no role in the rules.


It is then easy to prove that,

nrczt-braid elimination theorem: given an nrczt-braid, its target can be eliminated.

Proof: exactly the same as for nrczt-whips, following the total ordering of the candidates, until the last left-linking candidate, with no compatible right-linking one, is reached. The proof shows progressively that, if the target was true, then all the left-linking candidates would be false and all the right-linking candidates would be true.


Finally, it may be useful to give an elementary example of something which cannot be the beginning of any nrczt-braid (it is impossible to define any total ordering of the candidates, compatible with the above definition):

Code: Select all
    / {llc1 rlc1 t1#rlc2}
  /
z
   \
     \ {llc2 rlc2 t2#rlc1}

each of the 2 lines represents an rc, rn, cn or bn cell,
with t2 an additional candidate nrc-linked to rlc1 and t1 an additional candidate nrc-linked to rlc2.

From z true, there is no possibility of concluding that rlc1 is true or that rlc2 is true: one can only conclude (rlc1 & rlc2) or (t1 & t2)

This example is also an indication on how nrczt-braids could be generalised. But before generalising them, there's a lot more to say about them.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Fri Sep 26, 2008 2:01 am


SOLVABLE BY NRCZT-BRAIDS <=> SOLVABLE BY T&E(ECP+NS+HS)


This post gives a precise answer to the question: what is the solving potential of nrczt-braids?
Given any resolution theory, such a question is generally very hard to answer. E.g., if I considered only whips instead of braids, I'd have no answer.

First, I need non ambiguous definitions. And for this, you must remember my distinction between a resolution rule and a resolution technique (see here:http://forum.enjoysudoku.com/viewtopic.php?t=5600&start=0).

Definition: Given a resolution theory T and a candidate z, T&E(T, z) is the following resolution technique:
- start a new grid by copying the current PM; add z to this new grid as a decided value; apply to this new PM all the rules in T;
- if a contradiction is obtained in this new PM, then delete z from the original one; if no contradiction is obtained, then merely go back to the original PM.

I think this is what everyone means by "using T&E(T) to eliminate candidate z".

Definition: Given a resolution theory T, T&E(T) is the following resolution technique (this is only conceptual, any implementation would optimise this):
- a) define phase = 1;
- b) apply all the rules in T;
- c) set changed-PM = false; mark all the remaining candidates as "not tried";
- d) if there is at least one "not-tried" candidate, then choose any one of them, say z; apply T&E(z); if it eliminates z, then set changed-PM = true and apply all the rules in T, otherwise un-mark z; in both cases, goto d;
- e) if there is no not-tried candidate:
----------- if changed-PM = true, then set phase = phase +1 and goto c);
----------- if changed-PM = false, then stop.
Notice that the procedure allows considering the same candidate z several times. This is reasonable, because any elimination on another candidate z' by T&E(z') may entail a new possibility of a contradiction appearing in a new application of T&E(z).


Definition: a puzzle P is solvable by T&E(T) if the above procedure leads to a solution.


We'll be interested only in T= ECP+NS+HS (with ECP = the rules for the elementary constraints propagation).

Notation: T&E designates T&E(ECP+NS+HS)




THEOREM: ANY ELIMINATION THAT CAN BE DONE BY AN NRCZT-BRAID WITH TARGET Z CAN BE DONE BY T&E(ECP+NS+HS, z)
COROLLARY: ANY PUZZLE THAT CAN BE SOLVED WITH ONLY NRCZT-BRAIDS (+ of course ECP, NS and HS) CAN BE SOLVED BY T&E(ECP+NS+HS).


Proof: obvious.
What is interesting is that the converse is true:

THEOREM: ANY ELIMINATION THAT CAN BE DONE BY T&E(ECP+NS+HS, z) CAN BE DONE BY AN NRCZT-BRAID WITH TARGET z.
COROLLARY: ANY PUZZLE THAT CAN BE SOLVED BY T&E(ECP+NS+HS) CAN BE SOLVED BY NRCZT-BRAIDS.

Notice that puzzles that can't be solved by T&E(ECP+NS+HS) are extremely rare.


We shall show that any elimination done by T&E, at any step in the resolution process, could have been done by an nrczt-braid.

Consider the PM generated by the T&E hypothesis z=n0r0c0 and take n0r0c0 as the target of the nrczt-braid we're going to build.
In the auxiliary PM generated by the T&E hypothesis, the T&E procedure is a well defined sequence of deletions of candidates based on ECP and of assertions of values based on NS or HS, until a contradiction is reached (if one is reached).

1) Consider the first step of T&E that is not an elimination by ECP.

Suppose first that the assertion made by this step relies on NS: say r'c'=n'
If this assertion can be made, it can only be because:
- n'r'c' is not nrc-linked to n0r0c0 (otherwise it would have been eliminated by ECP);
- all the other candidates for cell r'c' have been eliminated by the assertion of n0r0c0, which supposes that they are nrc-linked to n0r0c0, because only ECP can produce eliminations.
Take any of the candidates in cell r'c', different from n'r'c', say n1r'c'.
Then {n1r'c' n'r'c'} is the first cell of our nrczt-braid (and all the other candidates in cell r'c' are z-candidates).

The same reasoning applies if this step is an assertion by HS(row): instead of considering the rc-cell r'c', we consider the rn-cell r'n'.
The same reasoning applies if this step is an assertion by HS(col): instead of considering the rc-cell r'c', we consider the cn-cell c'n'.
The same reasoning applies if this step is an assertion by HS(blk): instead of considering the rc-cell r'c', we consider the bn-cell b'n'.


2) The sequel is done by recursion. If we have been able to replace the T&E procedure upto the nth assertion step, then we can replace it by a longer nrczt-braid upto the (n+1)th assertion step. Name n'r'c' the nth candidate asserted.
Suppose first that the (n+1)th assertion made by T&E relies on NS: say r'c'=n'
If this assertion can be made, it can only be because:
- n'r'c' is not nrc-linked to n0r0c0 or to any of the previous candidates asserted in any of the previous steps, i.e. to any of the right-linking candidates of the partial nrczt-braid we've already built (otherwise it would have been eliminated by ECP);
- all the other candidates for cell r'c' have been eliminated by the assertions of n0r0c0 and of all the previously asserted candidates, which supposes that each of them is individually nrc-linked to the target or to some of the previous right-linking candidates;
- there is a candidate n1r'c' in cell r'c' which is nrc-linked to n0r0c0 OR to a previous right-linking candidate n2r2c2. Take {n1r'c' n'r'c'} as the next cell of our braid. NOTICE THAT IT WOULD BLOCK HERE IF WE CONSIDERED WHIPS INSTEAD OF BRAIDS.

The new cell of our nrczt-braid, {n1r'c' n'r'c'}, is appended to the right of n2r2c2 (all the other candidates in cell r'c' are z- or t- candidates wrt to already existing branches of the net).

The same reasoning applies if this step is an assertion by HS(row): instead of considering the rc-cell r'c', we consider the rn-cell r'n'.
The same reasoning applies if this step is an assertion by HS(col): instead of considering the rc-cell r'c', we consider the cn-cell c'n'.
The same reasoning applies if this step is an assertion by HS(blk): instead of considering the rc-cell r'c', we consider the bn-cell b'n'.


3) End: a contradiction is detected by T&E when a cell (rc-, rn-, cn- or bn-) has no candidate left. Suppose it is an rc-cell.
How can that happen? Only via an ECP step. But it means then that the last asserted value is nrc-linked to a previous right-linking candidate or to the target, i.e. we have an nrczt-braid.

q.e.d.


Remark: for the first time, we thus have a set of resolution rules (the set of nrczt-braid[n] rules, for any length n, together with ECP, NS and HS) which is equivalent to T&E.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Sat Sep 27, 2008 2:22 am



Theorem: T&E(NS+HS, n) = T&E(B-NRCZT, n-1)


Said otherwise, any puzzle that can be solved by ordinary T&E (i.e. using only NS and HS to prune the search) with at most n hypotheses, can be solved with only n-1 hypotheses if rules from B-NRCZT are used to prune the search.

More formally:
B-NRCZT is defined as for the other resolution theories I've already introduced:
BSRT = {ECP, NS}
L1_0 = BSRT + HS
B-NRCZT1 = L1_0 + B-NRCZT1 = NRCZT1
B-NRCZTn+1 = B-NRCZTn + rule for nrczt-braids of length n.

B-NRCZT = union of all the B-NRCZTn {= B-NRCZT729, as no braid can have a longer length}

For any resolution theory T, T&E(T, n) is to be understood as the extension of the T&E(T) procedure defined in the above post, obtained by allowing it to generate auxiliary grids at any depth ≤ n.

Proof: this is an obvious corollary of the theorem in the previous post.


It is also obvious that other theorems can be obtained by projecting everything into the rc-space (or any of the rn, cn or bn spaces), e.g.
Theorem: T&E(NS, n) = T&E(B-XYZT, n-1)
where an xyzt-braid of length k is defined in an obvious way as the 2D counterpart of an nrczt-braid of length k, in rc-space.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Mon Sep 29, 2008 9:47 am


The scope of nrczt-braids (concrete results)


There are several ways one can use the theorem saying that nrczt-braids make the same eliminations and can solve the same puzzles as ordinary T&E (with no guessing).

As a player, if we eliminate a candidate by T&E in an auxiliary grid where we use only ECP, NS and HS, then we know that we could justify this elimination by an nrczt-braid. Of course, knowing that something is possible is not the same thing as seeing it done in real life. Otherwise, why should we solve puzzles: for all the puzzles we try to solve, we generally know in advance that they have a solution.

The equivalence theorem can also be used to answer the following question: what is the scope of nrczt-braids? In this case, we only want to know whether a puzzle is solvable by braids, without knowing exactly by which braids or at what level it is in the B-NRCZT rating (i.e. the length of the longest braids necessary to solve it). In this case, we can merely answer "all the puzzles that can be solved by T&E" and use this much faster procedure in all our computations. That's what I've done below.


1) Random collections
All the 10,000 minimal puzzles in the sudogen0 collection randomly generated by suexg are solvable by braids; that's no fresh news, as they were already all solvable by the simpler nrczt-whips (chains and lassos if you prefer the old style).

I've therefore generated and tested 1,000,000 minimal puzzles with the same generator: all of them are solvable by nrczt-braids.
Open question: are all of them solvable by nrczt-whips (as is the case for the first 10,000)? It would be too long to check directly with SudoRules.


2) Relationship with the Sudoku Explainer rating (SER)
We know that puzzles with high SER are very rare and are difficult to obtain with a random generator. I therefore tried another collection biased towards high SER.
We already knew that nrczt-whips can solve almost any puzzle upto SER 9.3 and some puzzles at SER 9.4.
With braids, we can go a little further. Computations on gsf's collection of 8153 hardest show that:
- nrczt-braids can solve almost any puzzle in it upto SER 9.8;
- the proportion of solvable puzzles decreases as SER increases upto 10.2.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby fcom » Mon Sep 29, 2008 3:55 pm

Your info is very usefull for me ...
I m begginer yet
Thank you!!!!!!!!!!!!!!!!!:D
fcom
 
Posts: 1
Joined: 29 September 2008

Postby denis_berthier » Mon Sep 29, 2008 10:49 pm

Hi fcom,

Welcome on this forum.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Mon Sep 29, 2008 10:52 pm


Experimental results for T&E(B-NRCZT)

I've already shown that almost all the puzzles can be solved by braids. Let's now concentrate on the hardest.

Using the equivalence between T&E(B-NRCZT) and T&E(ECP+NS+HS, 2) [i.e. T&E at depth 2 pruned by only ECP, NS and HS] proven above, I obtain the following experimental results.

All the known puzzles can be solved by T&E(B-NRCZT), i.e. by T&E at depth one (a single hypothesis at a time) pruned by rules for nrczt-braids.

Some time ago, I conjectured that any puzzle could be solved at depth one of T&E if nrczt-whips were used to prune the search; and I showed that this was true for EasterMonster.
I still don't know whether this conjecture is true.
But if we take braids instead of whips, then it becomes experimentally true (I have no formal proof though).
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Wed Oct 01, 2008 12:06 am


Whip example


Flashback on the whips, with an illustrative example which was still missing. I've now finished replacing nrczt- chains and lassos by nrczt-whips in SudoRules.

I've chosen this example because it displays the 4 kinds of whips: rc, rn, cn and bn.

This example is grid "282 hard" from the Sudoku-factory forum.

In the full nrc-notation, the dot at the place of the last rlc indicates that no rlc is possible.

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


***** SudoRules version 13.7w *****
1.....2........3.4.4.5.6....7...8.4...8.4.1...9.2...6....1.7.8.5.7........3.....9
hidden-single-in-a-block ==> r1c9 = 6
interaction row r8 with block b8 for number 9 ==> r7c5 <> 9
interaction block b3 with row r3 for number 8 ==> r3c5 <> 8, r3c1 <> 8, r9c8 <> 5, r5c8 <> 5
nrc-chain[3] n3{r8c8 r5c8} - n3{r5c2 r1c2} - n3{r3c1 r3c5} ==> r8c5 <> 3
nrc-chain[3] n3{r7c9 r7c5} - n3{r3c5 r3c1} - n3{r1c2 r5c2} ==> r5c9 <> 3
nrc-chain[3] n3{r7c5 r7c9} - n3{r8c8 r5c8} - n3{r5c2 r1c2} ==> r1c5 <> 3
nrc-chain[3] n3{r5c8 r8c8} - n3{r7c9 r7c5} - n3{r3c5 r3c1} ==> r5c1 <> 3
nrct-chain[3] n7{r2c1 r3c1} - n3{r3c1 r3c5} - n2{r3c5 r3c3} ==> r2c1 <> 2

At this point, the PM is:
Code: Select all
  +-------------------+-------------------+-------------------+       
  | 1     358   59    | 34789 789   349   | 2     579   6     |       
  | 6789  2568  2569  | 789   12789 129   | 3     1579  4     |       
  | 2379  4     29    | 5     12379 6     | 789   179   178   |       
  +-------------------+-------------------+-------------------+       
  | 236   7     1256  | 369   13569 8     | 59    4     235   |       
  | 26    2356  8     | 3679  4     359   | 1     2379  257   |       
  | 34    9     145   | 2     1357  135   | 578   6     3578  |       
  +-------------------+-------------------+-------------------+       
  | 2469  26    2469  | 1     2356  7     | 456   8     235   |       
  | 5     1268  7     | 34689 2689  2349  | 46    123   123   |       
  | 2468  1268  3     | 468   2568  245   | 4567  127   9     |       
  +-------------------+-------------------+-------------------+

and we get our first whip
nrczt-whip-cn[3] n3{r5c2 r1c2} - n3{r1c4 r8c4} - {n3r8c8 .} ==> r5c6 <> 3
in full nrc-notation:
nrczt-whip-cn[3] n3{r5 r1}c2 - n3{r1 r8 r4* r5*}c4 - n3{r8 . r5*}c8 ==> r5c6 <> 3
This is a very special whip, making no use of t-candidates. We could name it an nrcz-whip (nrcz-whips are not programmed independently in SudoRules).
The suffix cn in its name indicates that the final contradiction will be obtained in a cn-cell, which will be the cn-cell of the last, isolated left-linking candidate, here c8n3. And indeed, in this cn-cell, n3 appears only in rows r8 and r5: r8 is impossible (left-linking candidate) and r5 is impossible (nrc-linked to the target). Repeated in this particular case, the proof of the general theorem goes like this: if the target was true, in column c8, there'd be no place for number n3; therefore the target is false. But of course, we never have to re-do this proof.

nrct-chain[3] {n9 n5}r1c3 - n5{r6c3 r5c2} - {n5 n9}r5c6 ==> r1c6 <> 9
nrc-chain[4] n3{r3c5 r3c1} - n3{r1c2 r5c2} - n3{r5c8 r8c8} - n3{r7c9 r7c5} ==> r6c5 <> 3, r4c5 <> 3
nrc-chain[4] n3{r7c9 r7c5} - n3{r3c5 r3c1} - n3{r1c2 r5c2} - n3{r5c8 r8c8} ==> r8c9 <> 3
nrct-chain[3] {n1 n2}r8c9 - n2{r4c9 r5c8} - n3{r5c8 r8c8} ==> r8c8 <> 1
nrct-chain[5] {n2 n9}r3c3 - {n9 n5}r1c3 - n5{r6c3 r5c2} - n3{r5c2 r1c2} - n3{r3c1 r3c5} ==> r3c5 <> 2
interaction row r3 with block b1 for number 2 ==> r2c3 <> 2, r2c2 <> 2
nrct-chain[5] n2{r3c3 r3c1} - {n2 n6}r5c1 - {n6 n3}r4c1 - {n3 n4}r6c1 - n4{r9c1 r7c3} ==> r7c3 <> 2


At this point, the PM is:
Code: Select all
  +-------------------+-------------------+-------------------+       
  | 1     358   59    | 34789 789   34    | 2     579   6     |       
  | 6789  568   569   | 789   12789 129   | 3     1579  4     |       
  | 2379  4     29    | 5     1379  6     | 789   179   178   |       
  +-------------------+-------------------+-------------------+       
  | 236   7     1256  | 369   1569  8     | 59    4     235   |       
  | 26    2356  8     | 3679  4     59    | 1     2379  257   |       
  | 34    9     145   | 2     157   135   | 578   6     3578  |       
  +-------------------+-------------------+-------------------+       
  | 2469  26    469   | 1     2356  7     | 456   8     235   |       
  | 5     1268  7     | 34689 2689  2349  | 46    23    12    |       
  | 2468  1268  3     | 468   2568  245   | 4567  127   9     |       
  +-------------------+-------------------+-------------------+


and we get our next two whips (still cn-whips), the two of which use both t- and z- candidates:

nrczt-whip-cn[5] n9r7{c1 c3} - {n9 n5}r1c3 - {n5 n6}r2c3 - n6{r4c3 r5c2} - {n5r5c2 .} ==> r7c1 <> 6
in full nrc-notation:
nrczt-whip-cn[5] n9{r7c1 r7c3} - {n9 n5}r1c3 - {n5 n6 n9#n9r7c3}r2c3 - n6{r4c3 r5c2 r4c1*} - n5{r5 . r1#n5r1c3 r2#n5r1c3}c2 ==> r7c1 <> 6


nrczt-whip-cn[5] n2{r2c5 r2c6} - n1{r2c6 r6c6} - n1{r4c5 r3c5} - n3{r3c5 r3c1} - {n7r3c1 .} ==> r2c5 <> 7
in full nrc-notation:
nrczt-whip-cn[5] n2r2{c5 c6} - n1{r2 r6}c6 - n1{r4 r3 r2* r5#n1r6c6}c5 - n3r3{c5 c1} - n7{r3 . r2*}c1 ==> r2c5 <> 7


Now comes an rn-whip:
nrczt-whip-rn[5] n2{r9c2 r5c2} - n3{r5c2 r1c2} - n5{r1c2 r2c2} - {n5 n9}r1c3 - {n9r7c3 .} ==> r7c1 <> 2
in full nrc-notation:
nrczt-whip-rn[5] n2{r9 r5 r7* r8*}c2 - n3{r5 r1}c2 - n5{r1 r2 r5#n2r5c2}c2 - {n5 n9}r1c3 - n9r7{c3 . c1*} ==> r7c1 <> 2
the first cell has two z-candidates (a rare situation).

nrct-chain[5] n1{r9c2 r9c8} - {n1 n2}r8c9 - {n2 n3}r8c8 - n3{r8c6 r7c5} - n2{r7c5 r7c2} ==> r9c2 <> 2

At this point, the PM is:
Code: Select all
  +-------------------+-------------------+-------------------+       
  | 1     358   59    | 34789 789   34    | 2     579   6     |       
  | 6789  568   569   | 789   1289  129   | 3     1579  4     |       
  | 2379  4     29    | 5     1379  6     | 789   179   178   |       
  +-------------------+-------------------+-------------------+       
  | 236   7     1256  | 369   1569  8     | 59    4     235   |       
  | 26    2356  8     | 3679  4     59    | 1     2379  257   |       
  | 34    9     145   | 2     157   135   | 578   6     3578  |       
  +-------------------+-------------------+-------------------+       
  | 49    26    469   | 1     2356  7     | 456   8     235   |       
  | 5     1268  7     | 34689 2689  2349  | 46    23    12    |       
  | 2468  168   3     | 468   2568  245   | 4567  127   9     |       
  +-------------------+-------------------+-------------------+


and we get our first rc-whip:
nrczt-whip-rc[5] {n6 n2}r5c1 - {n2 n3}r4c1 - {n3 n9}r4c4 - {n9 n5}r5c6 - {n5r5c2 .} ==> r4c3 <> 6
in full nrc-notation:
nrczt-whip-rc[5] {n6 n2}r5c1 - {n2 n3 n6*}r4c1 - {n3 n9 n6*}r4c4 - {n9 n5}r5c6 - {n5 . n2#n2r5c1 n3#n3r4c1 n6*}r5c2 ==> r4c3 <> 6


The end works similarly:

nrct-chain[4] n6{r2c3 r7c3} - n9{r7c3 r7c1} - n4{r7c1 r9c1} - n8{r9c1 r2c1} ==> r2c1 <> 6
nrczt-whip-rn[5] n7{r5c4 r6c5} - n7{r1c5 r1c4} - n4{r1c4 r1c6} - n3{r1c6 r1c2} - {n3r5c2 .} ==> r5c8 <> 7
nrct-chain[6] n7{r2c1 r3c1} - n3{r3c1 r1c2} - n3{r5c2 r5c8} - {n3 n2}r8c8 - {n2 n1}r8c9 - {n1 n7}r9c8 ==> r2c8 <> 7
nrct-chain[6] n8{r9c1 r2c1} - n7{r2c1 r3c1} - n7{r3c9 r1c8} - n5{r1c8 r2c8} - {n5 n6}r2c2 - {n6 n2}r7c2 ==> r9c1 <> 2
interaction block b7 with column c2 for number 2 ==> r5c2 <> 2
nrc-chain[3] n2{r7c2 r8c2} - {n2 n3}r8c8 - n3{r7c9 r7c5} ==> r7c5 <> 2
nrct-chain[6] n8{r9c1 r2c1} - n7{r2c1 r3c1} - n7{r3c9 r1c8} - n5{r1c8 r2c8} - {n5 n6}r2c2 - n6{r2c3 r7c3} ==> r9c1 <> 6
interaction column c1 with block b4 for number 6 ==> r5c2 <> 6
nrc-chain[6] {n8 n4}r9c1 - {n4 n3}r6c1 - n3{r5c2 r5c8} - {n3 n2}r8c8 - {n2 n1}r8c9 - n1{r9c8 r9c2} ==> r9c2 <> 8
nrczt-whip-bn[6] n3{r3c1 r1c2} - n3{r5c2 r5c8} - {n3 n2}r8c8 - {n2 n1}r8c9 - {n1 n7}r9c8 - n7r3c8 - ==> r3c1 <> 7
hidden-singles ==> r2c1 = 7, r9c1 = 8
interaction block b7 with row r7 for number 4 ==> r7c7 <> 4
hidden-pairs-in-a-row {n4 n9}r7{c1 c3} ==> r7c3 <> 6
hidden-single-in-a-column ==> r2c3 = 6
xy-chain[3] {n9 n5}r1c3 - {n5 n8}r2c2 - {n8 n9}r2c4 ==> r1c5 <> 9, r1c4 <> 9
nrc-chain[3] {n9 n8}r2c4 - {n8 n7}r1c5 - n7{r6c5 r5c4} ==> r5c4 <> 9
nrczt-whip-rn[5] n3{r8c8 r5c8} - {n3 n5}r5c2 - {n5 n9}r5c6 - n9{r8c6 r8c5} - {n8r8c5 .} ==> r8c4 <> 3
nrc-chain[2] n3{r5c2 r1c2} - n3{r1c4 r4c4} ==> r4c1 <> 3
naked-pairs-in-a-block {n2 n6}{r4c1 r5c1} ==> r4c3 <> 2
hidden-single-in-a-column ==> r3c3 = 2
nrczt-whip-cn[5] n3{r4c4 r6c6} - n1{r6c6 r2c6} - n2{r2c6 r2c5} - n9{r2c5 r3c5} - {n9r3c7 .} ==> r4c4 <> 9
nrczt-whip-bn[5] n8{r8c4 r8c5} - n9{r8c5 r8c6} - n3{r8c6 r7c5} - n6{r7c5 r4c5} - {n9r4c5 .} ==> r8c4 <> 6
nrczt-whip-rn[5] {n4 n6}r9c4 - n6{r4c4 r4c5} - n9{r4c5 r5c6} - n9{r8c6 r8c5} - {n8r8c5 .} ==> r8c4 <> 4
naked-pairs-in-a-column {n8 n9}{r2 r8}c4 ==> r1c4 <> 8
nrct-chain[6] n1{r8c9 r3c9} - n8{r3c9 r6c9} - n7{r6c9 r5c9} - {n7 n6}r5c4 - {n6 n2}r5c1 - n2{r4c1 r4c9} ==> r8c9 <> 2
naked and hidden singles ==> r8c9 = 1, r9c2 = 1
nrct-chain[3] n8{r6c7 r3c7} - {n8 n7}r3c9 - n7{r6c9 r6c7} ==> r6c7 <> 5
nrct-chain[6] n9{r5c6 r4c5} - {n9 n5}r4c7 - {n5 n6}r7c7 - n6{r7c2 r8c2} - n6{r8c5 r9c5} - n5{r9c5 r9c6} ==> r5c6 <> 5
naked and hidden singles ==> r5c6 = 9, r4c7 = 9
interaction column c7 with block b9 for number 5 ==> r7c9 <> 5
naked-pairs-in-a-block {n2 n3}{r7c9 r8c8} ==> r9c8 <> 2
naked-single ==> r9c8 = 7
interaction row r1 with block b2 for number 7 ==> r3c5 <> 7
interaction row r9 with block b8 for number 2 ==> r8c6 <> 2,> r8c5 <> 2
naked-pairs-in-a-column {n3 n4}{r1 r8}c6 ==> r9c6 <> 4, r6c6 <> 3
hidden-single-in-a-block ==> r4c4 = 3
naked-pairs-in-a-row {n5 n9}r1{c3 c8} ==> r1c2 <> 5
hidden-pairs-in-a-block {n8 n9}{r8c4 r8c5} ==> r8c5 <> 6
xy-chain[3] {n5 n2}r4c9 - {n2 n3}r5c8 - {n3 n5}r5c2 ==> r5c9 <> 5
hidden-single-in-a-row ==> r5c2 = 5
naked-singles
GRID 0 SOLVED. LEVEL = L6, MOST COMPLEX RULE = NRCZT6
135784296
786912354
942536718
671358942
258649137
394271865
429167583
567893421
813425679

10/03/08: changed the nrc-notation for the end of whips, so as to make it closer to that of chains: - {nrc .} instead of - nrc -
Last edited by denis_berthier on Fri Oct 03, 2008 4:30 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby champagne » Wed Oct 01, 2008 2:03 am

a relatively easy puzzle using one ALS/AHS/AC


Code: Select all
100000200000000304040506000070008040008040100090200060000107080507000000003000009
1 r1c9=6

Code: Select all
1     358  59   |34789 3789  349  |2    579   6     
26789 2568 2569 |789   12789 129  |3    1579  4     
2379  4    29   |5     12379 6    |789  179   178
----------------------------------------------
236   7    1256 |369   13569 8    |59   4     235   
236   2356 8    |3679  4     359  |1    2379  2357   
34    9    145  |2     1357  135  |578  6     3578 
-------------------------------------------------
2469  26   2469 |1     2356  7    |456  8     235 
5     1268 7    |34689 23689 2349 |46   123   123   
2468  1268 3    |468   2568  245  |4567 127   9     


[]7r3c1 - 7r3c79 = 7r123c8 - 7r9c8 = 7r9c7 - 7r36c7 ACr346c7:( = 5r46c7) - 5r456c9 = 5r7c9 - 3r7c9 = 3r7c5 - 3r3c5 = 3r3c1 - 7r3c1


2 r2c1=7 3 r9c1=8 4 r2c3=6
->XY WING r2c2 58 (1)=r1c3 59 (2)=r2c4 89
->UR P1=r8c4 3689 P2=r8c7 46 P3=r9c4 46 P4=r9c7 4567



Code: Select all
1    358  59   |34a7o8 378   3a4A |2    579  6     
7    58   6    |89     12c89 129  |3    159  4     
239I 4    29   |5      1379  6    |789  179  178
--------------------------------------------------
236  7    125  |369    13569 8    |59   4    235   
236  35   8    |367O9  4     359  |1    2379 2357   
3I4i 9    14I5 |2      1357o 135  |57   6    3578 
-------------------------------------------------
4I9i 26   4i9I |1      2356  7    |56   8    235 
5    126  7    |3689   23689 2349 |46   123  123   
8    126  3    |4A6a   256   245  |4567 127  9



#[] 3r6c9=>7r6c5.o []7r6c7 - 8r6c7 = 8r6c9 - 3r6c9 []7r6c9 - 3r6c9
# a
[]3r6c1==9r3c1.I - 3r3c1 = 3r1c2 - 3r1c6.a
[]3r6c5 - 3r7c5 = 3r8c456 - 3r8c8 = 3r5c8 - 3r5c2 = 3r1c2 - 3r1c6.a
[]3r6c6 - 3r1c6.a
[]3r6c9 <=7r1c4.o - 4r1c4.a

5 r1c6=4 6 r8c7=4 7 r9c4=4

Code: Select all
1   358  59  |378  378    4   |2    579  6     
7   58   6   |89   1289   129 |3    159  4     
239 4    29  |5    1379   6   |789  179  178
-----------------------------------------
236 7    125 |369  13569  8   |59   4    235   
236 35   8   |3679 4      359 |1    2379 2357   
34  9    145 |2    1357   135 |578  6    3578 
-----------------------------------------
49  26   49  |1    2356   7   |56   8    235 
5   1K26 7   |3689 23689  239 |4    123  123   
8   1k26 3   |4    256    25  |567  1K27 9


# "K"
[]7r6c5 - 7r5c4 = 7r1c4 - 3r1c4 = 3r13c5 - 3r7c5 = 3r7c9 - 5r7c9 = 7r9c8 - 1r9c8.K
[]7r6c7 - 7r9c7 = 7r9c8 - 1r9c8.K
[]7r6c9 - 8r6c9 = 8r3c9 - 1r3c9 = 1r8c9 - 1r8c2.K

5r7c9 = 7r9c8 as in the first step

8 r9c2=1


Code: Select all
1    3A58 59  |378  378   4   |2    579  6     
7    58   6   |89   1289  129 |3    159  4     
23a9 4    29  |5    13A79 6   |789  179  178
----------------------------------------------
236  7    125 |369  13569 8   |59   4    235   
236  3a5A 8   |36O9 4     359 |1    2379 2357   
34   9    145 |2    1357  135 |578  6    3578 
----------------------------------------------
49   26   49  |1    2356  7   |56   8    23I5m 
5    26   7   |3689 23689 239 |4    123  123   
8    1    3   |4    256   25  |567m 2m7M 9 


#"m"
[]5r5c2==3r3c5.A - 3r7c5 = 3r7c9 - 5r7c9.m
[]5r5c6 - 5r9c6 = 2r9c6 - 2r9c8.m
[]5r5c9 - 5r7c9.m


Nothing special to the end
champagne
2017 Supporter
 
Posts: 5677
Joined: 02 August 2007
Location: France Brittany

Postby denis_berthier » Wed Oct 01, 2008 2:11 am

champagne wrote:a relatively easy puzzle using one ALS/AHS/AC

Any puzzle has lots of resolution paths. Mine was an illustrative example, not using UR.
The NRCZT rating, NRCZT6, corresponds to relatively easy puzzles anyway.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby champagne » Wed Oct 01, 2008 2:13 am

denis_berthier wrote:Any puzzle has lots of resolution paths. Mine was an illustrative example, not using UR.


UR is not important here. The key point is the ALS/AHS/AC r346c7.
champagne
2017 Supporter
 
Posts: 5677
Joined: 02 August 2007
Location: France Brittany

Postby denis_berthier » Wed Oct 01, 2008 2:22 am

champagne wrote:The key point is the ALS/AHS/AC r346c7.

The key point is what one wants it to be.
The key point of my post was illustrating whips.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby StrmCkr » Wed Oct 01, 2008 10:23 pm

how can u jutify easy
with 120+ lines of text (moves) to find the solution?

when it can be soled with fewer applications?
like champanes 14
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 647
Joined: 05 September 2006

Postby denis_berthier » Wed Oct 01, 2008 11:34 pm

StrmCkr wrote:how can u jutify easy
with 120+ lines of text (moves) to find the solution?
when it can be soled with fewer applications?
like champanes 14

In my resolution paths, I systematically give all the steps, even the simplest - so that anyone can check the solution. Champagne gives only some steps.

Anyway, the number of steps can't be a measure of difficulty and I've never seen any proposal in this sense.
A puzzle that uses only elementary rules to do lots of eliminations will have lots of elementary steps.

As there is no general agreement on any rating system, discussions on such topics can be endless and sterile.
I said "relatively easy". This is related to the hardest rule used, here NRCZT6. If I mention its SER: 9.0, it doesn't seem so easy. Conclusion: it seems easier with nrczt-chain rules than for SE. It may seem easier if you consider another set of rules. But the converse is likely to be true of other puzzles.

The purpose of this example was to illustrate whips, not to launch a debate about rating. I've another thread for this purpose, where different rating systems are compared.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Thu Oct 02, 2008 4:21 am


Some teasing about T&E


As T&E is a very sensitive issue, I was expecting some reactions after my new T&E theorem.
As everyone's sleeping, let me be a little provocative about how it could be interpreted.

One could argue that, as the result of T&E can always be obtained by braids, which are a kind of pattern, then it is absurd to reject T&E as a resolution technique.

One could also argue that what the theorem shows is that, as soon as we accept nets (even relatively mild ones, such as braids), we are not far from accepting T&E. One could conclude that if T&E is to be rejected, then nets are to be rejected.

I now let you meditate on this.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to Advanced solving techniques