The New Sudoku Players' Forum

[denis_berthier]

Applying the "one-connected-inside" rule in a larger puzzle

10x10 puzzle Hard 3,858,923 from puzzle-loop.com can be solved by local constraint propagation plus an application of the one-connected-inside technique I mentioned in example #1 here: http://forum.enjoysudoku.com/solving-slitherlink-puzzles-t31264-7.html

Code: Select all

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


Using only local constraints propagation (plus the adjacent 3s rule) - a very tedious work if it wasn't done automatically by CSP-Rules - one obtains the following state:

Code: Select all

XXXOXXOXOX
OOXOXOOXOX
XXXOXXXXXX
XOXXXOXXOX
OOXOXOOOOO
XXXOXXXOXX
XOOOXO-OXX
OOXOOOXXXO
XXXOXOXOOO
XOXXXXXXXX

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


At this point, no local constraint can make a choice between the remaining two possibilities. But the only way to connect the inside is as follows (of course, one could also invoke the only-one-loop constraint):

Code: Select all

XXXOXXOXOX
OOXOXOOXOX
XXXOXXXXXX
XOXXXOXXOX
OOXOXOOOOO
XXXOXXXOXX
XOOOXOXOXX
OOXOOOXXXO
XXXOXOXOOO
XOXXXXXXXX


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


[denis_berthier]

Applying the "one-connected-outside" rule in a larger puzzle

In a complementary way to my previous post, 10x10 puzzle Hard 4,484,334 from puzzle-loop.com can be solved by local constraint propagation plus an application of the one-connected-outside technique I mentioned in examples #2 et #3 here: http://forum.enjoysudoku.com/solving-slitherlink-puzzles-t31264-7.html

Code: Select all

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


Using only local constraints propagation (plus the adjacent 3s rule), one obtains the following state:

Code: Select all

XXOXOXOXOX
XXOXOXXXXX
XXXXXXOXOO
OOXOOOOOOX
XXXXXXXOXX
OOXOXXXOOX
XXXOOOXXXX
XOXXXOXOOO
OOOXOOXOXX
XXXX-XXXXX


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


At this point, no local constraint can make a choice between the remaining two possibilities. But the only way to connect the outside is as follows (here again, one could also invoke the only-one-loop constraint):

Code: Select all

XXOXOXOXOX
XXOXOXXXXX
XXXXXXOXOO
OOXOOOOOOX
XXXXXXXOXX
OOXOXXXOOX
XXXOOOXXXX
XOXXXOXOOO
OOOXOOXOXX
XXXXOXXXXX


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


[Serg]

Hi, Denis!

I've tried several "hard" puzzles from the site you've found yesterday (puzzle-loop.com): 5 of size 5x5 and 25 of size 7x7.

The hardest I've found is #5,451,296 ( I don't know how they name their puzzles; it suggests they have a huge number of them).

Code: Select all

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

"Hardest" should be understood with the same warnings as always, i.e. wrt to my resolution approach. In the present case, it means that I have to apply several only-one-loop arguments in addition to local constraints propagation.

Serg (or anyone else), if you try it, I'd like to have your opinion on difficulty.

I've still solved this puzzle! I was forced to use methods of in/out-line control (described in your posts in this thread) to do it. (My previous solving pathes didn't require any in/out-line control.)
Nice puzzle! Though it is difficult, but can be solved by logical methods (I don't account for local (2-3 cells wide) T&E.) Here is solution:

Code: Select all

+---+---+---+   +---+   +---+
|           |   | 3 |   | 3 |
+   +---+---+   +   +---+   +
|   |     2     |     2     |
+   +   +---+   +---+---+   +
|   |   | 3 | 1   2     | 2 |
+   +---+   +   +---+---+   +
|     2   1 | 3 |     2     |
+   +---+   +---+   +---+   +
|   |   |         2 |   |   |
+   +   +---+   +---+   +   +
| 2 |     3 |   |     2 |   |
+   +   +---+   +   +---+   +
|   |   | 3     |   | 3     |
+---+   +---+---+   +---+---+


Thank you for finding this puzzle.

Serg

[denis_berthier]

Nice puzzle! Though it is difficult, but can be solved by logical methods (I don't account for local (2-3 cells wide) T&E.)

Yes. I think it's nice because it isn't too easy and we don't have to track several levels of hypotheses - contrary to the Raetsel puzzles.

As of now, I've tried:
- five 5x5
- forty 7x7
- twenty 10x10
from the same site.

I could solve all of them* by local constraints propagation plus in/out arguments or eliminations related to potential small loops (sometimes with many cells, but always obvious).
I may try later a few 15x15 or 20x20 to check if the same remains true of them.



(*) except one. Indeed, I can't find a solution for the following (Hard 10x10 # 7,716,100):

Code: Select all

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

I've checked several times that I hadn't made an error in copying it, but it seems to be OK.
BTW, have you noticed that you can select a puzzle by its number (below the iPhone icon, "Specific puzzle" option)?


Two things I've learnt from the manual parts of solving I had to do:
1) always make immediately all the eliminations related to each assertion before making further assertions! This helps a lot in avoiding errors.
2) don't try to be smart by guessing part of the path; it often turns out to be wrong. Instead keep to the local constraints as long as possible. This is particularly important in cases where embedded hypotheses have to be made (as for many of the Raetsel puzzles, eventually leading to a contradiction, i.e. a partial loop) and that are therefore very error-prone. There is also another reason: this is the only means for proving uniqueness of the solution. This "rule" may seems obvious, but it isn't so easy to apply it strictly.

