Nice loops for advanced level players - grouped nice loop

Advanced methods and approaches for solving Sudoku puzzles

Nice loops for advanced level players - grouped nice loop

Postby Jeff » Wed Dec 07, 2005 12:48 pm

Grouped nice loop is short for grouped inference nice loop. Carcul has already superbly described one type of grouped nice loop, namely Strong grouped nice loop that uses grouped x-nodes as grouped nodes. Here, I am going to describe its complement, namely Weak grouped nice loop that uses with almost locked sets as grouped nodes.

Apart from grouped x-node and almost locked set, there are also other grouped nodes that can be used to make inferences within grouped nice loops. Together, these grouped nodes form a list including but are not limited to the following:

    grouped x-node, Note: a grouped x-node nice loop is equivalent to an empty rectangle deduction.
    almost locked set (Lockedset+1)
    almost unique rectangle (AUR)
    almost x-wing, Note: an almost x-wing nice loop is equivalent to a fillet-O-fish.
    almost NxN fish (finned fish)
    almost BUG-Lite (BUG-Lite+2), Note: all almost unique patterns are almost BUG-Lites.
A grouped nice loop may have one or more of the above grouped nodes embedded in a simple nice loop. Names have been used in some special cases listed below:

    Grouped x-cycle - an x-cycle with grouped x-node(s) as grouped node(s).

    Grouped xy-chain - an xy-chain with almost locked set(s) as grouped node(s).

    Strong Grouped Nice Loop - a simple nice loop with grouped x-node(s) as grouped node(s).

    Weak Grouped Nice Loop - a simple nice loop with almost locked set(s) as grouped node(s).

    AUR Nice Loop - a simple nice loop with almost unique rectangle(s) as grouped node(s).

    Almost x-wing Nice Loop - a simple nice loop with almost x-wing(s) as grouped node(s).
Candidate deduction theorems 1 to 5 for simple nice loops can be extended to grouped nice loops provided that the nodes making the deductions are nodes that contain only one cell.

I will demonstrate how to spot this type of grouped nice loop via a few examples, including an xyz-wing, a grid posted by Bennys for the almost locked set xy-wing rule and an almost x-wing.

Code: Select all
Example 1 - Grouped xy-chain (xyz wing)

+----------------+----------------+----------------+
| 7    1    4    | 2    3    9    | 8    6    5    |
| 2    5    9    | 8    6    1    | 4    7    3    |
| 3    6    8    | 57   4    57   | 2    1    9    |
+----------------+----------------+----------------+
| 4    38   7    | 56   1    2568 | 35   9    28   |
| 9    38   6    | 47   58   247  | 35   24   1    |
| 5    2    1    | 3    9   *48   | 7    48   6    |
+----------------+----------------+----------------+
| 8    9    3    | 1    7    45   | 6    25   24   |
| 6    4    2    | 9    58   3    | 1    58   7    |
| 1    7    5    |*46   2   *468  | 9    3    48   |
+----------------+----------------+----------------+

An xyz-wing is regarded as a chain with triple implication streams due to the inference made by the naked pair. With the definition of grouped nice loop, this triple chain can now be expressed as a double chain with a grouped node [r9c6|r9c4]. This grouped nice loop, also specifically called an grouped xy-chain, has links of weak inference associated with the grouped node containing an almost locked set (lockedset+1).

Nice loop notation:
[r7c6]-4-[r6c6]-8-[r9c6|r9c4]-4-[r7c6] => r7c6<>4

where
[r9c6|r9c4] is a lockedset+1 grouped node
[r6c6]-8-[r9c6|r9c4]-4-[r7c6] are grouped inferences meaning: r6c6=8 => r9c6=r9c4=46 => r7c6<>4

Code: Select all
Example 2 - Grouped xy-chain (almost locked set xy-wing rule)

