2
$\begingroup$

Note: This is not asking for a general strategy, you can find that here.

Is the following a valid strategy in solving Numberlink (Flow Free) puzzles (I like to call it 'unwrapping the grid'):

1...3
24.1.
...4.
3..2.
.....

Since the 3s are on the edge of the box with nothing in the way, we can connect them:

1...3
24.1│
...4│
3..2│
└───┘

Then we can ignore the 3s:

1...
24.1
...4
 ..2

Now, the 2s and the 1s are on the edge of our remaining figure, also with nothing on the way – connect them:

1──┐
24.1
└┐.4
 └─2

Now, ignore them:

4.
 .4

And the 4s are on the edges:

4┐
 └4

Now, put it all together to get the solution:

1──┐3
24┐1│
└┐└4│
3└─2│
└───┘

In this case, it solved the whole puzzle. In other cases, it may be good to make progress.

But does it actually work?

Affirmative case:  please provide a proof

Negative case:     please provide a valid counterexample
        (noting that the base puzzle must also have a unique solution)

Edit: Jaap Scherphuis has provided a counterexample where there is a direction ambiguity. Is there a counterexample where there is no direction ambiguity (i.e. one of the boundaries has another number on it or there is only one path either way), because the strategy can't actually be used with such an ambiguity?

$\endgroup$
5
  • $\begingroup$ Wikipedia isn't absolutist about requiring all cells to be filled by a solution. Are you? $\endgroup$
    – humn
    Commented Mar 3, 2017 at 8:17
  • 1
    $\begingroup$ @humn - I think it's better that all cells be filled else we have plenty of good strategies like corner parties not working. $\endgroup$
    – boboquack
    Commented Mar 3, 2017 at 8:19
  • $\begingroup$ (Side comment:) The reverse - "wrapping the grid" - does seem like a handy way to make one of these puzzles $\endgroup$
    – humn
    Commented Mar 3, 2017 at 8:26
  • $\begingroup$ I'm sure this works, but I don't actually have a proof. $\endgroup$
    – Kruga
    Commented Mar 3, 2017 at 8:34
  • $\begingroup$ It's a strategy I use all the time. Sometimes however, both directions around the edge are available, and then you have to think about which one eats up too much living room for the other links. If one of the two numbers is not on the border but near, you can often still prove/intuit that the link has to go most of the way along the border, simplifying the rest of the puzzle. $\endgroup$ Commented Mar 3, 2017 at 8:48

1 Answer 1

4
$\begingroup$

The strategy often works, but it is not fool proof.

Here is an interesting example where there are two cells labelled a on the border, but connecting them by a link along the border in either direction will not work.

 . . . . . . . . a . . . . . . . .
 . . b c d e . . . . . f g h i . .
 . . j . . j . . . . . k . . k . .
 . . b c d e . . . . . f g h i . .
 . . . . . . . . a . . . . . . . .
This is a rather contrived counterexample, and in practice this kind of situation is very unlikely to occur.

Edit: Here is an example without the directional ambiguity:

 . . . . . . . . a g . . .
 . . b c d e . . . . . h .
 . . j . . j . . . . f . .
 . . b c d e . . . g h . .
 . . . . . . . . a f . . .
Here's a nicer more symmetric example.
 . . . . . . . . . . . . a
 . . b c d e . . . . . . g
 . . j . . j . . . . f . f
 . . b c d e . . . . . . g
 . . . . . . . . . . . . a

Edit 2: Kruga pointed out in a comment an excellent counter example that occurred in real life:

 . . . . . . . 9 1
 . 3 . 9 8 . . 8 .
 . . . . . . . . .
 1 . . . . 7 . 2 .
 . . 2 6 . . . . .
 . 4 5 . . . . . .
 . . . . . 6 . . .
 . . 4 . 5 3 . 7 .
 . . . . . . . . .
Here is the same diagram with links 3-9 already filled in. If link 1 had been connected around the board edge, there ends up not being enough room left for links 2 and 3. Instead, you have to link 8 and 9 first, and then link 1 becomes an ambiguous case which you cannot solve for certain till 4-7 have also been linked (though it clear after 8 and 9 that the long route isolates the top-left 3 so is probably wrong).
 . . . ┌───────9 1
 . 3 . 9 8─────8 .
 . . . . . . . . .
 1 . . . . 7─┐ 2 .
 . . 2 6 . . └─┐ .
 . 4 5 └─┐ . . │ .
 . │ └─┐ └─6 . │ .
 . └─4 └─5 3 . 7 .
 . . . . . . . . .
enter image description here

$\endgroup$
2
  • $\begingroup$ I just came across a better counter example here. The purple have a clear path around the edge, but that's not the solution. $\endgroup$
    – Kruga
    Commented Mar 7, 2017 at 22:37
  • $\begingroup$ Thanks @Kruga, I have added your excellent example to the answer. $\endgroup$ Commented Mar 8, 2017 at 5:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.