Let me put it like this: Numberlink.
Numberlink in my eyes has something of a notoriety as a puzzle because whilst the rules are deceptively simple, you are actively encouraged to use metalogic – things like assuming all the squares are used, and that the solution is unique – to solve it. You can read more about it in MellowMelon’s excellent post here:
http://mellowmelon.wordpress.com/2010/07/24/numberlink-primer/
Of course, this provides the author of a Numberlink puzzle with a headache – after all, you can’t use the same solving meta-logic or you might end up with something like this:
Which most certainly does not solve uniquely. What I did was start off with a blank grid, and then filled it up with strands. As it turns out, the way I packed these strands together wasn’t “tight” enough, and there is plenty of the sort of wriggle-room you need for multiple solutions. Actually, I should confess before you go hunting for what I originally had in mind, that this was rather naughtily designed to leave exactly one square blocked off and hence left blank. This has nothing to do with the uniqueness of the solution however; you can rather trivially push one of the clues up by one square to get one particular solution that fills up the grid.
Nevertheless, I am convinced there is some logic dictating the uniqueness of a Numberlink solution. My proposed statement goes something like:
Suppose we are given a Numberlink puzzle (a grid with pairs of clues needed to be joined up), and a solution to the Numberlink puzzle that uses up all the squares. Then if this solution has “The Right Properties” then it must be unique.
Quite what The Right Properties are, I’m not entirely sure. One particular strategy is showing that the set of all solutions to a Numberlink puzzle are basically fiddles of each other, each related by a series of something akin to the Reidemeister moves of knot theory. Once you know what all the fiddles are, checking uniqueness of a solution comes down to scanning your candidate solution and seeing if you can apply any of these fiddles – using what I vaguely described as wriggling-room – to get a new solution from it.
One particular example was supplied by Andrey Bogdanov via the UKPA forums – a truly excellent resource – which means that the statement has to say something about symmetry, and what Topologists might call hyperelliptic involutions!
Anyhow, that’s nothing anything close to being rigorous, but I believe there’s a useful strategy there for those that are interested to take a look at. I’m sort of hoping that there might be multiple solutions to this one. Finding another solution to what I have in mind as “the” solution didn’t happen in the 5 minutes I had a quick scan over – so if there is indeed another solution I’d be interested in seeing what it looks like!
#087 Numberlink – rated medium. Maybe.All puzzles © Tom Collyer 2009-10
P.S. I know I definitely get some Japanese traffic to this blog, so if you are in the know – there are after all humongous nikoli Numberinks which would surely be impractical for a computer to check uniqueness – then please speak up :)
Well, this one certainly feels unique to me, but I have the same misgivings and uncertainties about resolving uniqueness for numberlinks as you do.
ReplyDeleteThe 11’s and 14’s together certainly force the general shape in the top right.
You get a little flexibility in where the four squirts out of the lower right, but as far as I can tell you can’t actually make the 1-5 part work if you send the 4 over the top.
Unique.
ReplyDeleteGreat post, great puzzle.
TheSubro
Cheers Thomas – actually your logic there is very reminiscent of the Reidemeister moves. More than that, it has a base in logic that a computer would be able to check very quickly (not that I have the skills necessary to do this, or indeed any sort of any programming) – you are checking basic properties on pairs of pairs. I also think it is the right way to think about “wriggle room”. Most illuminating!
ReplyDeleteI’d have a feeling that systematically enumerating various possibilities might be a start on “proving” numberlink. At this stage, I’d be inclined to think that checking at most triples or quadruples of these transitive intersections might be sufficient. When I get a chance I’ll have a check over a few numberlink solutions and see if this applies…
Regarding puzzle #87
ReplyDeleteThe puzzle feels very constrained – moreso than a typical Nikoli
We can say (without using uniqueness)
that “at most one” path can go around the 1s – this has to be 10s
and “at most one” path can split the 15s – this has to be the 14s (else the 14s will split the 11s)
The 1s then have no choice but to stick to the left (can’t split any other pair of numbers)
and then the 2s and the 4s then have to go around (either side of) the 3s
I’m pretty confident of a “uniqueness” proof here – sending paths around convex corners would seem to preserve uniqueness as the “shortest remaining path” – assuming all squares are used?