The New Sudoku Players' Forum

[denis_berthier]

Examples of solutions

Note: the original version of this post has been drastically changed, after Serg found several errors in my incomplete manual analyses (see his next posts). This adventure showed me that one must really be careful not to discard too quickly any possibility!

Earlier in this thread, I mentioned http://www.janko.at/Raetsel/Slitherlink/ as an interesting source of puzzles.

Here are three examples taken from it.




****************************** #19 (corrected) ******************************

Code: Select all

OO--X
-----
-----
X---O
-X-XO

In this example, constraints propagation doesn't give much:

Code: Select all

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

Consider in turn the two possibilities for Vr1c5:

A) Vr1c5 = 0

Code: Select all

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

There are now two sub-possibilites:

Aa) Hr4c3 = 0

Code: Select all

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

Again, two sub-possibilities:

Aa1) Hr4c4 = 1

Code: Select all

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

=> open end

Aa2) Hr4c4 = 0

Code: Select all

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


Two sub-possibilities

Aa2-1) Vr5c4 = 1

Code: Select all

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

=> small loop

Aa2-2) Vr5c4=0

Code: Select all

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

=> open end


Partial conclusion: Aa is impossible


Ab) Hr4c3 = 1

Code: Select all

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


2 in r4c4 and 3 in r5c4 => contradiction


Partial conclusion: Vr1c5 = 0 is impossible


B) Vr1c5 = 1

Code: Select all

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


two sub-possibilities

Ba) Vr4c4 = 1

Code: Select all

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


=> open end


Bb) Vr4c4 = 0

Code: Select all

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

Solution

I don't know if there is a simpler way of proving that there is only one solution in this case, but this T&E way is rather unsatisfactory to me.





****************************** #17 (corrected) ******************************

Code: Select all

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

Easy constraints propagation leads to:

Code: Select all

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


Consider in turn each possibility for Vr3c3.

A) Vr5c3 = 1 :

Code: Select all

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


there are now two sub-possibilities:

Aa) Hr4c2 = 1

Code: Select all

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


=> small loop

or
Ab) Hr4c2 = 0

Code: Select all

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


=> small loop


B) Vr5c3 = 0:

Code: Select all

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

Again, there are two sub-possibilities

Ba) Vr4c3 = 1

Code: Select all

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

=> small loop


Bb) Vr4c3 = 0

Code: Select all

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

Solution





****************************** #14, an interesting puzzle suggesting new rules ******************************


