The New Sudoku Players' Forum

[denis_berthier]

Using global inside/outside constraints


The global one-loop constraint is equivalent to two global constraints:
- a one-connected-inside constraint
- a one-connected-outside constraint (outside including the non-displayed space around the grid)
and none of the two can be reduced to the other, as illustrated by the following examples.

Having the inside/outside position of all the cells is obviously equivalent to having all the borders.
As a result, it is convenient to print the solution in inside/outside form ("O" for outside the curve, "X" for inside, "—" for undecided in case only a partial solution is obtained).


Here are three examples from the Krazydad Easy book b001, where I need no global constraint to reach a partial solution. (Recall that, in my approach, a partial solution can only have properties common to all the solutions.)
I'll also show how the puzzle can then easily be finished by using the inside or outside global constraints.


Example 1: puzzle #7:

Code: Select all

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

partial solution:

OOOXOXO
OOXXXXX
OXXO-OO
XXOO-XO
OXXOOXX
XXOOOXO
OXXXOXX


Notice that all the Os are connected and the one-connected-outside constraint is thus already satisfied.
Let's now use the global one-connected-inside constraint : by colouring in green or red the connected parts inside the loop (the Xs), it is obvious that the only means of satisfying the global one-loop (or global one-connected-inside) constraint is to have r3c5 and r4c5 inside.
This shows that the one-connected-inside constraint is not reducible to the one-connected-outside constraint when they are taken to replace the one-loop constraint (this is obvious as a connected outside might not be singly connected if there are two closed curves).

OOOXOXO
OOXXXXX
OXXO—OO
XXOO—XO
OXXOOXX
XXOOOXO
OXXXOXX


Example 2, puzzle #2:

Code: Select all

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

partial solution:

XXXXXXX
XOOXOOX
OOXXXO—
XOOXOOX
XOXXXXX
XXXXOOX
XXOXXOX


Here, all the X's are already connected, and the one-connected-inside constraint is thus already satisfied
But the only means of connecting the Os is to have r3c7 outside the loop.
This shows that the one-connected-outside constraint is not reducible to the one-connected-inside constraint when they are taken to replace the one-loop constraint (this is obvious as a connected inside might not be singly connected if there are two closed curves).


Example 3 (an example of the same kind as above), puzzle #4:

Code: Select all

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

partial solution:

OXX—XOX
XXOOXXX
XOOXXOO
XXOXOOX
OXXXOXX
XXOXXXX
XXOXOXO


Again, all the X's are already connected, and the one-connected-inside constraint is thus already satisfied.
But the only means of connecting the Os is to have r1c4 outside the loop.



Exercise, # 6 of the same Karzydad "book":

Code: Select all

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


Using only local constraints, show that one can obtain the following situation:

Code: Select all

XXXXO—X
OXOX———
OOOOO——
XXOXOO—
—OOXXOX
—XOXOOX
OXXXXXX


Now using the only-one-inside constraint, show that one must have:

Code: Select all

XXXXO-X
OXOXXX-
OOOOO-X
XXOXOOX
XOOXXOX
XXOXOOX
OXXXXXX


The final three cells are easily dealt with using the givens and the global constraints:
r3c5 = 1 => r3c6 can only be O
r1c5 = 2 => r1c6 can only be O
Finally, connexity of the Xs requires r2c7 = X

[saul]

Denis,

I have to apologize for not acknowledging this post earlier. I didn't get Jason's notification, or more likely, I accidentally deleted it while cleaning up my inbox. I just saw this when I came to look up an old post.

I don't want to get started reading it now, because it's already midnight here, and by the looks of it, if I get started on it, I'll be up till all hours. I look forward to reading this very much.

[denis_berthier]

I have to apologize for not acknowledging this post earlier. I didn't get Jason's notification, or more likely, I accidentally deleted it while cleaning up my inbox. I just saw this when I came to look up an old post.

Hi Saul,

Don't worry. Here, we've had (and still have) a scorching heat and my brain turned into yoghurt. I can't imagine which damages anything slithering inside could do.
Later, I'll post harder examples.

[saul]

Denis,

I'm just starting to look at your posts on slitherlink closely, and I have a number of questions.

1. You say, "The best place I've found for a list of "standard" Slitherlink resolution rules is wikipedia. But Mebane is also OK." What is Mebane? I googled it, but didn't come up with anything that seemed relevant. If it's a typo, I can't guess what it ought to be.

2. I want to confirm that I understand your terminology. You are constructing a graph with one vertex for each cell of the grid, and one vertex for the region outside the grid. The cells are considered adjacent as vertices if they are orthogonally adjacent. The outside region is adjacent to all of the cells on the border. Correct?

3. In example 3, you say, "But the only means of connecting the Os is to have r1c4 inside the loop." Should this be "outside the loop?"

