# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1520: Just pondering

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]

### 4 responses to “Enigma 1520: Just pondering”

1. Jim Randell 5 September 2012 at 9:10 am

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.

```from itertools import product
from enigma import irange, join, printf

# the three colours
colours = tuple('123')

# possible rotations of a 2x2 square
def rotations(s):
(a, b, c, d) = s
return (s, (d, a, b, c), (c, d, a, b), (b, c, d, a))

# find possible 2x2 slabs with 3 colours, unique under rotation
slabs = set()
for s in product(colours, repeat=4):
# rotations of this slab
rs = rotations(s)
# is this a rotation of a slab we've already seen?
if slabs.intersection(rs): continue

N = len(slabs)
printf("There are {N} different 2x2 slab combinations")

# an exception to raise if the puzzle is solved
class Solved(Exception): pass

# a class to solve an n x m grid
class Puzzle:

def __init__(self, n, m):
self.size = (n, m)
# make the empty grid
self.grid = list([' '] * m for _ in irange(1, n))

# attempt to solve the grid
def solve(self):
# let's assume (0, 0) is colour 1, and (0, 1) is colour 1 or 2
self.grid[0][0] = '1'
# try to place a slab
self.place(0, 1, set(), colours[:2])

# place a slab at (x, y)
def place(self, x, y, seen, colours=colours):

# are we done?
(n, m) = self.size
if y == m: (x, y) = (x + 1, 0)
if x == n: raise Solved

# don't place slabs in the pond
if x > 1 and x < n - 2 and y > 1 and y < m - 2:
self.place(x, m - 2, seen)
return

# place a slab at (x, y)
for c in colours:
seen1 = seen
g = self.grid
g[x][y] = c
# does it complete a 2x2 square?
if y > 0 and (x == 1 or x == n - 1) or x > 0 and (y == 1 or y == m - 1):
# what is the square?
s = (g[x - 1][y - 1], g[x][y - 1], c, g[x - 1][y])
# have we seen it?
if seen.intersection(rotations(s)): continue
seen1 = seen.union([s])
# try the next square
self.place(x, y + 1, seen1)

# display the grid
def display(self):
for r in self.grid:
printf("[{r}]", r=join(r))
printf()

# for an a x b pond there are 2(a + 2) + 2(b + 2) 2x2 slabs that can be made
# so let's consider all possible ponds starting with the longest perimeter
done = False
print()
for p in irange((N - 8) // 2, 2, step=-1):
for a in irange(1, p // 2):
b = p - a
x = Puzzle(a + 4, b + 4)
try:
x.solve()
except Solved:
# we've found a solution, so display it
c = 2 * (a + b + 4)
printf("{a}x{b} pond, {t} slabs, {c} 2x2 combinations", t=2 * c)
x.display()
done = True
if done: break # remove this line to find non-maximal solutions
```

Solution: The path is made up of 48 slabs.

2. Hugh Casement 21 January 2016 at 7:23 am

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.

• Jim Randell 21 January 2016 at 11:35 am

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:

3. Hugh Casement 21 January 2016 at 11:59 am

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!

This site uses Akismet to reduce spam. Learn how your comment data is processed.