All entries for Friday 24 September 2010
September 24, 2010
Today I must start with a bit of a confession. Whilst it might surprise those readers with longer memories, I do try and put out puzzles on a Friday that solve uniquely. However, I’m not entirely sure I want to do the same this week.
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:
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!
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 :)