The New Sudoku Players' Forum

[denis_berthier]

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

[Serg]

Hi, Denis!

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

[denis_berthier]

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.

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]

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 .


[Serg]

Hi, Denis!

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

[denis_berthier]

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.

[dstoykov]

www.youtube.com/watch?v=qOEfJOODhIs&index=1&list=PLDFoLiUFJTEa_KdehuWo12cppFEv8_Cug

[dstoykov]

https://www.youtube.com/watch?v=qOEfJOODhIs&t=

The last post is more than two years old.
Is there any active forum members ?

[Serg]

Hi, dstoykov!

The last post is more than two years old.
Is there any active forum members ?

I am Slitherlink fun. Your links points to https://www.puzzle-loop.com/ site. Their puzzles (even "hard") are too simple. "Very Hard" Slitherlink puzzles from "BrainBashers" - https://www.brainbashers.com/slitherlink.asp are more complicated, but the hardest free puzzles I've found at http://www.kakuro-online.com/slitherlink/ site ("Hard" puzzles generated at "Generator" tab).

Serg

[dstoykov]

Thank you Serg for the links.

When we(*) started to develop our bot, we planned to create 7 or 8 levels of rules - an analog of our human rules when manually solve slitherlink puzzles at puzzle-loop.com.
But when we finished the first 5 levels, the unfinished bot started to solve all the puzzles including the hardest levels. And it confirmed our assumption that the rest of planned level 6 and 7 are some kind of composition of previous levels 1 to 5

So, I started to assume the puzzles in puzzle-loop are more simple than I expected.
Now I will check your links.

According to rules we defined and coded in our bot - we defined some C++ data structures (classes) for "dots", "cells", "h-lines" and "v-lines" all of them multiplied by four rotations.
And than it was very easy to code the rules like this simple rule:
--------------------------------------------------------
bool AuxDot::Rule6_Simple()
{
if (*pt == 1 && *pb == 1 && (*pl == -1 || *pr == -1)) // -1 unknown, 0 - red 'x' (impossible) , 1 - line exists

{
*pl = 0;
*pr = 0;
return true;
}
return false;
}
--------------------------------------------------------

This C++ simple rule, translated to our human rules means:

In a dot, if top_line exists and bottom_line exists and (left_line is unknown or right_line is unknown)
then set left_line to impossible (red 'x') and set right_line to impossible


-------------------------------------------
(*) "we" means me and my two sons. We together discussed and coded the bot. They were high school students at this moment.


-----------------------------------------------
EDIT
According to "very hard" puzzles at https://www.brainbashers.com/slitherlink.asp - I just solved manually a 15x15 puzzle level "very hard" and I didn't find any difficulties except that mouse clicks are harder than mouse click on puzzle-loop.com
-----------------------------------------------

EDIT
Accordind to http://www.kakuro-online.com/slitherlink/ - I just solved manually a 18x10 puzzle and yes, they are a little bit harder than puzzle-loop.com. Our bot will not be able to solve this puzzle with its existing rules and we have to add some new.

[Serg]

Hi, dstoykov!

This C++ simple rule, translated to our human rules means:
In a dot, if top_line exists and bottom_line exists and (left_line is unknown or right_line is unknown)
then set left_line to impossible (red 'x') and set right_line to impossible

I don't understand your description. Could you show an example?

According to "very hard" puzzles at https://www.brainbashers.com/slitherlink.asp - I just solved manually a 15x15 puzzle level "very hard" and I didn't find any difficulties except that mouse clicks are harder than mouse click on puzzle-loop.com

I should say that I solved 10x10 puzzles only at cited sites. (It is my favorite size of Slitherlink puzzles.)

Serg

[dstoykov]

This simple rule

In a dot, if top_line exists and bottom_line exists and (left_line is unknown or right_line is unknown)
then set left_line to impossible (red 'x') and set right_line to impossible

is shown on the picture

simpleruleexample.jpg (9.87 KiB) Viewed 2059 times

https://drive.google.com/file/d/0B6IJyb-0zNlPRzJ1SkRtdl8yMzg/view

EDIT
If want to be more precise and strict, there are two subcases for this specific simple rule - (left_line is unknown or right_line is unknown) and it is not exactly shown on the picture.
The correct picture is

simpleruleexample2.jpg (18.62 KiB) Viewed 2057 times

[dstoykov]

50x50-260.jpg (245.12 KiB) Viewed 2045 times

[dstoykov]

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 .


10x10.jpg (48.6 KiB) Viewed 2042 times