All entries for Friday 24 September 2010

September 24, 2010

Friday Puzzles #71

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:
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 :)


Information

Welcome to the blog of current UKPA sudoku champion, two-time Times national sudoku champion and general logic puzzle fan Tom Collyer.



Home of the original Friday Puzzles, each Friday I publish a 100% original and handmade logic puzzle, inspired by the world-famous Nikoli company.


How to play:
AkariFillominoHashiHeyawakeHitoriKakuroLITSMasyuNumberlinkNurikabeRipple EffectShikakuSlitherlinkSudokuSuraromuYajilin.

Tags

September 2010

Mo Tu We Th Fr Sa Su
Aug |  Today  | Oct
      1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30         

Search

Latest comments

  • I like the appearance of the solution. :P Nice one. by Prasanna Seshadri on this entry
  • I think I've seen something vaguely similar in some of Palmer's puzzles as well. To be honest I've a… by on this entry
  • That's two puzzles in a row where I find something I had used before. I know, not plagiarism; just g… by Bram on this entry
  • Kota, that's not really true. I had made my puzzle before going to the WPC already. Also I don't hav… by Bram on this entry
  • About 20 minutes, after restarting from a mistaken conclusion. by Bryce Herdt on this entry

Copyright Statement

Puzzles published on this blog are licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 Unported License. Please leave a comment or send an email for more information.

Creative Commons License
Not signed in
Sign in

Powered by BlogBuilder
© MMXIX