[Serg]

Hi, Denis!

I can't find a solution for the following (Hard 10x10 # 7,716,100):

Code: Select all

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

I've checked several times that I hadn't made an error in copying it, but it seems to be OK.
BTW, have you noticed that you can select a puzzle by its number (below the iPhone icon, "Specific puzzle" option)?

I checked this puzzle too (by eye) for correspondence to the original - all look like OK. I'll try to solve this puzzle coming days.
I noticed posibility to select puzzle by number, but it turns out you must select class of puzzle too (size and difficulty level), otherwise you can pick up another puzzle having the same number, but another size.

Serg

[denis_berthier]

Hi Serg,

I'll try to solve this puzzle coming days.

I've finally found the solution and proven that it is unique. As before, in my first attempts, I had missed possibilities.
Unless I'm still missing some obvious resolution path (but I've already attacked it from different angles), it is much harder than the other ones from this site.
I'm still interested if you give it a try.

[evert]

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.


...

Code: Select all

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


That's great!

My regional settings are on Dutch (Netherlands) - United States-International - and alt- doesn't work for me for getting the horizontal continuous line. What's the asci-number?

[evert]

Never mind; http://www.asciivalue.com/index.php
— = 151

[denis_berthier]

Never mind; http://www.asciivalue.com/index.php
— = 151

HI Evert,

