Listen With Others

Are you sitting comfortably? Then we'll begin

Listener 4114, Three-Square: A Setter’s Blog by Elap

Posted by Listen With Others on 19 December 2010

The Theme

I can’t remember having seen a puzzle which was based on triangular numbers, but I’m sure there must have been some. It is impossible to fit perfect squares into a ‘crossword-sized’ grid with all digits checked (there are simply not enough numbers of each length), but triangular numbers are a different kettle of fish. It was time for a triangular numbers puzzle.

Feasibility

I had calculated that whatever the size or shape of a ‘crossword-sized’ grid which has all of its squares checked, the grid can be filled with different triangular numbers in only one or two ways on average; there may be no ways, or there may be two or three or even more ways, but on average there will be between one and two. The calculation was done by analysing the distribution of digits in each position of the numbers and calculating the probability that crossing numbers would fit in with each other. I wrote a program to do this, and the results were in line with my rough calculations. As soon as the number of rows plus the number of columns is greater than 23, the expected number of ways becomes less than 1.

The expected and actual number of ways in which grids can be filled with different triangular numbers is as follows (I have yet to determine the actuals for the 8 x 9 and 9 x 9 grids):

I didn’t consider an 8 x 8 grid to be quite large enough for the puzzle, but I calculated that it would take hundreds of years to fit numbers into a 9 x 9 grid, even using the fastest computer – and with the possibility of it being impossible!

The construction of an 8 x 9 grid would have taken about five months for my computer to attempt, again with the possibility of no solution. I actually tried it for 2½ months early in 2009 but decided not to pursue it, having not found a solution. Indeed, I had to replace the computer’s power supply fan during the attempt because it wore out. Out of curiosity I will finish the run at a later date.

Grid Design

Fitting the numbers into a grid which consisted of triangular cells was a non-starter, and so I had to figure out a way to use a traditional squared grid. The only way forward was to have some unchecked squares. This had two major advantages: it was practicable to construct the grid, and it would result in a puzzle in which unchecked squares could be completed by the solver as part of the theme.

I was aiming for a grid with a solid block of crossing triangular numbers – something with a ‘wow’ factor; something which some solvers would dismiss as being impossible – and so I decided to have a few squares sticking out around the grid rather than bars or black squares inside it. Filling the grid would be that much easier with the presence of unchecked squares, and so I decided to aim for a 9 x 9 block with extra squares so that there were some 11-digit numbers. I would have preferred the first grid below, but it would have taken up to a few years to try to fill it with triangular numbers – with the possibility of it being unsuccessful – and so I compromised by settling on the second grid:

The Computer

I knew that the filling of this grid would involve a huge amount of processing (even given that there would be over a million ways of doing it), and my PC was a few years old. I strolled along to my local PC World (in August 2007) and happened to see a quad-core PC at an affordable price. Dual-core PCs had been around for some time, but I didn’t know that quad-core ones existed. This was a good omen.

I use an 18-year-old 16-bit Borland Pascal compiler which runs under DOS – ideal for me because I don’t want the overheads of a graphical interface for what is essentially data manipulation, and anyway I don’t enjoy Windows programming – I’m an old fogey who wants all the code in one place! With this PC I could partition my processing into four concurrently running Command Prompt sessions. The result was that it would effectively run at 7½ times the speed of my old 2.6GHz single-core PC. The manager at PC World was quite amenable to me running a program (one that created a 7 x 7 grid of triangular numbers) on the PC to confirm the speed improvement. The PC was up and running in my study that afternoon.

Filling the Grid

There is no short cut which can be used to fill a grid with numbers from a given set (or a grid with words, come to that).

The programming was a challenge. There are 30,579 nine-digit triangular numbers and 305,793 eleven-digit ones. At first sight the task looks daunting, even for a fast computer: for each of the 30,579 nine-digit numbers which are to be tried in the first row, all possible numbers which have a matching first digit must be tried in the first column. For each of these two combinations, all possible numbers must be tried in the second row. For each of these three combinations, all possible numbers must be tried in the second column, and so on. As the nested looping increases, the total number of combinations to be tried becomes astronomical.

There are five ways to reduce the running time of a program. One is to use more than one computer (for various reasons I didn’t want to do this); another is to use a faster computer, and that had been acquired. The third is to use a better algorithm, and the fourth is to improve the efficiency of the coding. The fifth way – and this is really important – is to make sure that the data is in a format which can be processed efficiently.

