Occasionally something diary-worthy happens to me which never quite gets written down in here, because it happened so gradually that there was no point at which I could look back and decide it was obviously over and hence able to be written about coherently. Earlier this week, a conversation at post-pizza reminded me of just such an incident from the year before last, so I'll write it up now on the basis that it's better late than never.

In mid-2005 my puzzle collection acquired a game called Map, in which you are given a map with a partially specified four-colouring, and your task is to reconstruct the full four-colouring (of which there is one unique one which satisfies the provided clues). In order to automatically generate such puzzles, my plan was to create a map, four-colour it, and then gradually un-colour regions in order to create a puzzle of the desired difficulty. Step two of that, of course, needs an algorithm which four-colours a map.

The simplest algorithm that does the job is a recursive one. Given a map, pick an uncoloured region, iterate through all the colours for that region which don't already conflict with something else, and for each possibility recurse into the remaining regions, stopping as soon as an answer appears. You can speed this up hugely by choosing, at every stage of the recursion, the currently most constrained region to iterate over next; this prunes the search tree early and often, and although the worst-case performance is still exponential in theory, this technique turns out to be able to handle puzzle-grade maps without becoming unreasonably slow.

But I've never been a fan of algorithms which have a hideous worst case but are OK in practice. So during my initial research for this puzzle, I googled around to see if I could find a four-colouring algorithm with a more sensible time complexity, and was pleasantly surprised to turn up one that claimed to run in O(N^2) time.

The algorithm was a by-product of a proof of the four-colour theorem. Apparently the original 1977 proof had included an O(N^4) algorithm, but more recently a bunch of four mathematicians re-proved the theorem using fewer special cases and more verifiable computation, and as a side effect managed to improve the associated algorithm to be quadratic rather than quartic. Unfortunately, this meant the algorithm was also described in terms of high-powered graph theory some way beyond my fluency, so the paper didn't really give me enough details to implement it.

So I mailed one of the authors of the paper and asked if he could clarify some details for me. He replied, in what felt like a rather patronising tone, that he didn't think his algorithm would be much use to me because it was hard to implement.

Well, I'm not scared by that. I'm pretty good at implementing strange algorithms, even algorithms which I've been warned not to try because they're too hard. For example, when I was doing my DipCS, the Algorithms lecturer warned an entire roomful of Cambridge students that they should on no account attempt to implement a B-tree library, because they would be picking bugs out of it until Judgment Day and it would never become stable enough to be useful; since then I've ignored that advice two and a half times with no obvious ill effects, and one of the resulting B-tree libraries has been extensively used in PuTTY for many years now and has contributed virtually nothing to the rate of bug reports. It was indeed fiddly and did take some very careful and thorough testing, but I did it. So while his warning was probably not an unreasonable thing to say to a completely random person who'd just emailed him announcing an intent to implement his algorithm, I decided that if anyone could have a decent go at the job regardless then I could.

So I persisted, and we discussed the details of the algorithm, and gradually – so gradually that I never got round to writing this post about it – it became clear to me that despite my self-confidence he had in fact been right.

A basic sketch of the proof of the four-colour theorem goes like this:

• Here is a ginormous appendix listing about six hundred small fragments of graphs.
• Given any planar graph (which has had some simple preprocessing done on it), you can guaranteeably find one of those fragments somewhere in it. Proof by exhaustive computer search.
• Given a graph which contains one of those fragments, you can reduce it to a slightly smaller graph, in such a way that if you are then presented with a four-colouring of the reduced graph you can transform it back into a four-colouring of the original graph. Details of exactly how to do this for each of the 600 fragments are given in the ginormous appendix.
• All sufficiently small planar graphs can be four-coloured, simply by virtue of having at most four vertices.
• Hence, essentially by an induction-like argument, any planar graph can be four-coloured.

The four-colouring algorithm precisely follows the structure of the proof: given a (preprocessed) graph, we search for one of the 600 fragments in it, which we turn out to be able to do in linear time by applying cleverness. We then construct our reduced graph (still in linear time), recurse to four-colour that, and (in linear time) transform the four-colouring of the reduced graph into one for the original graph. Since each recursive step takes O(N) time internally, and each recursive step removes at least one vertex from the graph so that there can be at most N recursive steps in total, this leads to a quadratic-time algorithm, as promised.

Unfortunately, this also leads to some rather undesirable properties of the algorithm:

• It has quadratic space cost as well as quadratic time. Each recursive step has to construct a slightly reduced version of its input graph, and as best I could tell it pretty much has to construct it in entirely separate memory rather than subtly modifying the original graph data structures. Quadratic space cost is really hideous; I can't think of any algorithm in common use which has it.
• Its linear-time recursive step has an extremely large time constant. It has to search the graph for one of 600-odd small graph fragments, which is going to take 600 times however long it takes to find one fragment. And before that it has to compute a quantity called ‘charge’ for each vertex of the graph, which is done by another nasty graph-pattern-matching step, and which is vital to knowing whether you've found your fragment or not. Meanwhile, even finding one fragment is painfully slow: you have to essentially iterate over all edges of your input graph and ask ‘Suppose this edge of G corresponded to a given edge of my fragment F; can I then match up the rest of the edges and vertices of F without finding a mismatch?’.
• Perhaps worst of all, it isn't sensibly testable. The set of 600 fragments has been proved to be sufficient to guarantee that one can be found in any graph, but hasn't been proved to be necessary. The guy I corresponded with, in fact, was of the opinion that it might easily be that only 20-50 of them were actually required; he just hadn't managed to prove it. So you end up with 600 special cases in the algorithm code, but you can't construct a set of test inputs which between them exercise more than a small fraction of those special cases. This is a recipe for unreliability.

Once that lot became clear, I abandoned the idea of implementing the algorithm. I still think my original self-confidence was reasonably justified, in that I could make pretty much as credible an attempt at the job as anyone. It's just that given the first two points above, I think no sensible programmer would want to use such an algorithm in production code even if a working implementation was handed to them on a plate; and given that point three then stands in the way of producing that working implementation in the first place, it's just not a feasible project at all.

So the current version of Map still uses the simple early-pruning recursive algorithm; and the story stands as a cautionary tale with the moral that even if you have my antipathy to cowboy algorithms like Quicksort and hash tables, just occasionally the worst-case asymptotic time complexity of an algorithm can still be a vanishingly small concern compared to other considerations.