The New Sudoku Players' Forum

[denis_berthier]

Definition of Extended Quasi-Loops in SLITHERLINK

In my book [PBCS2], I introduced the concept of a Quasi-Loop in Slitherlink, a very powerful chain pattern that allows to take into account the global only-one-loop constraint.
In short, a Quasi-Loop is a closed loop (made of decided H/V lines) minus a "missing line" (i.e. an undecided H/V line) that would allow to close it if it was TRUE. Depending on the length of this missing line, the conclusion of the QL resolution rule is, the "missing line" can be asserted as FALSE or TRUE.

This powerful pattern can be extended with the following definitions:

• two undecided H or V lines with a common Point are said to have an isolated junction (at this Point) if the other two lines from this Point are decided and FALSE; as a result, the two given lines can only be TRUE or FALSE at the same time; they behave as a single line;

• a sequence of n H/V lines is called an isolated-HV-chain[n] if all these H/V lines are undecided and any two contiguous H/V lines in the sequence have an isolated junction; as an obvious result, all the lines of this isolated-HV-chain[n] can only be TRUE or FALSE at the same time;

• an Extended-Loop[n] is defined as a Quasi-Loop[p] plus an isolated-HV-chain[q], such that p + q = n and the two chains meet at their two ends, making a closed loop; as a result, depending on the total number of lines touching the given cells, the whole isolated-HV-chain (i.e. all of its HV-lines) can be declared TRUE or FALSE; this is the Extended-Loop resolution rule.

[denis_berthier]

An example of Extended Quasi-Loops in SLITHERLINK
Let’s take the following example (puzzle I.4 from Mebane ):

Code: Select all

. 3 . . 2 . . 2 . .
3 0 . 2 0 2 . 1 2 .
. 3 . . 3 . . 0 . .
. . . . . . . . . .
. . 3 . . . 1 3 0 .
. 3 1 0 . . . 2 . .
. . . . . . . . . .
. . 1 . . 0 . . 2 .
. 3 3 . 1 2 2 . 0 2
. . 1 . . 2 . . 3 .

If we apply all the rules in SlitherRules as defined in [PBCS2], i.e. without the Extended-Loops, we reach the following partial solution:

Code: Select all

.   .———.   .   .———.———.———.———.———.———.
    | 3 |       | 2           2         |
.———.   .———.———.   .   .———.———.———.   .
| 3   0       2   0   2 |     1   2 |   |
.———.   .———.———.   .———.   .   .   .   .
    | 3 |       | 3 |         0     |   |
.   .———.   .   .———.   .   .   .———.   .
                                |       |
.———.———.———.   .   .   .   .———.   .   .
|         3 |             1 | 3   0     |
.   .———.———.   .   .   .   .———.   .....
|   | 3   1   0               2 |   :   :
.   .———.   .   .   .   .   .   .———.....
|       |                           :   :
.................   .   .   .   .———.....
:   :     1     :     0         | 2     |
.................   .   .———.———.   .   .
|   | 3 | 3 |     1   2 | 2       0   2 |
.................———.———.   .———.   .———.
:   :     1     :     2     |   | 3 |
.................———.———.———.   .———.   .


You can see three (and only three) isolated-HV-chains (you could argue there are indeed six chains, as they can be reversed):
• isolated-HV-chains [2]: Hr6c10-Vr6c10
• isolated-HV-chains [2]: Hr11c2-Hr11c3
• isolated-HV-chains [4]: Hr8c3-Hr8c4-Vr8c5-Hr9c4.

(Cell rows and columns are numbered from 1 to 10; as a result, H or V lines are numbered from 1 to 11.)

If we activate xtd-Loops, the part of the resolution rule up to the previous partial solution is unchanged, but then an Extended-Loop appears and it’s enough to allow a full solution using a few more standard Loops (see the “Examples/ Slitherlink/Mebane” folder in CSP-Rules-V2.1 for details of the resolution path). The partial-loop part has length 42 and the isolated-HV-chain part has length 2 (hence the total length, 44):

XTD-LOOP[44]: Hr7c9-Vr6c9-Hr6c8-Vr5c8-Hr5c8-Vr4c9-Hr4c9-Vr3c10-Vr2c10-Hr2c9-Hr2c8-Hr2c7-Vr2c7-Hr3c6-Vr3c6-Hr4c5-Vr3c5-Hr3c4-Hr3c3-Vr3c3-Hr4c2-Vr3c2-Hr3c1-Vr2c1-Hr2c1-Vr1c2-Hr1c2-Vr1c3-Hr2c3-Hr2c4-Vr1c5-Hr1c5-Hr1c6-Hr1c7-Hr1c8-Hr1c9-Hr1c10-Vr1c11-Vr2c11-Vr3c11-Vr4c11-Vr5c11- ==> Hr6c10-Vr6c10 = 0

