All entries for 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 :)
September 19, 2010
If you don’t want to read on, then this picture sums up my fortunes rather neatly:
Circled is a closed subset of wrongly permuted digits that ruled me out of the grand final of the 2010 Times National Sudoku Championship. Instead, the deserving winner of the Championship was George Danker, who correctly solved the four puzzles of the grand final in the fastest time. In second place was two-time champion Nina pell, and in third was Mark Goodliffe – the current Times Crossword Champion.
The Longer version starts here.
I popped on a train down from Coventry to Euston on the morning of the championship, joined by Andy at Milton Keynes. After stopping off at the M&S food place at Euston to buy some lunch and a water bottle, we made our way to the Institute of Education – handily located about 5 minutes away. Once inside, it was excellent to catch up with a few familiar faces – first up was fellow WSCer George Danker together with his supporting entourage of his parents and girlfriend Sophie. We were joined by Mike Colloby, and crossworders Simon Anthony and Mark Goodliffe (see their website http://www.piemag.com/ if you like that sort of thing). I always feel a bit sorry for the other people before the event, because they generally are sat down looking very nervous, perhaps solving a puzzle or two, but mostly all in awkward silence. I hope they comforted themselves with the goody bag, which also included a card advertising the forthcoming UKPA Sudoku Championship as well as a newspaper. As ever, the bit with the sudoku was curiously absent.
Anyhow, onto the first preliminary. The format, same as ever was one hour to do four puzzles. I made sure to get a desk at the front, for minimum of distraction, and couldn’t well resist taking the desk numbered 81.
I started this round well, cleanly getting out the first puzzle. I hit a bit of a sticking point with the second, so decided to move on. This wobble started to pronounce itself as I messed up the third puzzle fairly early on into the puzzle – no matter, deep breath, bit of rubbing out, out it comes cleanly. Phew. Puzzle four was the best yet, whizzing through with no hitches, leaving me just to get on with the second. I couldn’t see anything in the notation I’d already put down, so after maybe a minute I decided to take a punt and guess. This seemed to working beautifully, until I realised at the end that there was an apparent uniqueness issue. Alarm bells start blazing in my head, and the only option was to go nuclear with the rubber. This had the relieving effect of showing an obvious resolution of the 28 pair in the third row. Rest of the puzzle comes out cleanly, and I declare in 8th place in a time of around 24 minutes, having performed my checking routine of checking for unfilled squares. I was unsure about the time, but this is what George reckoned having declared a few seconds earlier.
This was pretty slow by my own standards, but I was only really warming up, and the lost time was easily explained away by my wobbles. My solving speed was good, and this was the main thing. In the break I was glad to have a chat with Simon who said that I wasn’t the only one to have had a hiccough – he reckoned he had solved six and a half puzzles in the first part. For the rest of the break I settle down on the floor with Andy and read a bit of the paper
The second part of the preliminary was much the same, four puzzles to do and an hour to do them in. This time I was ready to regain a bit of face, and this was the case as I caned up the first puzzle, being fairly sure that mine was the first fiddling about with the paper to move onto the second puzzle in the room. Again with the second puzzle I start well, but then hit a hitch. No matter, move onto the third. A similar story, and was about to go onto the fourth until a spot something fairly clever with either pairs or triples, and the puzzle then fell pretty quickly. On to the fourth – I get through this quite quickly, but see a conflict with a 5 right at the end. Balls! I start rubbing out, started again – then saw where the error lied in my first attempt! Easily corrected and so with the imprints of my first go still there I hastily put the numbers back in. It seemed to solve fine. OK, back to the second – again I saw what I was missing and quickly blitz through this too. A quick check for empty squares reveal a couple in the first puzzle – fill them out, and again I declare.
I initially reckoned this must have been in 15-20 minutes, but Mark Goodliffe reckons that was more the timespan he got the second set done in; I had finished a long way ahead of anyone else in the room, making my time closer to 10 minutes. Which if true would be a time competitive with any Sudoku solver in the world. At any rate, it left me with a lot of time sat at my desk. As with the first preliminary, I spent this making 10×10 puzzles in the notebook that came in the goody-bag. Cumulatively, I now have a good collection of Masyu and Nurikabe to publish here at a later date!
Back to the narrative. The end of the second preliminary drew close and David Levy was ready to announce the 8 grand finalists. Having only been 8th in the first part of the preliminary, I was expecting to hear my name fairly early on. I was pleased to hear the names of Mark Goodliffe in 6th place, and George Danker in 5th. When I heard that there was a three-way tie for 2nd place, I thought this had to me. First name was read out. Shoot. Second, again not me. Third – Nina Pell.
Shit shit shit. Shiiiiit. I couldn’t possibly have been first could I?
No. That went to Stephen Gerrard.
Not again! Not again not again!
In retrospect, it is plain to me that the error must have been on that fourth puzzle, which I hastily redrew the numbers in for. I must have copied over one bad egg or something. I should have checked it more thoroughly. Caning up the entire room by a clear 5 minutes, and I hadn’t checked carefully. What an absolute idiot!
After the finalists were congratulated, David Levy mentioned that if anyone who expected to place higher (me) then they should come over and the error of their ways was to be pointed out. I duly did so, at this point convinced I had screwed myself over, and asked “I’m sure that I did make a mistake, however I’m curious as to where it was”. What I saw was the picture above, indeed from the fourth puzzle.
In retrospect, I think there are two parts to the reasoning as to why I hadn’t checked my second preliminary set more closely. The first is that when solving on paper, I normally catch my errors when solving, and restart. The most likely thing I will do to mess up is simply leave cells blank. I have learned this from previous years, and now make sure to do an empty cell check in all competitions. In short, I felt I had done enough checking. The second part to the reason is far uglier. On the way to winning last year, I had placed 7th in both parts of the preliminaries; solidly and unspectacularly. Having been 8th in the first part this year, I wanted to make my mark. Simon had mentioned that with regards to my nikoli times, I was certainly getting faster. In short then, I hadn’t wanted to the statement I was making to the room to be watered down by spending too much time checking.
Whilst the second half of this reasoning probably smacks of hubris, I think it is only fair to mention that the first half of the reasoning is crucial to this too. With my current procedure, I reckon I catch 80-90% of my potential dickhead errors.
After having finished with the judging team, I had a quick word with the photographer, who seemed familiar from last year but as it turned out wasn’t, and mine was a common enough mistake! Apparently she had taken enough photos of me to warrant taking my details, and overall seemed a good sport. I also shared some kind words with regular reader David Collison, which was very nice!
I decided to stick around for the grand final – firstly because my good friends George and Mark were involved, and secondly because I wanted to start the cathartic process by solving alongside them. I wished George all the best, hoping that he’d win to maintain the integrity of the UK WSC team from April. Mark mentioned that as always, he didn’t think he had the raw speed of the likes of George or Nina, but was going to maximise his chances via a bifurcation strategy – much as he had done in 2007 when he reached the final. I think the common consensus at this stage was that Nina was probably the favourite. At this point I was engrossed enough with what was to come that my own failings didn’t seem to matter too much. After all, I’ve one this twice before – and mistakes happen to the best of us!
So, on to the final. Firstly I’ll state that the puzzles were pretty tough – a little harder than what are published as super-fiendish these days. Whilst I was a little slow in places, I generally had no problems with the puzzles (I have always thought that generally my advantages as a sudoku solver are exaggerated by harder puzzles), working through them fairly rhythmically although a little stickily in patches, getting them out in 21 minutes, as timed by Simon who had also stuck around for the final. I reckon this was a little over par by my standards, although I think I’ll post them up later if people are interested to see how their times stand up.
The action with the grand finalists was intriguing, with the apparent difficulty of the puzzles being reflected in the faces of the competitors, together with the regular sound of someone rubbing out and presumably start a puzzle over. Mark was the first to declare – something of a shock – but apparently his bifurcation strategy had paid off handsomely. A little while – perhaps four or five minutes later – after him, George then finished, looking a little resigned. Again there was a gap of a few minutes, before Nina finished. I sort of switched off a bit here – focussing on finishing off the slitherlink puzzle I was writing.
The twist was to come after the time was up. Of the eight papers, David Levy announced, only two had all of the four grids completed correctly. Not what you wanted to hear at all! Moreover, it took what seemed like an absolute age before the results were clear, and the final standings announced. The big gasp came as Mark was announced as third place – indicating that the final two placings were Nina in second, and George as champion.
I tried to make eye contact and give him a big thumbs up. With all respect to Mark and Nina, I am glad that George did win. Having solved side by side with him in Philadelphia at the Worlds last April, I can safely say he is a top notch solver with a bright puzzling future ahead of him. This kiss of death now perhaps, but if he decides to compete I think he’s the clear favourite for the UKPA championship too. Most definitely a worthy champion!
It was also announced that the third puzzle of the set was the hardest – this seemed to be confirmed by the experiences on the sidelines; both Andy and Simon had gotten stuck at exactly the same point. Rather frustratingly, I couldn’t see where to point out the next step in the puzzle, despite having made pretty easy work of it minutes earlier. After about 10 minutes, I finally saw the blaringly obvious – a 179 triple in the 6th column.
We stayed for the presentation – interestingly enough the junior (best finish for 15 and under) was awarded the same prize as everyone else – a Time atlas of the world to which I could only think what does a 15 year old want to do with that? After exchanging a few last pleasantries with Simon, Mark and Nina, that was that – I headed off. One last regret was apparently missing Times journalist and most excellent drinking buddy Jack Malvern for all the journalisty bits. I shall have to keep waiting for the appearance of the phrase “brain fart” in Britain’s most reputable newspaper.
There’s always next year – my record so far is: 06 beaten by David McNeill; 07 won; 08 defeated by myself with a massive brain fart; 09 won; 10 again defeated myself with a dickhead error; so hopefully things look good for 2011! Thanks for reading!
September 17, 2010
So this week time has somewhat ambushed me and I don’t really have anything brilliant to share. Given that I’m going to be busy at The Times national sudoku championship over the weekend, I can’t really cop out and offer to post something up later either. Do expect another hideously long and boring report coming soon. Haha…
So what I’m left with is basically the beginnings of an idea that will hopefully get off the ground after the official UK Puzzle Association’s 1st Sudoku Championship/Competition. No harm in a shameless plug, even though there a few things left to be sorted out there. Anyhow, back to the idea. What we have is a Standard Sudoku, only I’m telling you that exactly three (3) of the given clues are wrong. You can probably tell this is very much an initial concept puzzle, but it’s the best I’ve got this week – sorry!
Also (with a seamless change away from personal failings), last week I also forgot to plug the latest issue of Dr. Gareth Moore’s Sudoku Xtra. The latest issue (#10) features a wide selection of good puzzles from Gareth + more – including a Sudoku Islands puzzle from yours truly. Definitely recommended!
All puzzles © Tom Collyer 2009-10
September 10, 2010
So this week I’ve decided to keep playing with the alternative presentation of Yajilin. My argument at this stage is that this really isn’t a stand-alone Yajilin variant, and to reply rather lately to the comment MellowMelon made on the last post that yes, I agree that in general it isn’t too hard in filling up the grid with “useless” clues. With this presentation, I could indeed have gone through that process this week, but there are two main reasons why I’m serving you up the following.
Firstly I couldn’t be bothered. What can I say, maybe I’m lazy, maybe I just need the right motivation. But secondly, I think the shaded squares add a certain something to the aesthetic appeal of the puzzle over, let’s face it, is otherwise a rather barren looking grid.
Certainly, this is a different sort of solving experience going on here, working out the claustrophobic implications of the narrow passage ways than you’d see in your average Yajilin puzzle, but I think it must be reiterated that it’s an easy job to put these back into “standard” presentation.
But you’re probably getting bored reading all that, and would much prefer some puzzles to solve. Enjoy!
[My apologies for inconsistent and unsolvable early versions of #084. For the record, the top left clue went from being unmarked, to being a 0, and finally to its correct status as a 2:)]
All puzzles © Tom Collyer 2009-10
September 03, 2010
For this week’s puzzle, I’ve decided to have a little play with Yajilin, and its presentation.
A problem I quickly ran into was with how the clues have an effect on the puzzle. It wasn’t too long into making this that I had a nice symmetric pattern laid out in the grid, and a few clues in place. As I continued putting in more and more clues, it became increasingly obvious that I wasn’t going to need all the marked squares for clues that I’d set aside. However, I also realised that I couldn’t simply throw them away (for one thing, think of the symmetry!). But more importantly, because the rules of Yajilin say that you have to use every square in the grid, these as yet clueless squares were still playing a crucial role in the solving process.
As such I’m going to throw you two versions of the same puzzle, presented slightly differently. For the first, I filled in the the clue squares I needed, sometimes ridiculously, and sometimes a little more obscurely, all the time trying not to introduce too many logical short-cuts into the puzzle.I am not sure then, that despite having more information in the first version, whether actually the second is a nicer solve.
Note in this version that you can shade in a square directly adjacent to a blank grey square, although the loop definitely cannot enter these squares. Also note that the the grey squares aren’t included in the count of the to-be-shaded squares.
I’m hoping I’ve deleted the right clues, although I suppose it’s not the end of the world If I’ve gone too far. I think it should work out that there are probably still one or two technically surplus clues hiding in there.
All puzzles © Tom Collyer 2009-10
September 02, 2010
Nope, not this week’s puzzle just yet, it’s still Thursday (just)!
Anyhow, no doubt exasperated with my makeshift attempts to post up the last two Friday Puzzles – which I might add for my own moral satisfaction were drawn up and on the camera on time – David Millar of The Griddle took matters into his own hands and drew them up, undoubtedly to make the solving experience a little easier than working from those photos!
Anyhow, he has very kindly shared these with me, and saved me the bother of drawing them up myself!
Thanks again David!
Again, apologies for the delay!
Apologies for the delay!