detuned radio
http://blogs.warwick.ac.uk/tcollyer
It buzzes like a fridge...
enGB
(C) 2014 Thomas Collyer
http://blogs.law.harvard.edu/tech/rss
Thomas Collyer
Thomas Collyer
Warwick Blogs, University of Warwick, http://blogs.warwick.ac.uk
120

Friday Puzzles #98 by Thomas Collyer
http://blogs.warwick.ac.uk/tcollyer/entry/friday_puzzles_98/
<p>I’ve been writing an awful lot of puzzles this week, but sadly for this blog (I still really hate that word by the way) most of them won’t be ready until, say, June. Most – not all! This little fella was a little too tame to be let out into the wild by itself, but I’m sure will be appreciated here. Certainly on my part, easy Numberlink make for less heartache regarding uniqueness (touch wood!). Enjoy!</p>
<blockquote>
<p><strong>#124 Numberlink</strong> – rated <strong>easy</strong> <br />
<a href="http://www.warwick.ac.uk/~marear/puzzles/124nl.png"><img src="http://www.warwick.ac.uk/~marear/puzzles/124nl.png" alt="" border="0" /></a> </p>
</blockquote>
<p>All puzzles © Tom Collyer 200911</p>
Friday Puzzles
Numberlink
Fri, 01 Apr 2011 00:01:20 GMT
Thomas Collyer
http://blogs.warwick.ac.uk/tcollyer/entry/friday_puzzles_98/#comments
094d73cd2ed863a0012f0e5d35961398
2

Friday Puzzles #91 by Thomas Collyer
http://blogs.warwick.ac.uk/tcollyer/entry/friday_puzzles_91/
<p>And so, dearest reader, we will once more traverse the logical minefield that is numberlink. I’m 95% sure that the solution I have in mind for this week’s puzzle is rigid to the point of being unique – which is interesting because at first glance it doesn’t seem like it should be the case.</p>
<p>I’m hoping very much that this ambiguity is what actually makes this a rather hard puzzle. Assuming that I haven’t bodged it, this is definitely not an easy, and probably rises above medium too – although I’m not a great judge of numberlink difficulty. And as always with numberlink, I think the most valuable feedback would be directed towards any potential multiple solutions anyway, so I positively encourage you to try and break this rather than worry too much about my grading…</p>
<p>And to think I was going to risk yet another comment free week by doing a kakuro! Maybe next week eh. Enjoy!</p>
<blockquote>
<p><strong>#117 Numberlink</strong> – rated <strong>medium</strong> <br />
<a href="http://www.warwick.ac.uk/~marear/puzzles/117nl.png"><img src="http://www.warwick.ac.uk/~marear/puzzles/117nl.png" alt="" border="0" /></a> </p>
</blockquote>
<p>All puzzles © Tom Collyer 200911</p>
Friday Puzzles
Numberlink
Fri, 11 Feb 2011 00:00:35 GMT
Thomas Collyer
http://blogs.warwick.ac.uk/tcollyer/entry/friday_puzzles_91/#comments
094d735829a72d04012e11a20a1c4d8e
3

