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


- 5 comments by 1 or more people Not publicly viewable

  1. Jack

    Well, this one certainly feels unique to me, but I have the same misgivings and uncertainties about resolving uniqueness for numberlinks as you do.
    The 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.

    26 Sep 2010, 14:58

  2. Thesubro

    Unique.

    Great post, great puzzle.

    TheSubro

    28 Sep 2010, 04:03

  3. Thomas Snyder

    A basic problem you can run into is wrapping things around each other to be cute, not because one must wrap around the other. So one thing I do when constructing is to make sure for any pair (or triple …) X and Y, if a straight line between X and a straight line between Y intersect, then one has to wrap/avoid the other. I can use something like this on today’s 10×10 “Medium” Numberlink (10/10/10) to see that 5/6 and 7/8 must wrap one way or another. BY seeing one way the 7 wrapping around the 8 intersect the 4’s and the other it doesn’t, you get the work-in to solve the puzzle. If I try this view on your puzzle, I see that none of 6/5/2 need to wrap, so there are the alternate solutions that plagued your puzzle on the LMI test. I’m not sure if this is part of the special property, but it is something I look for where I’ve made obvious mistakes, by tying a slip knot that isn’t necessary.

    10 Oct 2010, 17:03

  4. 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!

    I’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…

    10 Oct 2010, 18:31

  5. Ronald

    Regarding puzzle #87
    The 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?

    25 Nov 2010, 02:44


Add a comment

You are not allowed to comment on this entry as it has restricted commenting permissions.

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