Following the publication of my book, "Pattern-Based Constraint Satisfaction and Logic Puzzles (Second Edition)" (PBCS2), in which there is a full chapter dedicated to Slitherlink, I'll give here the detailed solution of a few Slitherlink puzzles according to the resolution model developed in the book - if anyone is still interested in Slitherlink (the topic hasn't been active for a long time).
I'll take the examples discussed in the old thread: http://forum.enjoysudoku.com/solving-slitherlink-puzzles-t31264.html, which I opened little after I discovered Slitherlink on some website. What I wrote there is now largely superseded by what's in the book.
And, as my resolution model is now complete, I preferred to open a new thread.
First, a few definitions and notations (details can be found in the book):
Given a mxn grid (m rows and n columns of cells), there are:
- m+1 rows and n columns of possible horizontal lines
- m rows and n+1 columns of possible vertical lines
the horizontal line at the top of cell r3c7 is named Hr3c7
the vertical line at the left of cell r3c7 is named Vr3c7
There are 3 types of "natural" CSP-Variables (associated with straightforward representations of the givens and solution):
- Nrc represents the number of borders of cell (r, c) touching the solution loop
- Hrc represents the upper border of cell (r, c), Hrc = 1 if it touches the solution loop, 0 otherwise
- Vrc represents the left border of cell (r, c), Vrc = 1 if it touches the solution loop, 0 otherwise
Notice that all the resolution rules presented in the literature use only these CSP-Variables (in their own, usually informal, ways).
As always in my approach, there are additional CSP-Variables, with symbols n, e, s, w representing the cardinal directions:
- Prc represents the point at the upper left corner of cell (r, c). Its values can only be o, nw, ne, sw, se, ns, ew (representing which lines going through it do belong to the solution loop, with obvious restrictions for cells at the edges and corners.
- Brc represents the border of cell (r, c). Its values can only be o, n, s, w, e, nw, ne, sw, se, ns, ew, wne, nes, esw, swn (representing which lines of the border do belong to the solution loop), with obvious restrictions for cells at the edges and corners.
Optionally, there is one more type of CSP-Variables:
- Irc represents whether cell (r, c) is inside (Irc = 1) or outside (Irc = 0) the solution loop.
Notice that, with the values allowed for Prc CSP-Variables, the basic fact that a point can only have 0 or 2 lines touching it is automatically taken into account.
Slitherlink: pattern-based solutions
2 posts
• Page 1 of 1
Slitherlink: pattern-based solutions
by denis_berthier » Sat Aug 08, 2015 5:53 am
Last edited by denis_berthier on Sat Aug 08, 2015 8:49 am, edited 1 time in total.
- denis_berthier
- 2010 Supporter
- Posts: 4215
- Joined: 19 June 2007
- Location: Paris
Easy example
by denis_berthier » Sat Aug 08, 2015 6:22 am
The first example in the old thread was the following easy 7x7 puzzle:
Here is the full resolution path.
Notice that, as always with such kinds of puzzles involving large numbers of candidates, most steps (singles) are trivial and would be applied by a human player without even thinking about it. They make the resolution path look very long, but I preferred to keep them, at least for a first example.
All the (classical) non-single rules that appear in the path are "macro-rules", i.e. they can be replaced by sequences of singles and whips[1], as proven in PBCS2.
The LOOP[k] are what allows to take into account the only-one-loop global constraint. They are not really necessary here. They could be replaced by rules for innies and outies (using the Irc CSP-variables).
and the solution
- Code: Select all
. 0 2 3 3 3 2
0 . . . . . 3
2 . 2 . . . 1
. . . . . . 2
. . . . . . 3
3 1 3 1 1 2 3
. . . . 2 . .
Here is the full resolution path.
Notice that, as always with such kinds of puzzles involving large numbers of candidates, most steps (singles) are trivial and would be applied by a human player without even thinking about it. They make the resolution path look very long, but I preferred to keep them, at least for a first example.
All the (classical) non-single rules that appear in the path are "macro-rules", i.e. they can be replaced by sequences of singles and whips[1], as proven in PBCS2.
The LOOP[k] are what allows to take into account the only-one-loop global constraint. They are not really necessary here. They could be replaced by rules for innies and outies (using the Irc CSP-variables).
Hidden Text: Show
and the solution
- Code: Select all
. . . .———. .———. .
0 2 | 3 | 3 | 3 | 2
. . .———. .———. .———.
0 | 3 |
. .———. .———. .———.———.
2 | 2 | | | 1
.———. .———. . .———. .
| | | | 2
.———. .———. .———. .———.
| | | 3 |
.———. .———. . . .———.
| 3 1 | 3 1 1 | 2 | 3
.———. .———.———. . .———.
| | 2 | |
. .———.———.———. .———.———.
- denis_berthier
- 2010 Supporter
- Posts: 4215
- Joined: 19 June 2007
- Location: Paris
2 posts
• Page 1 of 1