I haven't tried the exercise yet. It seems straightforward to do with a pencil, but I'll have to think more about the computer algorithm. Obviously, you start by finding the connected components of the subgraph induced by the X's. Color them different colors for convenience. Then an unknown vertex must be an X if every path from the red component to the blue component, say, must pass through that vertex. I have to think about how to find such vertices efficiently.

I'm having trouble keeping the two views of the puzzle in mind, though. There used to be a site with a daily slitherlink puzzle that automatically colored the inside and the outside as you worked the puzzle; that is, cells inside and outside the curve were colored differently. I need something like that. The inside-outside notation is very convenient for an email, I must say; this is a good idea.

[Pat]

1. You say, "---But Mebane is also OK."
What is Mebane?

Palmer Mebane

[denis_berthier]

Hi Saul,

2. The cells are considered adjacent as vertices if they are orthogonally adjacent. The outside region is adjacent to all of the cells on the border. Correct?

Yes. Cells can only be adjacent horizontally or vertically (i.e. not diagonally). Said otherwise, a border must have positive length.

To be more precise about the above examples: by applying local constraint propagation rules (whips), CSP-Rules produces some resolution state (displayed above in the inside/outside format). As of now, I finish the puzzles manually, using the ideas in my previous post.
For puzzles harder than those in that post, some iteration is required, giving this pattern of proof: (whips | only-one-loop argument)*.

3. In example 3, you say, "But the only means of connecting the Os is to have r1c4 inside the loop." Should this be "outside the loop?"

Yes. Thanks. I've corrected my post.

The inside-outside notation is very convenient for an email, I must say; this is a good idea.

It is an old theorem that a continuous closed curve with no self-intersection separates the plane into two disjoint parts: a compact one (call it the inside) and an unbounded one (call it the outside).
It's useful, but not always enough to solve a puzzle. See my forthcoming examples.

[denis_berthier]

Notation and graphical representations for Slitherlink puzzles.


In one of my previous posts, I've introduced the compact in/out representation of the solution (or a partial solution).

As far as I can see from the examples I've tried, in most cases, in/out arguments (combined with elementary constraints propagation, Singles and whips) are not enough to deal with the global one-loop constraint: one needs to consider the borders between cells.
Indeed, some borders may be decided without leading to deciding the in/out status of a cell and reducing the information content of the current resolution state to the latter would clearly be a loss of information.

Using borders supposes notations and some graphical means of representing them.

Notation:
- cells are named ricj, with i from 1 to #rows and j from 1 to #columns;
- horizontal borders are named Hricj, with i from 1 to #rows+1 and j from 1 to #columns;
- vertical borders are named Vricj, with i from 1 to #rows and j from 1 to #columns+1.

Graphical representation:
- a corner of a cell (or a "point") is represented by a dot;
- a border with decided TRUE (or 1) value is represented by a continuous line between the corresponding two corners (horizontally 3 times alt-, vertically |);
- a border with decided FALSE (or 0) value is represented by 1 (vertical) or 3 (horizontal) spaces between the corresponding two corners;
- a border with undecided value is represented by a semicolon (vertically) or 3 (non-fused) dots (horizontally) between the corresponding two corners;
- givens are copied inside the cells.
This is the best means I've found for having a reasonably portable output format. If anyone has a better proposal, I'm totally open to adopting it.

See my next posts for examples.

[denis_berthier]

An example using borders and harder only-one-loop arguments

Consider puzzle #3 in Mebane's pack:

Code: Select all

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


Using ECP, Singles and whips[1], one can easily reach the following resolution state (I give the two representations):

Code: Select all

in/out representation:

OXX----XOO
OOX----XXO
OXXO--OOXX
XXOOXXXO--
OXOXXOX---
OOOOOOX--- ; -X-
OXXXOXXO-O ; X
OOOXXXOOXO
OXOXXXOXXO
XXXXXOOOOO


Using in/our arguments as before, one could add the X shown after the semicolons. But (unless I'm missing something), it doesn't seem to be enough to deal with the rest of the puzzle. Anyway, even if it was possible, my purpose is only illustrative and this wouldn't change what follows.

Code: Select all

representation with borders (one can check that it provides more information than mere in/out):

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


From this representation, one can easily see that if Hr2c4 was 1, there would be a local loop around (r1c2 r1c3 r1c4 r2c3 r3c2 r3c3 r4c1 r4c2 r5c2).
Now, setting Hr2c4 to 0 easily leads to the following solution.

Code: Select all

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




It can now be rewritten in compact in/out form:

Code: Select all

OXXOXXXXOO
OOXXXOOXXO
OXXOOOOOXX
XXOOXXXOXO
OXOXXOXXXX
OOOOOOXXXO
OXXXOXXOXO
OOOXXXOOXO
OXOXXXOXXO
XXXXXOOOOO


[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)