Solving Slitherlink puzzles

For fans of all other kinds of logic puzzles

Re: Solving Slitherlink puzzles

Postby denis_berthier » Tue Oct 29, 2013 6:46 am

Some time has passed since my last post here. I've been busy with other things, but I've occasionally had some time for Slitherlink.

I had already coded all the specific rules I could find on the web. But as I said previously, most of them are subsumed by whips - so that coding them is rather frustrating: they can make the resolution paths shorter, but they don't allow to solve more puzzles.

Recently, I've coded a rule for automatically eliminating incomplete loops - which makes my manual solution paths above obsolete.
Since then, I can solve ALL the puzzles I've found on the 2 main websites discussed above: Krazydad and puzzle-loop.com

To be more precise, I've solved:

from puzzle-loop:
100 puzzles of category Hard and of size 7x7 ("Hard" is the hardest category there)
100 puzzles of category Hard and of size 10x10
5 puzzles of category Hard and of size 15x15
plus a few of other sizes or easier categories
Increasing size just makes the solution longer. (This is probably specific to this website, because it seems obvious that, much as in Sudoku, larger size implies larger mean maximum T&E-depth for minimal puzzles.)


from Krazydad:
of few tens taken from various "books", mainly of the "tough" category (the hardest there).
Same remarks as above about size.
For other types of puzzles (Sudoku, Kakuro, ...), Krazydad is known for having only easy puzzles.


various puzzles from other various websites.


I think most of the puzzles available on the web are not minimal (which is not a problem, as far as only resolution is concerned).
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Solving Slitherlink puzzles

Postby Serg » Wed Oct 30, 2013 12:36 pm

Hi, Denis!
denis_berthier wrote:I had already coded all the specific rules I could find on the web. But as I said previously, most of them are subsumed by whips - so that coding them is rather frustrating: they can make the resolution paths shorter, but they don't allow to solve more puzzles.

Recently, I've coded a rule for automatically eliminating incomplete loops - which makes my manual solution paths above obsolete.
Since then, I can solve ALL the puzzles I've found on the 2 main websites discussed above: Krazydad and puzzle-loop.com

So, you have now Slitherlink solver, right? If so, congratulations to you! This puzzle, to my mind, is rather difficult for "solver coding". Is your CRT sufficient to build Slitherlink solver w/o any empirical rules?

Serg
Serg
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Re: Solving Slitherlink puzzles

Postby denis_berthier » Wed Oct 30, 2013 3:25 pm

Serg wrote:
denis_berthier wrote:I had already coded all the specific rules I could find on the web. But as I said previously, most of them are subsumed by whips - so that coding them is rather frustrating: they can make the resolution paths shorter, but they don't allow to solve more puzzles.

Recently, I've coded a rule for automatically eliminating incomplete loops - which makes my manual solution paths above obsolete.
Since then, I can solve ALL the puzzles I've found on the 2 main websites discussed above: Krazydad and puzzle-loop.com

So, you have now Slitherlink solver, right? If so, congratulations to you! This puzzle, to my mind, is rather difficult for "solver coding". Is your CRT sufficient to build Slitherlink solver w/o any empirical rules?
Serg


Hi Serg,
I think I can answer yes, but only after a few precisions:

Firstly, as suggested by the title of my last book ("Pattern-Based Constraint Satisfaction ..."), I'm not interested in solving puzzles by any means (e.g. by DFS or BFS). I'm only interested in solving them in a pattern-based (or rule-based) purely logical way. I'm also interested in finding the simplest resolution path (in the sense that it uses the simplest possible rules - e.g. the shortest chains).
As a result, speed of resolution is not my main purpose. (You can consider that my problem is exponentially more complex than just finding a solution by any means.)

Secondly,
- for any type of logic puzzle that can be expressed as a CSP, puzzle instances can be classified according to the level of T&E they require when only Singles and elementary constraints are used;
- puzzles in T&E(0) can be solved by Singles and elementary constraints propagation;
- puzzles in T&E(1) can be solved by Braids (and most of the time by whips, a much simpler type of chain pattern);
- puzzles in T&E(2) can be solved by B-braids, a kind of extended braids admitting braids as their right-linking elements.
These results are valid for any CSP.


What I've shown for Sudoku is:
- "almost all" the 9x9 minimal puzzles are in T&E(0) or T&E(1) and can therefore be solved by braids;
- Blue's calculations suggest that about only 1/30,000,000 minimal Sudoku 9x9 puzzles are not in T&E(0 or 1);
- my calculations on the hardest list show that they are all solvable by B7-braids, which considerably reinforces my old T&E(2) conjecture that all the puzzles are in T&E(0 or 1 or 2);
- however, for larger sized Sudoku puzzles, the proportion in T&E(0 or 1) decreases very fast with grid size.