Friday Puzzles #81 by Thomas Collyer
http://blogs.warwick.ac.uk/tcollyer/entry/friday_puzzles_81/
<p>First up – I’ll post this week’s puzzle – which is a fairly gentle nurikabe. It’s been a while since I had a nice and easy puzzle so I hope this pleases the more casual of my readers!</p>
<blockquote>
<p><strong>#107 Nurikabe</strong> – rated <strong>easy</strong> <br />
<a href="http://www.warwick.ac.uk/~marear/puzzles/107nu.png"><img src="http://www.warwick.ac.uk/~marear/puzzles/107nu.png" alt="" border="0" /></a> </p>
</blockquote>
<p>All puzzles © Tom Collyer 200910</p>
<hr /><br />
<br />
But let’s move on. I want to discuss the numberlink puzzles from last week, and in particular make a few remarks about uniqueness of puzzle. As regular readers know, my approach to numberlink uniqueness is to find a solution to given array of clues and then try and establish its rigidity.
<p>The first puzzle I’ll discuss is <a href="http://www.warwick.ac.uk/~marear/puzzles/106nl.png">#106</a>. Here is the solution:</p>
<blockquote>
<p><br />
<a href="http://www.warwick.ac.uk/~marear/puzzles/106nl_ans.png"><img src="http://www.warwick.ac.uk/~marear/puzzles/106nl_ans.png" alt="" border="0" /></a> </p>
</blockquote>
<p>The first intuition I have about numberlink rigidity is the idea of “unnecessary wrapping”. The general idea is to suppose you have a pair of clues A, and another pair of clues B – and draw the straight line between these two clues. If these two straight lines intersect, then it is clear that one of the solution lines joining the clue must wrap around the other solution line. Conversely, alarm bells should be ringing with any candidate solution if the straight lines are disjoint and yet one solution line wraps round the other.</p>
<p>It is a quick check with this puzzle to see that there is no such unnecessary wrapping. I haven’t rigorously proved to myself that this means the solution must be rigid, but I’d be very surprised if this wasn’t the case (with a few highly symmetric exceptions). Ok, fine, I haven’t got anything more to add to this at the moment so let’s move on.</p>
<p>Here’s what I had in mind (in black) with the original <a href="http://www.warwick.ac.uk/~marear/puzzles/105nlb.png">#105</a> I posted, together with (in red) where things go wrong:</p>
<blockquote>
<p><br />
<a href="http://www.warwick.ac.uk/~marear/puzzles/105nlb_ans.png"><img src="http://www.warwick.ac.uk/~marear/puzzles/105nlb_ans.png" alt="" border="0" /></a> </p>
</blockquote>
<p>So there are a couple of points to consider here. Firstly, look at that pair of 2’s, and the amount of what I’ve just defined as “unnecessary wrapping” it does! There’s something more than meets the eye going on here. The initial idea for the breakin to this puzzle was with the 1’s and the 5’s. A little spatial reasoning quickly suggests that one of the solution lines must go via the topleft of the grid, and the other along the bottom edge – so that the cluster of 3/4/6/7 is avoided.</p>
<p>A little more inspection reveals that the 1’s would be causing all sorts of difficulty with the 6’s if it went out top left, so the 5 goes round the top left. It was here that I made the mistake. I thought there was only one way for the 5 to get past the 4 and the 6, but completely overlooked the obvious route as marked in red. This was how I fixed the puzzle – by closing up the gap (and adding a 13th pair of clues):</p>
<blockquote>
<p><br />
<a href="http://www.warwick.ac.uk/~marear/puzzles/105nl_ans.png"><img src="http://www.warwick.ac.uk/~marear/puzzles/105nl_ans.png" alt="" border="0" /></a> </p>
</blockquote>
<p>This alteration made the puzzle a little easier than intended. The 3/4/6/7/13 are now essentially forced. A by product of this is that it forces the 2 to squeeze the “wrong” side of the 1. This is a bit of “logic” that only came in to play later in the original – but essentially reveals the origin of the “unnecessary wrapping” of the 2. The given clues in the puzzle are acting as blocks to the paths, which must channel in between them, with the obvious restriction that there are only so many paths that can fit into a small space. So once the 2 goes round the back of the 1, it also has to go round the back of the 8 and the 9.</p>
<p>The rest of the puzzle is then fairly trivial.</p>
<p>What I find interesting with this puzzle is that actually it wasn’t too hard to find a sketch framework to logically prove the solution is the only one. Ok, I’ll hold my hands up with the stupid oversight with the 5’s, but the fix was essentially minimal and still retains most of the features I wanted from the original puzzle.</p>
<p>Going back to #106, I think this one is much harder to make a start to the puzzle and go step by step in trying to establish forced paths. Instead, it isn’t too tricky to use a little metalogic (i.e. assuming uniqueness of the solution) to get the solution out – and then to do a quick check to see that this solution turns out to be rigid. Which is a completely different approach to things!</p>
<p>Anyhow, for all those numberlink fans out there, I hope this has provided a little food for thought.</p>
Friday Puzzles
Numberlink
Nurikabe
Fri, 03 Dec 2010 03:28:13 GMT
Thomas Collyer
http://blogs.warwick.ac.uk/tcollyer/entry/friday_puzzles_81/#comments
094d735829a72d04012caa45da875282
0

