The New Sudoku Players' Forum

[denis_berthier]

[Denis, I was interested in your remarks, in your previous post, on applying your techniques to non-binary puzzles. Have you tried slither link? If each edge is represented by a boolean variable, the constraints given by the numbers would be quaternary. Also, for the edges meeting at a vertex, either two or zero of them must be 1, so we can say that the sum is less than 3 and not equal to one. In general, these would be quaternary constraints, but at the edges of the board they would be ternary, and binary at the corners.
The complication is the requirement that the solution consists of a single loop; the constraints above only ensure that we get a union of disjoint loops. It seems that you would have to generate all solutions and then reject the ones with multiple loops, but there are lots of incorrect solutions. For any cell not adjacent to a number, and not adjacent to the correct solution, we could add all its edges and satisfy the constraints. You would probably want to add a constraint for each cell to avoid this. But what about rectangles consisting of two cells? This would take some experimentation with actual puzzles.
Of course, this is "generate and test," and rather than finding all solutions, one would like to test the partial solutions to check that no loop had been created. I don't know if that fits into the CSP paradigm at all.
Would your techniques apply to slither link, do your think?

HI Saul,
Are you still interested in Slitherlink ?
I've recently had a look at it and I checked that my techniques work well.
Of course, for puzzles whose uniqueness can only be proven with the "one global loop" constraint, I need specific Jordan-Curve rules. But much can be done using only whips.

[saul]

I think slitherlink is a great puzzle, but I haven't played it in a long time, partly because I don't know a good source of puzzles on the Web.

What you say is very interesting. As I recall solving the puzzles, you use the one-loop constraint a lot, because it is often possible to find a small loop that satisfies the conditions on the cells it surrounds. I see that there may well be other constraints such a loop violates, though. In my limited experience, it's unusual to get to the end of the puzzle and find a second solution that uses two curves, but I've certainly run across this. In those situations, I've been applying the one-loop constraint all along, though. I think I would have guessed that absent the one-loop con constraint, there are typically several solutions. I gather from what you say that this is not so.

Do I understand correctly that your approach is to find all solutions, without regard to the one-loop constraint, and then discard all the ones that don't meet this requirement, or are you winnowing them out as you go? If the latter, how do you go about it? When I was thinking about writing slitherlink solver, and I never got past the idle speculation stage, I was considering keeping track of the connected components of the curve with union-find, and when a component was closed into a loop (easy to spot since two points of degree one have just been joined) checking to see if it was, in fact, a solution. This should be easy in most cases, because if there are any other components, the answer is "no". It's only when we've just constructed the only loop that we have to actually look at the individual numerical constraints. Are you doing anything resembling that, by chance?

[denis_berthier]

I think I would have guessed that absent the one-loop con constraint, there are typically several solutions. I gather from what you say that this is not so.

It depends on the puzzles. In most of the easy puzzles I've seen, I need no global one-loop constraint.

Do I understand correctly that your approach is to find all solutions, without regard to the one-loop constraint, and then discard all the ones that don't meet this requirement?

No, I can only find properties common to all the solutions.
I merely propagate all the local constraints, using whips. It doesn't solve all the puzzles : the one-loop constraint is built into most of them (but the easy ones) in such a way that you can't avoid using it at some point.

I was considering keeping track of the connected components of the curve with union-find, and when a component was closed into a loop (easy to spot since two points of degree one have just been joined) checking to see if it was, in fact, a solution. [...] Are you doing anything resembling that, by chance?

No, not at all.
I'll have to write the details of my approach, but it will take some time.

[denis_berthier]

I think slitherlink is a great puzzle, but I haven't played it in a long time, partly because I don't know a good source of puzzles on the Web.

It seems that, as for Kakuro, there's no Slitherlink discussion forum.

As for the sources of puzzles, I've used these:

- http://krazydad.com/slitherlink/ ; they have uncountably many Slitherlink puzzles of various sizes, classified into 3 levels (easy, intermediate, tough), but, as in the Kakuro case, I can't see any difference between the 3 ; I think the reason is, they generate them with Tatham software, which seems to be strongly biased towards easy puzzles ;

- http://www.janko.at/Raetsel/Slitherlink/ ; an interesting site ;

- http://mellowmelon.files.wordpress.com/2012/01/pack01slitherlinkv3.pdf, by Palmer Mebane ; when I wrote "Pattern-Based Constraint Satisfaction", I was very interested by their Hidato puzzles (they had only few, but the hardest I could find).

Have you tried these sources ? Otherwise, do you know better ones ?

I've opened a Slitherlink thread http://forum.enjoysudoku.com/solving-slitherlink-puzzles-t31264.html and asked Jason to move this discussion there, so that we don't mix up all the puzzles.
The Slitherlink posts have been moved to the new topic. JasonLion


[Edit: corrected Krazydad's source: Tatham]

[saul]

Thanks for the sources on slitherlink. I've only had time to glance at them. I don't have any sites to recommend myself. I tried one of the puzzles at http://www.nikoli.com/en/puzzles/slitherlink/ yesterday afetr reading your post. It was a good puzzle, but unfortunately the site just has a few sample puzzles. I learned that I have forgotten almost everything I ever knew about slitherlink, so I was glad to see that one of your sites included a introduction with all the rules about adjacent 3's and so on. In the regard, I was interested to see Krazy Dad's puzzles with different topologies, since that means that you would have to discover news rules in order to play them. (Of course, I imagine that with a constraint-based solver, this is entirely irrelevant. You just have to describe the new constraints. The nice AI problem is to automatically derive human-usable rules.)

[denis_berthier]

I was interested to see Krazy Dad's puzzles with different topologies, since that means that you would have to discover news rules in order to play them.

I imagine such rules would mainly be topology-adapted variants of the standard rules.

Of course, I imagine that with a constraint-based solver, this is entirely irrelevant. You just have to describe the new constraints.

Sure, that's the raison d'être of a general purpose constraint based solver.
If you were thinking of CSP-Rules in particular, this remains true even though it isn't a constraint based solver in the standard sense. It is a pattern-based constraint solver - patterns being Subsets, Bivalue-Chains, Whips, g-Whips, ... - which means that it provides meaningful resolution paths. In addition, it provides the simplest solution.

The nice AI problem is to automatically derive human-usable rules.

Mmmm, not before you can formally define "human-usable".
BTW, many of the known Slitherlink rules can be reduced to combinations of simpler ones, which are instances of short whips. For this reason, I think topological variants are amenable to the same treatment as standard puzzles.

[denis_berthier]

Reduction of "standard" rules

Finally, the best place I've found for a list of "standard" Slitherlink resolution rules is wikipedia. But Mebane is also OK.

Unfortunately for the interest of this game, I confirm what I said above : most of the resolution rules mentioned there are obviously reducible to sequences of ECP (Elementary Constraints Propagation), Singles and whips[1]. (Of course, using these rules instead of such combinations may make the solution look shorter.)

One obvious exception is the adjacent 3-3 rule, as the only means of ruling out a loop surrounding the two cells is the global one-loop constraint.

I've now fully interfaced Slitherlink to my general pattern-based solver of CSPs (" CSP-Rules") according to the principles explained for other puzzles in my last book ("Pattern-Based Constraint Satisfaction and Logic Puzzles").
And I've tried several puzzles from the above mentioned websites, at different difficulty levels (according to their own classifications). I can't find any logic in these classifications.

As in many puzzles with varying grid sizes, increasing grid size implies increasingly many obvious steps and makes the puzzles increasingly boring.

[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