Tasteful tiling with Excel

If you arrived looking for information on shuffling lists, lottery numbers and choosing random numbers that don't repeat, you may be interested in this article.

Someone who fits kitchens and bathrooms for a living asked for help with tiling: "Clients often want a random effect using different colours. You wouldn't believe how long we spend trying to get arrangements that look right, and then the client comes home and says she can see a space invader near the cooker."

He tried to produce random patterns with Excel so that the proposed tiling scheme could be pre-approved. Unfortunately, efforts with the RAND function did not look very random due to clusters of the same colour:

I was asked whether these clumps are due to a bug in RAND, and if there is a way to randomly distribute tiles of different colours without these shapes turning up.

Yes there is, but not by filling cells with RAND functions. RAND generates a number without reference to other cells. You can bias the result towards or away from certain numbers but this won't fix the problem.

I don't want what I asked for

When clients ask for a random pattern, they may not be asking for what they mean.

Download the file RandomTiles.xls from here. Open it, ensure the 'Run improver...' checkbox is unticked, and click the 'Truly random' button a few times. Watch the patterns. Parts will be as disordered as anyone could wish, but mostly there's a degree of clumpiness – areas of the same colour that form shapes the brain picks out as non-random.

And yet the VBA macro program behind this button is making genuinely random choices from the stock of tiles allocated on the upper left.

The fewer colours involved, the more likely it is that a tile will fall next to another of the same colour purely by chance. Clusters do not indicate a bug. The selection process would not be truly random if it did not exhbit clumping in most of the patterns. How often do lottery numbers come out evenly spaced? How often does flipping a coin produce alternating heads and tails over a long sequence? Very rarely. A tendency towards bunching is exactly how a random system behaves.

Clumping of tile colours may be pleasing to some. Others say it is not what they want.

If you press the button enough times, the random shuffling might eventually generate every possible arrangement of tiles including relatively un-clustered ones like this:

How many times? The number of unique patterns you can make in this grid with four colours is mind-bendingly massive.

Patterns generated by the program are random in the sense of being a random selection from all possible patterns. A few look very regular and planned. Some look totally chaotic. Between the extremes are a gigantic number that have a degree of clumpiness. These intermediate types are in the majority so they come up most often.

As an aside, it is interesting to note that if you could examine all possible patterns, in addition to the jumbled ones, you would see every possible image that could be represented with that number of pixels in those colours. Every possible face, every possible fragment of writing in any possible language invented or not, next week's lottery numbers... anything.

But with no easy way to pick out the relative few that appear to make sense, and no way to distinguish true information from false, there would be little point looking for something of value even if you had the time.

Cluster's last stand

What some of the tiler's clients really want is one of the sub-set of patterns that appear very chaotic. Press the 'Scatter' button and you will see that we can favour generation of these patterns.

The macro behind this begins by making a list of all the empty positions to be tiled. The list is shuffled like a deck of cards and the area is tiled in the random order so produced.

This alone would not reduce clustering. It is just a way of generating random selections, warts and all.

The twist is that at each position, the program counts the colours of nearby tiles. A random choice is made from among the least popular. If the stock of the chosen colour has been used up then an alternative unpopular choice is made.

Here, the program sees that the position about to be tiled has two orange neighbours, one yellow and one green. Its first choice is a random selection from the locally unrepresented blue and purple.

If stocks of both are gone, it makes a random choice between the next most unpopular colours, yellow and green. Should they be used up also, orange would be selected.

This local survey increases colour diversity around a tile, thus decreasing clumping. The brain is remarkably good at identifying patterns and even this improved algorithm leaves artefacts, though fewer than before and not so large.

Increasing the number of colours helps, as does overstocking slightly so the program cannot run out of colours prematurely.

Another variable you can play with is the size of the area examined around each tile. This is the value marked 'Scope', and note that it is not used by the first, truly random algorithm. A scope of 1 means the program examines immediately adjacent tiles – a 3 x 3 block.

Upping the value to 2 extends the reach by another tile in every direction, giving a block size of 5 x 5, and so on. Scope 0 removes local analysis, making 'Scatter' the same as 'Truly random'.

Pushing the scope upwards without also increasing the number of available colours increases local clustering. This is because examining a larger number of tiles reduces the possibility of making a unique choice. Play with this because the patterns often have some appeal.

The 'Scatter+' button hard-wires a scope of 2 and takes account of a tile's relative position as well as its colour.

The influence of the four immediately adjacent horizontal and vertical tiles is magnified by a weighting system. It is much less likely that a tile of the same colour as one in those positions will be selected.

Push this improved program into a corner by choosing a low number of colours and it tends to favour diagonal lines. On five colours Scatter+ generates good patterns where Scatter exhibits clumping.

You may find a pattern that's almost right except for a little tweaking. The worksheet allows manual swapping of tiles: select one tile, [Ctrl]-click the other and press the 'Swap tiles/areas' button.

Dump the clumps

Finally we come to the purpose of the 'Run improver...' checkbox I asked you to clear earlier. Tick it now and try all three buttons again.

The results are hard to distinguish from each other and all are better than before.

The problem with the scatter algorithm is that it doesn't have foresight. As it gets deeper into the run, it usually finds places where clumping is unavoidable due to unfortunate arrangements of neighbours. These were valid choices according to the state of the neighbourhood at the time, but have accidentally hampered later selections.

When tiling is complete we can see that re-making some choices gives local improvements. For instance, a tile may be swapped with another colour left in stock.

Scatter could be given some look-ahead intelligence but instead, activating the improver function causes a post-run analysis of the final pattern. Clumps are identified and attempts made to swap with better colours in the remaining stock. Priority is given to horizontally and vertically adjacent neighbours, then another pass is made to try to spruce up diagonals.

It works pretty well and removes the need for some of the options if the only point is to produce chaotic tile patterns. It may even be possible to ditch the scatter code and rely on the improver to scramble an ordered starting point.

Many people download the workbook for its utility value and have no interest in the background. For me, though, the insights collected along the way are the main motivation so the Excel file is left as an illustration of the ideas it realises.