Friday Puzzles #80 by Thomas Collyer
http://blogs.warwick.ac.uk/tcollyer/entry/friday_puzzles_80/
<p>More Numberlink this week. Over the week I’ve pretty much convinced myself the solutions I have in mind really are the only ones, and I’ll go into this more maybe with an edit to this post in a few days. What I’ll say for now is this. I reckon the second is a much nicer puzzle than the first, but the first was definitely more easy for me to convince myself of uniqueness.</p>
<p>This seemed rather strange to me on second inspection, as it turns out that it has a few properties that I had previously thought might have been barriers to uniqueness. In particular, it fails a test I’ve devised to check whether if you have one solution, then you can only have one.</p>
<p>This test was something I came up with when inspecting the second puzzle again. I haven’t rigorously proved this to myself but it does make intuitive sense. The second puzzle does pass this test.</p>
<p>Anyhow, my apologies for being so cryptic – but be assured dearest reader that I am only because I don’t want to spoil the solving experience, and also with the promise of explaining all in a few days time. Until then, enjoy!</p>
<p><a href="http://www.warwick.ac.uk/~marear/puzzles/105nlb.png"><strong><span class="caps">UPDATE</span> (II): <span class="caps">PUZZLE 105 EARLIER CAME WITH A SPECIAL OFFER OF MANY POSSIBLE SOLUTIONS FOR THE PRICE OF ONE</span>!!!</strong></a></p>
<blockquote>
<p><strong>#105 Numberlink</strong> – rated <strong>easy</strong> <br />
<a href="http://www.warwick.ac.uk/~marear/puzzles/105nl.png"><img src="http://www.warwick.ac.uk/~marear/puzzles/105nl.png" alt="" border="0" /></a> </p>
</blockquote>
<blockquote>
<p><strong>#106 Numberlink</strong> – rated <strong>medium</strong> <br />
<a href="http://www.warwick.ac.uk/~marear/puzzles/106nl.png"><img src="http://www.warwick.ac.uk/~marear/puzzles/106nl.png" alt="" border="0" /></a> </p>
</blockquote>
<p>All puzzles © Tom Collyer 200910</p>
Friday Puzzles
Numberlink
Fri, 26 Nov 2010 01:37:23 GMT
Thomas Collyer
http://blogs.warwick.ac.uk/tcollyer/entry/friday_puzzles_80/#comments
094d735829a72d04012c85d3de554097
4

Friday Puzzles #71 by Thomas Collyer
http://blogs.warwick.ac.uk/tcollyer/entry/friday_puzzles_71/
<p>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.</p>
<p>Let me put it like this: Numberlink.</p>
<p>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:<br />
<a href="http://mellowmelon.wordpress.com/2010/07/24/numberlinkprimer/">http://mellowmelon.wordpress.com/2010/07/24/numberlinkprimer/</a></p>
<p>Of course, this provides the author of a Numberlink puzzle with a headache – after all, you can’t use the same solving metalogic or you might end up with something like this:</p>
<p><a href="http://www.warwick.ac.uk/~marear/puzzles/badnumberlink.png"><img src="http://www.warwick.ac.uk/~marear/puzzles/badnumberlink.png" alt="" border="0" /></a></p>
<p>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 wriggleroom 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.</p>
<p>Nevertheless, I am convinced there is some logic dictating the uniqueness of a Numberlink solution. My proposed statement goes something like:</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>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 wrigglingroom – to get a new solution from it.</p>
<p>One particular example was supplied by Andrey Bogdanov via the <a href="http://forum.ukpuzzles.org/viewtopic.php?f=3&t=41#p670"><span class="caps">UKPA</span> forums</a> – a truly excellent resource – which means that the statement has to say something about symmetry, and what Topologists might call hyperelliptic involutions!</p>
<p>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!</p>
<blockquote>
<p><strong>#087 Numberlink</strong> – rated <strong>medium. Maybe.</strong> <br />
<a href="http://www.warwick.ac.uk/~marear/puzzles/087nl.png"><img src="http://www.warwick.ac.uk/~marear/puzzles/087nl.png" alt="" border="0" /></a> </p>
</blockquote>
<p>All puzzles © Tom Collyer 200910</p>
<p>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 :)</p>
Friday Puzzles
Numberlink
Fri, 24 Sep 2010 11:39:48 GMT
Thomas Collyer
http://blogs.warwick.ac.uk/tcollyer/entry/friday_puzzles_71/#comments
094d735829a72d04012b438abffc5747
5