+-------------------+-------------------+-------------------+
| 459   1    %479   |%78    3    %89    | 2    %58    6     |
| 59    569   679   | 278   289   4     |^35    1358  13    |
| 8     3     2     | 5     6     1     | 7     9     4     |
+-------------------+-------------------+-------------------+
|*139   7    *139   | 6     4     5     | 8     123   1239  |
| 6     28   *134   | 9     28    7     |^34    13    5     |
| 24    289   5     | 238   1     238   |^49    6     7     |
+-------------------+-------------------+-------------------+
| 7     4     39    | 23    259   6     | 1     235   8     |
| 12359 2569  1369  | 4     2589  2389  | 3569  7     239   |
| 2359  2569  8     | 1     7     239   | 3569  4     239   |
+-------------------+-------------------+-------------------+

In this example, Bennys proved that r6c2<>9 by a technique called almost locked set xy-wing rule. The same deduction can be viewed as a grouped nice loop with both multiple inference and grouped inference where the grouped node is an almost locked set [r5c3|r4c1|r4c3].

Nice loop notation:
[r6c2]-9-[r6c7]-4-[r5c7]-3-[r2c7]-5-[r1c8](-8-[r1c4]-7-[r1c3])-8-[r1c6]-9-[(r1c3)]-4-[r5c3|r4c1|r4c3]-9-[r6c2] => r6c2<>9

where
(-8-[r1c4]-7-[r1c3]) and (r1c3) is a multiple inference meaning: r1c8=8 => r1c6=9 & r1c4=7 => r1c3=4
[r5c3|r4c1|r4c3] is a lockedset+1 grouped node
[(r1c3)]-4-[r5c3|r4c1|r4c3]-9-[r6c2] are grouped inferences meaning: r1c3=4 => r5c3, r4c1 & r4c3 is a locked set of 139 => r6c2<>9

As a matter of interest, if this deduction is to be represented by a chain, it would be a forcing chain with 5 implication streams.

Code: Select all
Example 3 - Strong Grouped Nice loop

 *---------------------------------------------------------------------*
 | 7      156    456    |  2      458    146    | 3      458    9      |
 | 19     3      459    |  14589  7      149    | 2      458    6      |
 | 269    269    8      |  3      45     69     | 14     7      15     |
 |----------------------+-----------------------+----------------------|
 | 3      2678   267    | #1478   9     *1247   | 5      1246   128    |
 | 2689   4      25679  |  1578   258    127    | 1689   3      128    |
 | 289    2589   1      | #458    6      3      | 49     249    7      |
 |----------------------+-----------------------+----------------------|
 | 12689  12689  269    | ^469   ^24     5      | 7      1269   3      |
 | 4      2679   3      |  679    1     ^279    | 689    2569   258    |
 | 5      12679  2679   |  679    3      8      | 169    1269   4      |
 *---------------------------------------------------------------------*

This example is really a strong grouped nice loop with a grouped x-node. It is included here to clarify any wrong impression from the 2 examples above that a grouped nice loop should have all links with weak inferences. In fact, the inferences within a grouped nice loop could be a mixture of strong and weak inferences as shown here.

Nice loop notation:
[r4c6]-2-[r8c6]=2=[r7c5]=4=[r7c4]-4-[r6c4|r4c4]=4=[r4c6] =>r4c6<>2

where
[r6c4|r4c4] is a grouped x-node.
[r7c4]-4-[r6c4|r4c4]=4=[r4c6] are grouped inferences.

Code: Select all
Example 4 - Almost x-wing Nice Loop (Filet-O-Fish)

Image

This example is a grouped nice loop with an almost x-wing and a grouped x-node as grouped nodes. Other almost patterns work in the same principle.

Nice loop notation:
[r5c4]-1-[almost x-wing:r24c24]=1=[r4c56]-1-[r5c4] => r5c4<>1
where both [almost x-wing:r24c24] and [r4c56] are grouped nodes.
Last edited by Jeff on Fri Jun 02, 2006 12:42 pm, edited 10 times in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Carcul » Wed Dec 07, 2005 2:13 pm

Congratulations one more time for this further extension.:D
What I don't understand is: why did you ask me if I agreed that with triple implication chain we have reached the limit of the bilocation/bivalue plot technique, if you keep posting more extensions of it? You are answering your own question! What is your intention?