Most of the effort was concentrated on improving the algorithm. Every few days I would think of a new way to speed things up, sometimes cutting the processing time by 80% or 90%, sometimes by 10% or 20%, but more usually by just a few percent. However, the biggest time-saving was related to the data (ie the triangular numbers) and was achieved as follows:

Take a simple word square (all the letters are different so that the example will be clear – that’s why I’m using letters for this example instead of digits). The words used are:
        CLAW, DOCK, DUTY, KIPS, OGRE, TRAP, UGLI and YEWS.

Now rearrange the letters – order by the 3rd, 1st, 4th and 2nd letters, say:
        ACWL, CDKO, TDYU, PKSI, ROEG, ATPR, LUIG and WYSE.

Create a word square from these ‘words’:

Now restore the row order:

Finally, restore the column order:

The point is that reordering the letters in the words, then fitting the new ‘words’ into the grid, and then restoring the original letter order in the words, works. And, of course, it will work with digits as well. There will, however, only be a speed improvement if the distribution of digits in a given position of the numbers is skew – which it is for triangular numbers – or if the numbers of combinations of adjacent digits in the numbers are less than if the digits were random – which again is true for triangular numbers (there are only six different last digits out of a possible ten, 44 different combinations of the last two digits out of a possible 100, and 424 combinations of the last three out of a possible 1000).

This method was used to great advantage when fitting numbers into the Three-Square grid. Triangular numbers can only end in the digits 0, 1, 3, 5, 6 or 8, and the last few digits have a limited number of combinations as mentioned above. These constraints needed to be taken advantage of as soon as possible in the fitting, and so it made sense to reverse all the numbers before they were fitted into the grid. Also, there are 10 times as many 11-digit triangular numbers as 9-digit ones, and so the 11-digit ones needed to be fitted last (because most of the time the fitting would not reach this far). The rows and columns of the grid were therefore rearranged as follows to match the rearrangement of the digits in the triangular numbers:

Fitting the numbers into the second grid above took a tiny fraction of the time it would have taken to fit them in the first grid (I mentioned earlier that I ran a program at PC World to test the speed of my computer before I bought it. That program took 110 seconds to find all ways of fitting triangular numbers into a 7×7 grid, using the numbers with their digits reversed. If the digits had not been reversed, the same program would have taken just over four hours to complete).

I used every trick in the book, and many more besides, to maximise the efficiency of the program. Some of the code was cumbersome as a result, but this was justified by the speed improvement.

In the final version of my program I had developed an algorithm which had greatly reduced the exponential nature of the nested loops, and the coding had been optimised, much attention being paid to the areas where the program spent most of its time. The final version of the program fitted 48,000,000 numbers (not digits, but numbers) each second (taking advantage of all four processor cores) and, on average, produced a filled grid every 4½ days, each one requiring the fitting of 18 trillion numbers.

I ran the program continuously for a month and it produced seven filled grids. A couple of them had a very skew distribution of digits, but one of the remaining ones had a nice feel about it and that is the one I chose for the puzzle. From the puzzle’s conception to the production of these grids (November 2007 to April 2008), my computer consumed over 200KWh of electricity, and at times my study was noticeably warmer than the other rooms in the house. My wife was convinced that I was bonkers.

The Clues

I wanted the solver to fill in some squares of the grid as part of the theme. I had various thoughts, then hit on the idea of having shaded triangles in three corners of the grid, each consisting of six squares (three and six being triangular numbers of course!). I also wanted to introduce a new type of cluing notation. Even before designing the grid I had decided that I didn’t want black squares or bars, and decided that each grid entry would be indicated by its starting square, direction and length. This would enable the overlapping of grid entries, thus adding another dimension to the solving process.

But what form would the clues take? I wanted the triangular numbers theme to be hidden until the final stage of solving, but how? I pondered over this for a few days and became quite despondent. I then decided to search Chambers for definitions containing “triang” – and I hit the jackpot. There it was:

three’-square adj having an equilateral triangle as a cross-section.

Why, it was even a loose cryptic indication of crossing triangular numbers!

I was on a roll now. Some clues could be based on threes, some on squares, and some on triangles. Originally, I was going to involve right-angled, isosceles and scalene triangles, but I decided that isosceles triangles really weren’t very interesting.