Notice the convention for writing the Extended-Loop: on the left is the partial-loop made of decided TRUE H/V-lines; on the right is the isolated-HV-chain made of undecided H/V-lines; they all become decided by the conclusion of the rule (i.e. they are all set to FALSE in the present case).

Code: Select all

.   .———.   .   .———.———.———.———.———.———.
    | 3 |       | 2           2         |
.———.   .———.———.   .   .———.———.———.   .
| 3   0       2   0   2 |     1   2 |   |
.———.   .———.———.   .———.   .   .   .   .
    | 3 |       | 3 |         0     |   |
.   .———.   .   .———.   .   .   .———.   .
                                |       |
.———.———.———.   .   .   .   .———.   .   .
|         3 |             1 | 3   0     |
.   .———.———.   .   .   .   .———.   .   .
|   | 3   1   0               2 |       |
.   .———.   .   .   .   .   .   .———.   .
|       |                           |   |
.   .———.   .   .   .   .   .   .———.   .
|   |     1           0         | 2     |
.   .   .———.   .   .   .———.———.   .   .
|   | 3 | 3 |     1   2 | 2       0   2 |
.   .———.   .———.———.———.   .———.   .———.
|         1           2     |   | 3 |
.———.———.———.———.———.———.———.   .———.   .


[Serg]

Hi, Denis!
I solve Slitherlink puzzles regularly, so I am interested in powerful Slitherlink solving techniques. But unfortunately I understood nothing from your definitions. Maybe you should give more examples (with pictures).

You choosed bad example for your techniques demonstration - the puzzle is very simple and can be easily solved by basic techniques. For example, let's consider intermediate position you published.

Code: Select all

+   +---+   +   +---+---+---+---+---+---+
    | 3 |       | 2           2         |
+---+   +---+---+   +   +---+---+---+   +
| 3   0       2   0   2 |     1   2 |   |
+---+   +---+---+   +---+   +   +   +   +
    | 3 |       | 3 |         0     |   |
+   +---+   +   +---+   +   +   +---+   +
                                |       |
+---+---+---+   +   +   +   +---+   +   +
|         3 |             1 | 3   0     |
+   +---+---+   +   +   +   +---+   + A +
|   | 3   1   0               2 |   B   C
+   +---+   +   +   +   +   +   +---+ D +
|       |                           E   F
+   +   +   +   +   +   +   +   +---+   +
          1           0         | 2     |
+   +   +   +   +   +   +---+---+   +   +
      3   3       1   2 | 2       0   2 |
+   +   +   +   +---+---+   +---+   +---+
          1           2     |   | 3 |
+   +   +   +   +---+---+---+   +---+   +

Unknown edges in the right region are marked by letters: A,B,C,D,E,F.

Border line coming to "A" and "C" edges can be extended in 2 ways only - by "A" or by "C" edges. Extension by "A" edge should be prohibited, because it will break Slitherlink rules - solid edge "A" must be followed by solid edge "B", and the line will be closed too early. So, we must extend border line by "C" edge.

"D" edge closes the line, so border line must be extended further by "F" edge only. The only next step in this region is selection of "E" edge as solid.

Now we can say "stte", as Sudoku playes do.

Serg

[denis_berthier]

Hi, Denis!
I solve Slitherlink puzzles regularly, so I am interested in powerful Slitherlink solving techniques. But unfortunately I understood nothing from your definitions. Maybe you should give more examples (with pictures).

You choosed bad example for your techniques demonstration - the puzzle is very simple and can be easily solved by basic techniques. For example, let's consider intermediate position you published.

Code: Select all

+   +---+   +   +---+---+---+---+---+---+
    | 3 |       | 2           2         |
+---+   +---+---+   +   +---+---+---+   +
| 3   0       2   0   2 |     1   2 |   |
+---+   +---+---+   +---+   +   +   +   +
    | 3 |       | 3 |         0     |   |
+   +---+   +   +---+   +   +   +---+   +
                                |       |
+---+---+---+   +   +   +   +---+   +   +
|         3 |             1 | 3   0     |
+   +---+---+   +   +   +   +---+   + A +
|   | 3   1   0               2 |   B   C
+   +---+   +   +   +   +   +   +---+ D +
|       |                           E   F
+   +   +   +   +   +   +   +   +---+   +
          1           0         | 2     |
+   +   +   +   +   +   +---+---+   +   +
      3   3       1   2 | 2       0   2 |
+   +   +   +   +---+---+   +---+   +---+
          1           2     |   | 3 |
+   +   +   +   +---+---+---+   +---+   +

Unknown edges in the right region are marked by letters: A,B,C,D,E,F.

