|
Ichneumon -> RE: Classic Slitherlink (1/14/2013 7:14:12 AM)
|
A technique that be very powerful and extremely effective when you're otherwise stuck is what I call the "inside/outside" method. It's based on an algorithm in geometry which determines if a point is inside or outside of a (possibly very complex and convoluted) polygon, by counting whether a line drawn from the point to a point known to be outside the polygon crosses an even or odd number of edges (if even, it's outside the polygon, if odd, it's inside the polygon). This works because if you're inside and cross one line, you're now outside, and vice versa.
Since the final solution in Slitherlink is a closed loop, it too is a polygon, and any square on the grid is either inside or outside the loop. This fact can be used to deduce whether two adjacent squares must (or must not) have a line between them in the final solution.
Consider your partially solved puzzle as I've marked it up here. Look at the column near the middle which has colored dots on it. The red dot at the very top is clearly in a cell that is outside the loop, as there is no line above it. Moving down, since we crossed a line, the cell below it (which has the "3" in it) has to be inside the loop, so I've marked it with a blue dot. Moving down again, we cross another line, so the cell below that has to be outside the loop, and I've marked it with a red dot (it's also pretty obviously outside the loop since you've completed the area up and to the left of it which leads to the edge of the puzzle). The cell below *that* one we reach by crossing a "definitely no line here" boundary, so it too must also be outside the loop like the one we just came from (so a red dot again). And so on downward, flipping between inside/outside each time we cross a known line, and remaining with our current inside/outside status each time we cross a "no line here" boundary. When we reach the "maybe a line?" area surrounded by the turquoise box, we stop for a moment as we don't yet know if that's going to end up a line or a "no line".
Now we move to the bottom and repeat the process moving upwards. The lowest cell is clearly inside the loop since there's a line on the bottom of the puzzle dividing it from the "outside" area of the puzzle -- blue dot. As before, we move up the puzzle, marking each cell as inside (blue) or outside (red) based on whether we crossed a line to get there. Again we run into the "don't know" turquoise box area.
Note that we now know that the cell directly above the turquoise rectangle is *outside* the loop (since we red-dotted it), while the cell directly below the turquoise rectangle is *inside* the loop (since we blue-dotted it). Two immediately adjacent areas that are of opposite "sideness" (one outside, one inside) MUST be separated by a line lest they "run into" each other and create a contradiction. Thus we KNOW for a fact that a line belongs in the area marked by the turquoise rectangle. QED.
In this case it happened that we could do this exercise in a straight-line clear across the puzzle, but often things aren't that neat. But we can "go around corners" if necessary. If we didn't have the lower half of that dotted column complete enough, we could have done something else. Look at the cells marked with orange dots a little to the left. The lowermost one was clearly an "outside the loop" cell. From there I "walked" up the "also outside" region (not always in a straight line, but always crossing a "no line here" X'ed divider so we know we're still in the "outside" region. Look at the green dot just to the right of the uppermost orange dot -- we know it must be an "inside" cell since there's a known line between it and our "outside orange" dot. Lines separate insides from outsides.
Also note the other green dot on the "3" cell -- we know it must be an "inside" cell since we had to cross a line to it from the red (outside) dot just to the right of it (which we knew was outside due to coming down from the top of the puzzle before). Now consider the "is it a line?" area between the two green dots. It MUST NOT be a line, otherwise it would divide a known inside cell from a known inside cell, which is a contradiction. Adjacent inside cells, and also adjacent outside cells, have no line between them, they are part of the same region. So we can safely "x" that location and proceed solving as usual.
[image]local://261593/3B84E69A67394AC4A66B8709F804213D.jpg[/image]
|
|
|
|