Wednesday, 19 August 2015

grid deduction - The Terrible Twos of Slitherlink


This question is aimed at people who have a really good grasp of standard Slitherlink puzzles.


This is a standard, square cell, 10x10 Slitherlink puzzle I designed. It isn't what I would call a "true" Slitherlink puzzle, though.


Just2Puzzle


A true Slitherlink puzzle has as its solution exactly one closed, non-intersecting "loop" that goes along the grid lines between the numbers, and satisfies the numbers in the cells: each number has the loop bordering its square on exactly that many sides. It may surprise you to find out that this puzzle can become a true Slitherlink puzzle by removing some of the "2"s from the board.



What is the least number of twos that need to be removed in order for this Slitherlink to have exactly one solution? Anybody could stumble upon the answer, so if you post an answer below, you must explain why it cannot be less than the number you found.




The above image was taken from this website which contains a powerful SAT solver for Slitherlink puzzles. I consider it fair to use such a solver for this question, but you still have to explain what is going on.


There are more questions I can ask on the topic of Slitherlink puzzles made just from twos, so if there is interest... there's more where this came from.



Answer



The minimum number of twos that need to be removed is:



Three



Explanation:



In Slitherlink, there are two ways to have two edges on a square: two parallel lines or a single corner. Because of this, the optimal way to hit as many squares with two lines is to use a spiral:

11x10 example

Now, obviously the above example isn't going to work as it's 11x10, but it's a good visual for what's required of the spiral, namely two things:

1. The outside loop end will require a square with three sides, and

2. The inside loop end will require one square to have three sides, and another to have either one or three sides (one side would mean that the center loop will be bigger).

Because of the grid size being a square, the inner loop will need to have one square with only one side, as you can see from the failed example above.

As an aside, I would posit that any Slitherlink puzzle of this type with x rows and y columns would have a inner loop with two three-sided squares where x = y, and one of each of one-sided and three-sided squares if x = y + 1 or y = x + 1.



Here are two examples that will work with the constraints given:



Example 1
Example 2



As for the rules as to where the twos will be removed from:



There are two ways a two can be removed from the outside:

1. Remove from a corner

- In this case, move diagonally from that corner inwards to the fifth two, and remove it. Then, move diagonally one square towards either corner not opposite the beginning square, and remove the two there.
- This method produces eight possible answers, two for each corner.

2. Remove from a space adjacent to a corner (not diagonally).
- Move diagonally from the square you've removed a two from towards the center to the fourth two, and remove it. Then, move one diagonal space towards the closer non-opposite corner, and remove the two there.
- This method will produce eight answers as well, one for each space adjacent to the corner, with two of those spaces available for each.



No comments:

Post a Comment

Understanding Stagnation point in pitot fluid

What is stagnation point in fluid mechanics. At the open end of the pitot tube the velocity of the fluid becomes zero.But that should result...