Border line coming to "A" and "C" edges can be extended in 2 ways only - by "A" or by "C" edges. Extension by "A" edge should be prohibited, because it will break Slitherlink rules - solid edge "A" must be followed by solid edge "B", and the line will be closed too early. So, we must extend border line by "C" edge.

"D" edge closes the line, so border line must be extended further by "F" edge only. The only next step in this region is selection of "E" edge as solid.

Now we can say "stte", as Sudoku playes do.

Serg

Hi Serg,
Your graphic is ambiguous, as undecided and False lines are represented the same way.
But, supposing you're indeed speaking of the same final state as I mentioned before the Extended-Loops, you're absolutely right, and that's exactly how I finished this puzzle manually before I had the Extended Loops (I even put this example in the CSP-Rules/Examples folder). That's what's generally called T&E. Extended-Loops are designed to avoid it for more puzzles (not for all the puzzles, as this is impossible).

However, if you want more examples, see the same folder in CSP-Rules. Some examples completely change the resolution path.

[Serg]

Hi, Denis!

... that's exactly how I finished this puzzle manually before I had the Extended Loops ... That's what's generally called T&E. Extended-Loops are designed to avoid it for more puzzles ...

Amazing. Simple choice between 2 evident variants (which is simpler than multiplying 2 by 2) is awful T&E. To prevent use shameful T&E one should use much more complicated ABCD-chains. Nice! But just a moment - the most popular method of proving something in mathematics is following one. "Suppose statement A is true. It will lead us to contradiction. Then statement A is false." This is pure T&E method! All time mathematicians proved almost all known theorems by T&E method! It looks like they all were stupids because they didn't use more intelligent proofs.

Serg

[denis_berthier]

Hi, Denis!

... that's exactly how I finished this puzzle manually before I had the Extended Loops ... That's what's generally called T&E. Extended-Loops are designed to avoid it for more puzzles ...

Amazing. Simple choice between 2 evident variants (which is simpler than multiplying 2 by 2) is awful T&E. To prevent use shameful T&E one should use much more complicated ABCD-chains. Nice! But just a moment - the most popular method of proving something in mathematics is following one. "Suppose statement A is true. It will lead us to contradiction. Then statement A is false." This is pure T&E method! All time mathematicians proved almost all known theorems by T&E method! It looks like they all were stupids because they didn't use more intelligent proofs.

Serg

If you don't like this example, check the more complex ones, you will see how extended-loops do extend the resolution power of loops. I chose this example because it allows to see clearly the various patterns.
The whole approach of pattern-based solving is intended to avoid T&E and to use instead predefined patterns.

Proof by contradiction is NOT the most popular method in maths. We use proof by contradiction only when a direct proof is not available.

[Mathimagics]

Proof by contradiction is NOT the most popular method in maths. We use proof by contradiction only when a direct proof is not available.

G. H. Hardy described proof by contradiction as "one of a mathematician's finest weapons", saying "It is a far finer gambit than any chess gambit: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game."

My friend Serg might have gilded the lily somewhat, regarding the alleged proportion of theorems proved by contradiction ...

Nevertheless, I tend to agree with Hardy ...

[denis_berthier]

Proof by contradiction is NOT the most popular method in maths. We use proof by contradiction only when a direct proof is not available.

G. H. Hardy described proof by contradiction as "one of a mathematician's finest weapons", saying "It is a far finer gambit than any chess gambit: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game."

My friend Serg might have gilded the lily somewhat, regarding the alleged proportion of theorems proved by contradiction ...

Nevertheless, I tend to agree with Hardy ...

No one says that proof by contradiction is not powerful. However, it's considered inelegant when a direct proof is available.

And this is far from the question. In Sudoku, solving with a predefined pattern is not the same thing as using an ad hoc proof by contradiction.

[denis_berthier]

The quasi-loops I introduced in [PBCS2] are very simple, easy to find patterns. Their extended version is almost as simple and easy to find, because isolated-HV-chains are almost as visible as loops.

Here is one more example.

Consider the following puzzle (Mellon I.6):

Code: Select all

. . . 0 . 3 . . 0 .
0 . . . . 0 . 2 . .
. . 0 . 2 . . 0 . .
. 2 . . 0 . . . . 0
. 0 . . . . 0 . . .
. . . 0 . . . . 0 .
0 . . . . 0 . . 3 .
. . 0 . . 1 . 0 . .
. . 1 . 0 . . . . 0
. 0 . . 2 . 0 . . .


Using all the rules in CSP-Rules except extended-loops, no ordinary loop can be applied and we reach the following final state:

Code: Select all

.   .   .   .   .   .———.   .   .   .   .
              0     | 3 |         0
.   .   .   .   .———.   .———.———.   .   .
  0             |     0       2 |
.   .   .   .   .———.   .   .   .———.   .
          0       2 |         0     |