This example suggests new rules. (I haven't seen such rules mentioned anywhere, but the web is large!)

Code: Select all

. 2 . . .
2 3 . . .
. . . 2 .
2 2 . . 3
. 3 . . 3

Whatever values for the rest of the puzzle, nothing could allow to choose between the following two possibilities for the nw corner

Code: Select all

.———.———.———.........
|     2     :   :   :
.———.———.   .........
  2   3 |       :   :
.———.———.   .———.....
|           | 2     |
.............   .———.
: 2 : 2 :   :   | 3 
.............   .———.
:   : 3 :   :     3 |
.............———.———.


.———.   .———.........
|   | 2 |   :   :   :
.   .   .   ........
| 2 | 3 |       :   :
.   .———.   .———.....
|           | 2     |
.............   .———.
: 2 : 2 :   :   | 3 
.............   .———.
:   : 3 :   :     3 |
.............———.———.

This is a general property for any puzzle with the following pattern in the nw corner

Code: Select all

. 2
2 3

or similar patterns in the other corners. They are potential non-uniqueness patterns.

However, as found by Serg, there is a possibility to include this pattern in a solution.
As a result, we have a uniqueness rule:

When pattern

Code: Select all

. 2
2 3

is present at the nw corner
then the only possibility for excluding multiple solutions is to have:

Code: Select all

.———.———.
|     2
.   .———.
| 2 | 3 :
.   .....


This puzzles also suggests a special corner rule.
(At first, I thought there was a contradiction in the corner pattern, but Serg found a solution)

When the following pattern is present at the sw corner

Code: Select all

2 2
. 3

then the solution must contain all the following borders:

Code: Select all

|
.———.   .     
  2 | 2 |
.   .   .
    | 3 |   
    .———.

Of course, there is a similar rule for pattern

Code: Select all

3 2
. 2

in the same corner
and for similar patterns in the other corners.


If you are not interested in the details of Serg's remarks that led me to correct this post, you can jump to further examples here: http://forum.enjoysudoku.com/solving-slitherlink-puzzles-t31264-21.html

[Serg]

Hi, denis_berthier!
. . .
<Deleted wrong solving path description by denis_berthier>
. . .
Maybe I missed something ...
Isn't it a solution of puzzle#17?

Code: Select all

    +---+---+---+
  1 |           | 1
    +   +---+---+
    | 2 |
    +   +---+---+
    | 2       2 |
    +---+---+   +
      2   3 |   |
    +---+---+   +
    | 3         | 1
    +---+---+---+


If I am not mistaken, this solution is unique.

Serg

[Serg]

Hi, denis_berthier!
. . .
<Deleted wrong solving path description for puzzle#14 by denis_berthier>
. . .
You are right, both published possibilities of nw corner are indistinguishable. But both these variants are wrong, because they conflict with the rest of puzzle. This is solution of puzzle#14:

Code: Select all

+---+---+---+---+---+
|     2             |
+   +---+---+---+   +
| 2 | 3         |   |
+   +---+   +---+   +
|       |   | 2     |
+---+   +   +   +---+
  2 | 2 |   |   | 3
    +   +   +   +---+
    | 3 |   |     3 |
    +---+   +---+---+


As fas as I understand, this is correct unique solution of this puzzle. It seems to me you are too fast stating that cited site is unreliable. Nevertheless, thanks for introduction to Slitherlink - interesting (new to me) kind of puzzles.

Serg

[denis_berthier]

It seems to me you are too fast stating that cited site is unreliable.

Hi Serg,

Thanks a lot for your comments. I've corrected and extended my post accordingly.
I think the multiple solution example still holds (did you check it also?).
I've also revised my evaluation of that website (to "interesting but not fully reliable").

BTW, your notation with a "+" instead of a "." at the corners seems to be a good idea.

Nevertheless, thanks for introduction to Slitherlink - interesting (new to me) kind of puzzles.

I came to be interested in it via Saul's questions in the Kakuro thread. As you can see, I'm not very experimented in dealing with it.
In my approach, based on binary (local) constraints and implemented in CSP-Rules, Kakuro was a challenge due to its non-binary arithmetic constraints (I could finally replace them, in an efficient way, by binary ones).
With its global constraints, Slitherlink is another type of challenge. As of now, I deal with these manually after applying all the available whips. Unfortunately, as you can see from my above proofs, having to consider alternative possibilities (sometimes at several levels of embedding) is not very satisfactory (in addition to being error-prone). In various examples I've not reported here, "small" loops can be very long and I haven't yet found any pattern-based way of eliminating them early in resolution.

[Serg]

Hi, Denis!
I am afraid you've missed smth in puzzle#19 solving path. (I cannot follow your solution path.)
. . .
<Deleted wrong solving path description for puzzle#19 by Denis>
. . .
I've found solution for this puzzle

Code: Select all

                +---+
      1       1 | 3 |
+---+---+---+   +   +
|         2 |   |   |
+   +---+   +---+   +
|   | 3 |           |
+   +   +---+---+---+
|   |         2   1
+   +---+---+---+
| 2           3 | 1
+---+---+---+---+


I analysed it (manually) and didn't find additional solutions. So, I think it is unique.

Serg

[denis_berthier]

Thanks, Serg,

Finally, my three manual analyses had errors (I had skipped possible cases). Bad day!
In this example #19, my first "simple one-loop argument", immediately after the constraints propagation done by CSP-Rules (which I checked is not concerned by my manual errors), missed a possibility and introduced an erroneous border for r4c4.

I've corrected my original post (I've finally posted a full solution for this example).
I've also posted the correct solution for #17.

Of course, I'm not really satisfied by having to consider so many different possibilities before finding the solution.

[denis_berthier]

Trying Sample puzzles from Nicoli


There are very few available puzzles on the Nicoli website if you don't pay for membership. Here, I'll deal with only one, Sample #3, by Yuoichi Saito (all are of the same kind and level).

Code: Select all

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

Constraint propagation leads to

Code: Select all

