Words to Fill Space

For the April 2012 issue of Puzzlebomb, I devised Hilbert’s Space-Filling Crossword:

The five clues lead to four four-letter words along the rows of the grid, and one sixteen-letter word snaking round the shape given by the thick lines. The puzzle gets its name from the shape traced out by the long word, which is the second iteration of Hilbert’s space-filling curve.

You can see that the curve ‘fills the space’ of the grid, in that it passes through every square. But lots of possible curves do that. What’s so special about this one? Well, the clue is in the phrase ‘second iteration’. Take a look at the first six iterations of Hilbert’s curve (illustration courtesy of Braindrain0000 on Wikipedia):

You can imagine the first curve passing through every square of a $2\times2$ grid, the second through a $4\times4$ grid (like in the crossword), the third through an $8\times8$ and so on. That’s what we mean by ‘space-filling’: the more intricate the curve gets, the more it gets into every nook and cranny of the square it lives in. Choose any point in the square, and the curve will pass through it if you iterate it enough times. Strictly I should point out that the actual definition of the curve is the infinite limit of this process of iterations which really does pass through every point of the plane, although of course it stops being a ‘normal’ curve at this point, and is rather a fractal.

Further, like all good fractals, each iteration of the curve is produced from the previous one by a simple rule. You just divide every square of the grid into four little squares, and draw the basic n-shape in each of the smaller squares, with the orientation determined by which part of the old ‘n’ lived in that square, then join up the ends (picture from Qef on Wikipedia):

When the crossword was released, I made the following bold claim (after noon, I hasten to add, so you can be sure I’m serious):

How can I be sure of this? Well, first let’s clarify my assertion. It doesn’t take much effort to produce the following baby space-filling crossword:

but I doubt anyone’s much impressed by it. And there are other space-filling curves that a puzzle could possibly be constructed around. But what I mean is, another crossword cannot be produced following the same construction as mine using a second- or higher-iteration Hilbert curve (I’ll allow the curve to be any way round in the grid). I know this because, in setting this crossword, I checked them all.

Clearly, the grid is entirely determined by the sixteen-letter word it contains (since the whole point of the exercise is that the word goes through every cell of the grid). But not many valid sixteen-letter words will give valid four-letter words across the rows when curled up into Hilbert’s curve (in any orientation).  What do I count as a ‘valid’ word? Well, it’s a somewhat subjective judgement of course, but I used the freely-available UK Advanced Crossword Dictionary as my authority. It’s based on The Chambers Dictionary, the single-volume dictionary with perhaps the largest vocabulary and the de facto reference work for the more fiendish of the newspaper crosswords. The UKACD lists words and compound phrases (which are commonly used in crosswords), so the possible sixteen-letter ‘words’ run from “ABERNETHY BISCUIT” to “ZOOPHYSIOLOGISTS”, taking in 2,342 options.

To construct the puzzle, I (by which I of course mean my computer) simply ran through each one of these and checked the rows in each of the four possible grids to see if they were words. Since I wasn’t sure there’d be an example where they all were, and reckoned I could probably bodge something alright together with a near-miss, I got the computer to tell me when three or more rows were hits. This process had a rather infuriating habit of overheating my laptop, but the result is that I can report that DRAMATIS PERSONAE comes close, as do DEVIL’S COACH-HORSE and BOTANICAL GARDENS, but the solution to the puzzle above is the only completely valid example that exists (and to boot, consists of four common four-letter words and one sixteen-letter word that, while hardly everyday, is at least in the more selective Collins dictionary). If you want to know what the elusive word is, you’ll just have to solve the crossword, or wait for the answers, which will be posted here when the May 2012 Puzzlebomb goes live (or write your own program to find it). And if only one $4\times4$ example exists, I’m willing to bet there’s no third-generation crossword out there either. So I hope you enjoyed my little puzzle, because there will never be another.

(Of course, I encourage you to try and prove me wrong, or construct something similar. Let us know how you get on in the comments.)

Puzzlebomb is a monthly collection of new types of puzzles, released via Twitter and here on the Aperiodical. Past issues of Puzzlebomb, and their solutions, can be found here. If you’ve invented a puzzle you’d like to submit for possible use in a future Puzzlebomb, contact @stecks on Twitter or email Katie.

• Paul Taylor

Maths graduate, inveterate crossword and general puzzle doer, uses brackets excessively in writing (sorry)

8 Responses to “Words to Fill Space”

1. Paul Taylor

Oh dear, you’re right of course. I’ll fix it when I have a minute.

2. Anonymous

Was stuck with the REDACTED – I was working on REDACTED!

(I’ve removed a very minor spoiler until the solutions are published — Paul

3. Corey Plover

Very nice construction Paul. If you extend your wordlist from the 2,342 possible 16-letter long words from UKACD and use the 150,000-odd possible 16-letter words and phrases from Wikipedia’s list of article titles, there are about 50 more possible constructs, though almost all of them contain very poor selection of 4-letter words.

A possible exception might be TETRABROMOETHANE (a chemical hydrocarbon, C2H2Br4), spelling BART, ROTE, OMAN and ETHE (plural of ethos). Another option with a nice 4-letter words selection would be SANGAMONIAN STAGE (the last interglacial period in North America) spelling SAGE, GNAT, ANIS (ANI is a type of bird) and MOAN.