So, how can we extend this to Slitherlink?
The T&E(k) classification, the T&E(1) vs braids theorem still holds. What we don't know is the proportion of minimal puzzles in T&E(0 or 1) for some fixed grid size.

For any puzzle, we'll always find large instances that can't be solved by reasonably simple purely logical means. I think also that, for not too small grid size, we'll always find exceptionally hard instances of that size.
Where one puts the boundary of "reasonably simple" is much a matter of personal taste. For me, it may be whips or g-whips or B-whips or S-whips (or corresponding braids) - possibly of restricted size - , plus small-size Subsets or gSubsets, plus application specific rules (e.g. sk-loops in Sudoku; ascending chains, hills and valleys in Futoshiki; adjacent 3s and incomplete-loops in Slitherlink, ...)
In any case, there will always be a point where NO pattern-based solution will be possible. As the pattern-based requirement comes from players, I don't think this is a big problem: puzzles proposed to players shouldn't be too hard. Indeed, for all the puzzle types I’ve analysed in my last book, whips are so powerful that small ones (+ small Subsets) cover much more than puzzles ever proposed to real players.


Serg wrote:Is your CRT sufficient to build Slitherlink solver w/o any empirical rules?

The only rules I use for solving all the puzzles mentioned in my previous post are:
1) Singles, elementary constraint propagation,
2) whips,
3) elimination of partial loops,
4) plus a few application-specific rules that are formally reducible to the previous ones (I use them only because they are popular).

1 and 2 are meaningful and valid for any CSP and 3 can't be avoided in Slitherlink (it's part of the basic problem constraints). Is that what you meant by "w/o empirical rules" ?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Solving Slitherlink puzzles

Postby denis_berthier » Fri May 08, 2015 2:37 pm

If there is still anyone here interested in Slitherlink, I'd like to know what you think of the following 10x10 puzzle:


Code: Select all
. 2 2 2 . . 2 1 . 2
. 2 2 . 1 2 . 3 . .
1 1 . . . 3 1 . 1 .
. 2 . . 1 . 2 . . .
. 1 1 . . 1 . 2 2 1
2 1 1 1 3 . . 1 2 .
. 1 . 2 1 . 1 . 3 .
. 2 . 2 . 2 . 1 . 2
. 1 2 1 . 2 . . 1 .
2 3 . 3 . 3 1 2 2 .
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Solving Slitherlink puzzles

Postby Serg » Sun May 10, 2015 6:43 pm

Hi, Denis!
denis_berthier wrote:If there is still anyone here interested in Slitherlink, I'd like to know what you think of the following 10x10 puzzle:

Code: Select all
. 2 2 2 . . 2 1 . 2
. 2 2 . 1 2 . 3 . .
1 1 . . . 3 1 . 1 .
. 2 . . 1 . 2 . . .
. 1 1 . . 1 . 2 2 1
2 1 1 1 3 . . 1 2 .
. 1 . 2 1 . 1 . 3 .
. 2 . 2 . 2 . 1 . 2
. 1 2 1 . 2 . . 1 .
2 3 . 3 . 3 1 2 2 .

This puzzle is very difficult. I managed to process a quarter part only of the puzzle. It looks like rather unusual - too many digits, especially "1" and "2" digits. The most useful are "0" and "3" (especially useful are "3" digits located in neighbouring cells), but this puzzle has no such "clue" configurations.

Serg
Serg
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Re: Solving Slitherlink puzzles

Postby denis_berthier » Mon May 11, 2015 4:22 am

Serg wrote:This puzzle is very difficult. I managed to process a quarter part only of the puzzle. It looks like rather unusual - too many digits, especially "1" and "2" digits. The most useful are "0" and "3" (especially useful are "3" digits located in neighbouring cells), but this puzzle has no such "clue" configurations.


Hi Serg,

Thanks for trying.
It's one of the hardest 2 puzzles (among 500 "hard" 10x10) I generated with Tatham's software.
I had doubts about whether I had missed any obvious tricks, because Tatham's puzzles are generally not so hard.

I can still solve it with SlitherRules (the Slitherlink interface to CSP-Rules) but it requires whips[9], which is quite hard for Slitherlink, considering the high branching factor.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Previous

Return to Other logic puzzles