OXOXOXOOXX
XXXXXXOOOX
OXOXOX--XX
OOOOOX----
OOXOXXOO--
XOXXXOOXXX
XXXOOOOOXO
OOXXXOOXXX
XOOXOOOOOX
XXXXXOXXXX


Code: Select all

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


which is very close to a solution.

Hr6c9 = 1 would lead to a small loop (se corner):

Code: Select all

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



Therefore Hr6c9 = 0:

Code: Select all

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


Vr4c9 = 1 would lead to a small loop (east side):

Code: Select all

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



therefore Vr4c9=0:

Code: Select all

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


This is a solution and the proof shows it is unique.


Contrary to the Raetsel puzzles, once the local constraints have been propagated, it was easy to find the solution: only few possibilities leading to obvious small loops had to be discarded.
(The other available Nikoli samples work similarly).


This suggests that there are various kinds of puzzles, depending on the role played by the global only-one-loop constraint (and/or the in/out arguments in my first posts). Probably, different players will like different kinds.
Local constraints propagation may quickly become boring.
Only-one-loop arguments, if requiring several levels of hypotheses or long local propagation of constraints before a partial loop can be detected, may also quickly become very boring (this is what I felt with my T&E-ish solution to Raetsel #19)

[Serg]

Hi, Denis!
Please, correct a typo in your post, describing solution of puzzle#17 (a typo in final solution).

Here is another free site with Slitherlink and some other kinds of puzzles: http://www.puzzle-loop.com/.
I've found nice 5 x 5 "hard" puzzle on this site:

Code: Select all

+   +   +   +   +   +
      1           3 
+   +   +   +   +   +
          3   2   2 
+   +   +   +   +   +
  3   0   2       2 
+   +   +   +   +   +
              2   3 
+   +   +   +   +   +
  3               3 
+   +   +   +   +   +

To my mind this puzzle is really hard (but it looks like simple). I solved it from 5-th or 6-th attempt only.

Serg

[denis_berthier]

Hi Serg,

Please, correct a typo in your post, describing solution of puzzle#17 (a typo in final solution).

Thanks for noticing. I've corrected.

Here is another free site with Slitherlink and some other kinds of puzzles: http://www.puzzle-loop.com/.
I've found nice 5 x 5 "hard" puzzle on this site:

Code: Select all

+   +   +   +   +   +
      1           3 
+   +   +   +   +   +
          3   2   2 
+   +   +   +   +   +
  3   0   2       2 
+   +   +   +   +   +
              2   3 
+   +   +   +   +   +
  3               3 
+   +   +   +   +   +

To my mind this puzzle is really hard (but it looks like simple). I solved it from 5-th or 6-th attempt only.

It's good to have more references.
I've tried this puzzle: it can be completely solved by the techniques in CSP-Rules, i.e. by local constraints propagation (no use of the only-one-loop constraint)

Code: Select all

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


[denis_berthier]

Hi Serg,

I've tried several "hard" puzzles from the site you've found yesterday (puzzle-loop.com): 5 of size 5x5 and 25 of size 7x7.

The hardest I've found is #5,451,296 ( I don't know how they name their puzzles; it suggests they have a huge number of them).

Code: Select all

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

"Hardest" should be understood with the same warnings as always, i.e. wrt to my resolution approach. In the present case, it means that I have to apply several only-one-loop arguments in addition to local constraints propagation.

Serg (or anyone else), if you try it, I'd like to have your opinion on difficulty.

[Serg]

Hi, Denis!

Code: Select all

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

Serg (or anyone else), if you try it, I'd like to have your opinion on difficulty.

I've tried to solve this puzzle. But it is too difficult for me. I could not solve it in reasonable time. It seems to me it can be solved with T&E (global) method only. I cannot see more smart solution methods for it yet. I'll try to solve it again next week (on vacations).

Serg

[denis_berthier]

I've tried to solve this puzzle. But it is too difficult for me. I could not solve it in reasonable time. It seems to me it can be solved with T&E (global) method only. I cannot see more smart solution methods for it yet. I'll try to solve it again next week (on vacations).

At least, you can be sure it has a unique solution (err, if I haven't missed any).

[denis_berthier]

[Deleted]

[Serg]

< withdrown >

[denis_berthier]

[deleted]