.———.———.   .   .   .———.   .   .———.   .
|     2 |         0     |       |     0
.   .   .———.....   .———.   .   .———.   .
|     0     :   :   |     0         |
.———.   .....   .....   .   .   .   .———.
    |   :     0     :             0     |
.   .———.....   .....   .   .———.   .———.
  0         :   :     0     |   | 3 |
.   .   .   .....   .   .———.   .———.   .
          0     |     1 |     0
.   .   .   .———.   .   .   .   .   .   .
          1 |     0     |             0
.   .   .   .   .   .———.   .   .   .   .
      0     |     2 |     0
.   .   .   .———.———.   .   .   .   .   .


There are four obvious isolated-HV-chains, all of length 3.
And there are two partial loops, one of length 9+3 and one of length 40+3. Each of them can be completed by one of the above isolated-HV-chains, making an extended-loop.
Applying any of the two leads to the solution.

[Serg]

Hi, Denis!

The quasi-loops I introduced in [PBCS2] are very simple, easy to find patterns. Their extended version is almost as simple and easy to find, because isolated-HV-chains are almost as visible as loops.

Here is one more example.

Consider the following puzzle (Mellon I.6):

Code: Select all

. . . 0 . 3 . . 0 .
0 . . . . 0 . 2 . .
. . 0 . 2 . . 0 . .
. 2 . . 0 . . . . 0
. 0 . . . . 0 . . .
. . . 0 . . . . 0 .
0 . . . . 0 . . 3 .
. . 0 . . 1 . 0 . .
. . 1 . 0 . . . . 0
. 0 . . 2 . 0 . . .


Using all the rules in CSP-Rules except extended-loops, no ordinary loop can be applied and we reach the following final state:

Code: Select all

.   .   .   .   .   .———.   .   .   .   .
              0     | 3 |         0
.   .   .   .   .———.   .———.———.   .   .
  0             |     0       2 |
.   .   .   .   .———.   .   .   .———.   .
          0       2 |         0     |
.———.———.   .   .   .———.   .   .———.   .
|     2 |         0     |       |     0
.   .   .———.....   .———.   .   .———.   .
|     0     :   :   |     0         |
.———.   .....   .....   .   .   .   .———.
    |   :     0     :             0     |
.   .———.....   .....   .   .———.   .———.
  0         :   :     0     |   | 3 |
.   .   .   .....   .   .———.   .———.   .
          0     |     1 |     0
.   .   .   .———.   .   .   .   .   .   .
          1 |     0     |             0
.   .   .   .   .   .———.   .   .   .   .
      0     |     2 |     0
.   .   .   .———.———.   .   .   .   .   .


There are four obvious isolated-HV-chains, all of length 3.
And there are two partial loops, one of length 9+3 and one of length 40+3. Each of them can be completed by one of the above isolated-HV-chains, making an extended-loop.
Applying any of the two leads to the solution.

This example is even simpler than your previous one and can be solved without any loops. In fact, you published counterexamples, illustrating useless of your quasi-loops.

Serg

[denis_berthier]

This example is even simpler than your previous one and can be solved without any loops. In fact, you published counterexamples, illustrating useless of your quasi-loops.
Serg

Well, what simpler rules do you apply in this situation?

[Serg]

Hi, Denis!

This example is even simpler than your previous one and can be solved without any loops. In fact, you published counterexamples, illustrating useless of your quasi-loops.
Serg

Well, what simpler rules do you apply in this situation?

Let's consider top end of the left unclosed loop in your example. Two ways from this vertex are permitted only - Hr5c4 and Vr4c5 (hope, I used your notation correctly). The way by Vr4c5 closes left loop, so this way is prohibited. The only remaining way - by Hr5c4 solves the puzzle.

Serg

[denis_berthier]

Hi, Denis!

This example is even simpler than your previous one and can be solved without any loops. In fact, you published counterexamples, illustrating useless of your quasi-loops.
Serg

Well, what simpler rules do you apply in this situation?

Let's consider top end of the left unclosed loop in your example. Two ways from this vertex are permitted only - Hr5c4 and Vr4c5 (hope, I used your notation correctly). The way by Vr4c5 closes left loop, so this way is prohibited. The only remaining way - by Hr5c4 solves the puzzle.

Serg

"The way by Vr4c5 closes left loop," : that's exactly what the Extended-Loop does. The only difference with you is, it identifies the 3 undecided lines as a single pattern - a clearly visible one and this dispenses me of your final short round of T&E

Edit for more detail:
. either one has to test the hypothesis (T&E) that Vr4c5 is TRUE, apply a short series of singles and conclude that he finds a too short closed loop (your T&E approach)
- or one recognises an isolated-HV-chain[3] as standalone pattern that would close the existing partial-loop and that can therefore be eiiminated in a single shot by the (obvious) extended-loop rule.