Do you think I should use - instead of alt- ?
(It wouldn't be a problem for me: just change the value of a parameter).

[Edit:
Actually, I should change two parameters, because - and . don't make a good combination; they are not aligned.
I should also replace . by +
I had adopted . because it's the representation used on all the websites. But I also like Serg's notation with a +
So, it's up to the participants in this discussion.
]

[evert]

Never mind; http://www.asciivalue.com/index.php
— = 151

HI Evert,

Do you think I should use - instead of alt- ?
(It wouldn't be a problem for me: just change the value of a parameter).

[Edit:
Actually, I should change two parameters, because - and . don't make a good combination; they are not aligned.
I should also replace . by +
I had adopted . because it's the representation used on all the websites. But I also like Serg's notation with a +
So, it's up to the participants in this discussion.
]

Perhaps you could keep your current format, but allow the underscore as an alternative for ascii-151:

Code: Select all

.___.___.   .___.   .___.   .___.   .___.
| 2     |   | 3 |   |   |   | 3 | 3 |   |
.   .   .   .   .   .   .___.   .___.   .
| 1     | 3 |   | 3 | 1   2       2   2 |
.   .   .___.   .___.   .___.   .___.___.
|     1           2   2 | 3 |   |     2
.___.___.   .___.___.___.   .___.   .___.
        | 2 |     2   2   1   1     |   |
.___.___.   .___.___.___.___.   .___.   .
| 3       0   2             | 2 |       |
.___.___.   .___.   .   .   .   .___.   .
      3 |   |   |     1   1 |       | 2 |
.___.___.   .   .___.___.   .___.___.   .
|         1 |         2 | 1       2   2 |
.   .___.   .___.___.   .   .___.___.___.
| 3 | 3 |     1   3 |   | 2 | 2       2
.___.   .___.   .___.   .   .   .___.___.
  2       3 |   |     2 |   | 3 |     2 |
.___.___.___.   .....___.   .___.   .   .
|               :   :             1   2 |
.___.___.___.___.....___.___.___.___.___.


What software are you currently using for slitherlink?

[denis_berthier]

Actually, I should change two parameters, because - and . don't make a good combination; they are not aligned.
I should also replace . by +

Perhaps you could keep your current format, but allow the underscore as an alternative for ascii-151

But the _. combination is not good: _ is too low. So, if there is a problem with alt-, I prefer Serg's solution.

What software are you currently using for slitherlink?

I've interfaced CSP-Rules (my general rule-based software for bivalue-chains, whips, braids, g-whips, ...) with Slitherlink.
I've added a few specific rules, such as adjacent 3s, but most of them are reducible to combinations of Singles and local constraints propagation.

CSP-Rules has no rules for dealing with global constraints. In the present case, what I don't have (yet) is specific rules for eliminating lines leading to "small" loops. So, when a puzzle requires the actual use of the global only-one-loop constraint, I currently finish it manually, sometimes using T&E, with all the errors and boredom this may entail.

[Serg]

Hi, Denis!
I had enough time last week (on vacations) to solve puzzle, so I am posting my results ("human impressions") here.

10x10 puzzle Hard 3,858,923 from puzzle-loop.com can be solved by local constraint propagation plus an application of the one-connected-inside technique I mentioned in example #1 here: http://forum.enjoysudoku.com/solving-slitherlink-puzzles-t31264-7.html

Code: Select all

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


Using only local constraints propagation (plus the adjacent 3s rule) - a very tedious work if it wasn't done automatically by CSP-Rules ...

I solved this puzzle and confirm your solution. It is really hard puzzle to my mind. It took me 3 hours to solve it ("a very tedious work"). Congratulations to you - final position automatically produced by "CSP-Rules" is non-trivial. To my mind it's very difficult to code Slitherlink solver, because traditional backtracking approach doesn't work well in this case (decision on selecting a border has local effect, so we should search decision tree too deep).

Serg

[Serg]

Hi, Denis!

In a complementary way to my previous post, 10x10 puzzle Hard 4,484,334 from puzzle-loop.com can be solved by local constraint propagation plus an application of the one-connected-outside technique I mentioned in examples #2 et #3 here: http://forum.enjoysudoku.com/solving-slitherlink-puzzles-t31264-7.html

Code: Select all

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


I solve this puzzle too. It took me 1 hour only to solve this puzzle, so I'd call it not hard, but "gentle" or "normal" instead.

Serg

[Serg]

Hi, Denis!

Hard 10x10 # 7,716,100:

Code: Select all

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

I solved this puzzle. It is really hard (it took me 3.5 hours to solve it). It seems to be the hardest among the puzzles published in this thread.
This is its solution:

Code: Select all

+---+---+   +---+---+   +---+---+---+---+
| 2     |   | 3     | 3 | 2             |
+   +---+   +---+   +---+   +---+---+   +
|   | 3       3 |           | 3   2 | 2 |
+   +---+   +---+   +---+   +---+   +   +
|       |   | 2   2 |   | 1   2 | 2 |   |
+   +   +---+   +---+   +   +   +   +   +
|     1       2 |       |       |   | 3 |
+---+---+   +---+   +---+   +---+   +---+
        | 2 | 2     |       | 2         
+---+   +   +   +---+   +---+   +---+---+
| 3 | 3 |   |   | 3   1 | 3     | 2     |
+   +---+   +   +---+   +---+---+   +---+
| 2         |       |               | 3 
+---+---+   +---+   +---+   +---+   +---+
      3 | 1     |     2 |   |   | 1     |
+---+---+   +---+   +   +---+   +   +---+
| 2   1   2 | 2   1   1   2     |   | 3 
+   +   +---+   +---+---+---+---+   +---+
|       |     1 |                 1     |
+---+---+   +   +---+---+---+---+---+---+

Serg

[denis_berthier]

Hi Serg,
Thanks for your evaluations of these puzzles in manual solving.

I solved this puzzle and confirm your solution. It is really hard puzzle to my mind. It took me 3 hours to solve it ("a very tedious work"). Congratulations to you - final position automatically produced by "CSP-Rules" is non-trivial. To my mind it's very difficult to code Slitherlink solver, because traditional backtracking approach doesn't work well in this case (decision on selecting a border has local effect, so we should search decision tree too deep).

I had planned to write something about how I apply my general pattern-based approach of CSP solving to Slitherlink. I've been busy with other things and away from my Mac for some time, but I haven't given up with the idea.