### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,123)
- misc (2)
- project euler (2)
- puzzle (31)
- site news (43)
- tantalizer (31)
- teaser (3)

### Site Stats

- 168,282 hits

Programming Enigma Puzzles

5 September 2012

Posted by on **From New Scientist #2682, 15th November 2008** [link]

Around the edge of the rectangular fish pond in Joe’s back garden is a path two-paving-slabs wide. The square slabs are coloured light brown, grey or light green. Joe has arranged them so that the pattern of colours of any square of four slabs is unique, however viewed. If Joe had needed to make the path any longer, then colour patterns would have had to be repeated.

How many slabs make up the path?

[enigma1520]

Advertisements

%d bloggers like this:

This was a fun puzzle to solve programatically. The following Python code first determines the number of possible 2×2 slab combinations, and then searches for maximal possible constructive solutions. It outputs a solution for each possible pond size. It runs in 670ms.

Solution:The path is made up of 48 slabs.I can see that there are twenty-four 2×2 patterns that are different even under rotation. Also that, because each overlaps its neighbours, that means 48 slabs to fit round a rectangular pond whose dimensions sum to 8. Does it work for all such ponds: 7×1, 6×2, 5×3, and 4×4? Would it also work for a degenerate 8×0 pond (i.e. with no water but something like an edging strip along the middle to prevent patterns overlapping there)?

What layouts does your program generate? My own attempt ran overnight but by morning had found nothing: all those nested loops are very time-consuming.

My program starts looking for arrangements that consist of all of the possible 24 patterns, and it finds the following arrangements that use 48 slabs (corresponding to 1×7, 2×6, 3×5 and 4×4 ponds):

(The program only outputs the first arrangement it finds for a particular shape of pond, but there will be many other possible arrangements).

If you remove line 95 it will continue to examine smaller numbers of slabs, and it finds solutions without repeated patterns for 44 slabs (1×6, 2×5 and 3× 4 ponds), 40 slabs (1×5, 2×4 and 3×3 ponds), 36 slabs (1×4 and 2×3 ponds), 32 slabs (1×3 and 2×2 ponds), 28 slabs (1×2 pond) and 24 slabs (1×1 pond).

By changing the loop at line 84 to start from 0 (instead of 1), you can examine ponds with a dimension of 0. Here’s a diagram of a 48 slab path around a 0×8 pond:

That’s great, Jim. I was just about to cut out some “slabs” and try arranging them. You’ve saved me a lot of trouble!