BTW, in your first example, you can express the same conclusion with a simple nice loop or a strong nice loop.:D

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby Jeff » Wed Dec 07, 2005 5:20 pm

Carcul wrote:What I don't understand is: why did you ask me if I agreed that with triple implication chain we have reached the limit of the bilocation/bivalue plot technique, if you keep posting more extensions of it? You are answering your own question! What is your intention?

The essence of my question is in the word 'Chain'. Notice that all the nice loops derived from the bilocation/bivalue plot technique are forcing nets. Nick70 has developed a solver that can identify poly-implication forcing chains (he called them bifurcating chains). These are pure chains, but surely beyond human recognition. I feel that, besides forcing nets, triple chain is the limit of bilocation/bivalue plot.

Carcul wrote:BTW, in your first example, you can express the same conclusion with a simple nice loop or a strong nice loop.:D

Could you list these nice loops for us?
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby rubylips » Wed Dec 07, 2005 6:46 pm

Jeff,

I think this is what I would call an extended disjoint subset link, which I would write (probably - it's not yet implemented) r7c6=<4|8>=r9c6, i.e. when r7c6 contains a 4, r9c6 contains an 8. In general, I prefer shorter chains with complicated links to the long strong-link-only chains produced by computer solvers (such as mine!) as I think they replicate human thinking more accurately.

BTW, here's a very straightforward solution to your first puzzle:

Code: Select all
Consider the chain r5c5-8-r8c5-8-r8c8-8-r6c8-8-r6c6.
When the cell r5c5 contains the value 8, so does the cell r6c6 - a contradiction.
Therefore, the cell r5c5 cannot contain the value 8.
When the cell r6c6 contains the value 8, so does the cell r5c5 - a contradiction.
Therefore, the cell r6c6 cannot contain the value 8.
- The moves r5c5:=8 and r6c6:=8 have been eliminated.
The value 4 is the only candidate for the cell r6c6.
rubylips
 
Posts: 149
Joined: 01 November 2005

Postby Carcul » Wed Dec 07, 2005 8:28 pm

Jeff,

Here are some loops that also prove r7c6<>4 in the first example:

Simple nice loop 1: [r7c6]-4-[r9c4]-6-[r4c4]-5-[r5c5]-8-[r6c6]-4-[r7c6]

Simple nice loop 2: [r7c6]=5=[r8c5]-5-[r5c5]-8-[r6c6]-4-[r7c6]

Strong nice loop 1: [r7c6]-4-[r6c6]-8-[r6c8]=8=[r8c8]-8-[r8c5]-5-[r5c5]
=5=[r4c4|r4c6]-5-[r4c7]-3-[r4c2]-8-[r4c9]-2-[r7c9]-4-
[r7c6]

Strong nice loop 2: [r7c6|r9c6]-4-[r9c4]=4=[r5c4]=7=[r3c4]=5=[r4c4]
=6=[r4c6]=2=[r5c6]-2-[r5c8]-4-[r6c8]=4=[r6c6]-4-
[r7c6|r9c6]

This last loop proves that both r7c6 and r9c6 cannot be 4.
But, of course, your new weak nice loop is much more simple and easier to spot. Please continue your good work Jeff.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby Jeff » Thu Dec 08, 2005 2:22 am

rubylips wrote:In general, I prefer shorter chains with complicated links to the long strong-link-only chains produced by computer solvers (such as mine!) as I think they replicate human thinking more accurately.

These forcing nets (shorter chains with complicated links) are so powerful and we know that they are well within human ability. Excuse me for reserving the term 'chain' for simple nice loops.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Mon Mar 06, 2006 6:27 am

The first post has be edited with the following:

    Title changed

    Terminology revised in line with definitions

    Nice loop notation - Extra bracket added to a node to indicate its linkage with a multiple inference from upstream.

    An example added
Jeff
 
Posts: 708
Joined: 01 August 2005


Return to Advanced solving techniques