Threes

These clues were to be expressions which evaluated to numbers consisting only of threes. I wanted only three (of course) variables in each and only addition or multiplication involved – clues which involve subtraction or division don’t tend to be very useful for ascertaining the ranges of the unknowns. The expressions were therefore to be of the form ABC, AB + C or A + B + C, where A, B and C were grid entries. My program produced 676 possible clues.

Squares

I decided that each of these clues would refer to three grid entries and would be of the form A + B = C2. There were 353 to choose from.

Right-angled

Originally I was going to make each clue the sides of a right-angled triangle followed by its area, but decided that just the three sides would be adequate. For elegance, I wanted only primitive triangles – ones which are magnifications of others I find unsatisfying. I didn’t want a side which had more than three digits, and there were 158 triangles which fitted these criteria.

Scalene

Ever since my schooldays, I have been fascinated by Heron’s formula. It is so elegant. If the sides of a triangle are a, b and c, and s is half the perimeter, then the area of the triangle is:

s(s-a)(s-b)(s-c)

Isn’t that beautiful? What I find fascinating is that, for integral areas, there is an even number of each prime factor in the radicand. It makes for some interesting clue-solving.

I decided that each clue would consist of the sides of a scalene triangle followed by the area. Again, I wanted only primitive triangles. My program produced 5,675 triangles. I was very pleased to find three large triangles whose area could be a grid entry, two of them having five digits and one of them four.

Selecting the Clues

Having produced text files containing the universe of clues, I looked through all of them manually for a starting point.

Once the starting point had been decided upon, the next clue had to use some of that information, and by searching the text file which contained the possible clues, another one was chosen. This process was repeated as many times as necessary. After the clues had been created, they had to be gone through to make sure that there weren’t any superfluous ones – this could easily have happened without it being obvious. One of my aims was to have as few clues as possible, but the main aim was that there had to be a logical path through them.

Preamble

I found it difficult to produce a preamble which didn’t give the game away. I didn’t want to say that all the rows and columns had something in common and instead mentioned obliquely that triangles had to be completed. One of the vetters didn’t like triangular numbers to be referred to as triangles (quite justifiably), and pointed out that many solvers would miss the significance of the title because they didn’t have a copy of Chambers, and so the leap to the final stage was unfair. The preamble was therefore changed by the vetter to “…all the rows and columns are thematically consistent.” I felt this was OK, because the Threes and Squares clues referred to words in the title, and the only other thematic property was triangles.

A Comment on Solving Aids

In all of my puzzles there is a logical path through the clues. If you find you have to use a program or spreadsheet, think again: you don’t. You are missing out on a logical exercise. You are cheating yourself of the pleasure of solving the puzzle using deduction.

“Ah, but you use a computer to create the puzzles,” you might say. Yes, but without using a computer the puzzles wouldn’t exist.

Elap.

Advertisements

5 Responses to “Listener 4114, Three-Square: A Setter’s Blog by Elap”

  1. shirley curran said

    That was a dazzling explanation, thank you, Elap. Even the CERN scientist half of the numpty blogging team found the setting procedure ‘astounding’.

  2. Tom Borland said

    This is the most fascinating setter’s blog that I have ever read, increasing my already huge admiration for the puzzle. Perhaps Listener setters should be refunded on a per-kWh basis?

  3. erwinch said

    Yes, a fascinating read Elap, thank you.  Although I own a copy of Chambers, I didn’t think to look up the title.  I thought that it was just an invention, a play on three square meals perhaps and alluding to the threes and approximate shape of the grid.  Having seen the definition of three-square, I agree that it fully justifies the Squares as clues.

    I see from your Listener solution that you started with the clue: 33333 = L2 * T2 + r5.  I didn’t consider that at all at the beginning, no doubt increasing my labour no end.

  4. nms said

    Thanks, Elap, for sharing this totally fascinating blog with solvers.

    I spent many enjoyable hours filling the grid, but, despite trying hard, did not manage the last step, not thinking of triangular numbers at any point. Will certainly remember them in future.

  5. Alastair Cuthbertson said

    Puzzles which used triangular numbers – Triangular Torment and Triangles in Tough Crosswords and Triangles II and Triangles III in The Magpie spring readily to my mind. Oyler

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: