# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1124: Classy glass

From New Scientist #2280, 3rd March 2001 [link]

On each anniversary of its foundation my company asks a local artist to make a glass sculpture consisting of a three-by-three arrangement of squares of glass. On the first anniversary just one of the squares had to be red, the rest being blue. On the second anniversary two of the nine had to be red, the rest blue, etc. Before making the final work the artist produces scale models of all the possibilities so that we can choose the one we like best. For economy she does not make any two that look the same when rotated or turned over. So, for example, her first anniversary models were as illustrated, involving a total of just three red squares: For our current anniversary she has again produced scale models of all the possibilities, and for these she has had to make more than one hundred small red squares of glass.

Which anniversary is it, and precisely how many small red squares does she need?

[enigma1124]

### 6 responses to “Enigma 1124: Classy glass”

1. Jim Randell 13 March 2017 at 8:19 am

The grid is fairly small, so programatically we can just generate all possible colourings of the grid with n red squares, and then combine colourings that are the same by rotation/reflection.

This Python program examines the number of red and blue squares for anniversaries from 0 to 9. It runs in 57ms.

```from itertools import combinations
from enigma import irange, printf

# label the grid
square = (0, 1, 2, 3, 4, 5, 6, 7, 8)

# symmetries of the grid
grids = (
# rotations
(0, 1, 2, 3, 4, 5, 6, 7, 8),
(6, 3, 0, 7, 4, 1, 8, 5, 2),
(8, 7, 6, 5, 4, 3, 2, 1, 0),
(2, 5, 8, 1, 4, 7, 0, 3, 6),
# reflections
(2, 1, 0, 5, 4, 3, 8, 7, 6),
(8, 5, 2, 7, 4, 1, 6, 3, 0),
(6, 7, 8, 3, 4, 5, 0, 1, 2),
(0, 3, 6, 1, 4, 7, 2, 5, 8),
)

# canonical representation of a pattern
def canonical(grid):
return min(tuple(grid[r[i]] for i in square) for r in grids)

# number of red squares
for n in irange(0, 9):
r = set()
# choose red squares
for s in combinations(square, n):
# make the grid
grid = tuple((1 if i in s else 0) for i in square)

# count the number of different grids and number of red squares
gs = len(r)
rs = n * gs
bs = (9 - n) * gs
s = ('[*** SOLUTION ***]' if rs > 100 else '')
printf("n={n}, grids={gs}, red={rs}, blue={bs} {s}")
```

Solution: It is the fifth anniversary. 115 red squares are required.

Of course the numbers of red and blue tiles required for anniversary n are the same as the number of blue and red tiles required for anniversary 9 – n.

Here’s the output of the program, with the number of different grids and the number of red and blue tiles required for each anniversary:

```n=0, grids=1, red=0, blue=9
n=1, grids=3, red=3, blue=24
n=2, grids=8, red=16, blue=56
n=3, grids=16, red=48, blue=96
n=4, grids=23, red=92, blue=115
n=5, grids=23, red=115, blue=92
n=6, grids=16, red=96, blue=48
n=7, grids=8, red=56, blue=16
n=8, grids=3, red=24, blue=3
n=9, grids=1, red=9, blue=0
```
2. Hugh Casement 13 March 2017 at 2:13 pm

On the first anniversary there are 9 configurations, including reflexions and/or rotations.
On the second, 36 which is the 8th triangular number = 8×9/2!.
On the third, 84 which is the 7th tetrahedral number = 7×8×9/3!.
On the fourth, 126 = 6×7×8×9/4!, which I suppose we can call the 6th four-dimensional tetrahedral number.
Continuing in like manner we find (not surprisingly) that the numbers continue 126, 84, 36, 9, 1.

3. Brian Gladman 13 March 2017 at 4:26 pm
```from itertools import product
from collections import defaultdict

# 3x3 configurations are kept as an array of nine values: three
# for row 1, three for row 2 and then three for row 3

# the index of the old position for each position when rotated
ixr = (6, 3, 0, 7, 4, 1, 8, 5, 2)
# the index of the old position for each position when turned over
ixo = (2, 1, 0, 5, 4, 3, 8, 7, 6)

# check if a 3x3 configuration is in a set of such configurations
# by testing all four rotations in normal and overturned states
def is_in(sq, set_sqr):
s = sq[:]
for i in range(2):
s = tuple(s[k] for k in ixo)
t = s[:]
for j in range(4):
t = tuple(t[k] for k in ixr)
if t in set_sqr[sq.count(1)]:
return True
return False

# keep 3x3 configuations indexed on their number of reds
sqrs = defaultdict(set)
# form all possible 3x3 configurations
for sq in product((0, 1), repeat=9):
# if we have not yet seen this configuration
if not is_in(sq, sqrs):
# .. add it to our set for this number of red squares

# output the results
print('Red  3x3 Totals Red Blue')
for r in range(10):
c = len(sqrs[r])
print(f'{r:>3}{c:>5}{c*r:>11}{c*(9-r):>5}')
```
4. arthurvause 14 March 2017 at 9:41 am

The number of distinct ways of selecting M items in an N*N grid, unique up to rotation and reflection, is a well known problem.

This stackexchange question sketches the explanation of the solution, from which I have produced the code below, although I don’t claim to fully follow the derivation.

```import sympy

def solutions(N):
# number of ways of choosing objects in an N*N grid, up to rotation and reflection
# from https://math.stackexchange.com/questions/570003/how-many-unique-patterns-exist-for-a-nxn-grid

x = sympy.symbols('x')
if N%2 == 0:
p = ((1+x)**(N*N)+ 3 * (1+x*x)**((N*N)/2) + 2*(1+x)**N *(1+x*x)**( (N*N-N)/2 ) +2*(1+x**4)**( (N*N)/4 ))/8
else:
p = ((1+x)**(N*N)+ 4*(1+x)**N * (1+x*x)**((N*N-N)/2) + 2*(1+x)*(1+x**4)**( (N*N-1)/4 ) +(1+x)*(1+x*x)**( (N*N-1)/2 ))/8

return sympy.Poly(p,x).all_coeffs()

for a, n in enumerate( solutions(3) ):
if a*n > 100:
print "Anniversary number {} needs {} red squares".format(a,a*n)
```
• arthurvause 14 March 2017 at 10:06 am

Of course, for this problem, the solutions for even values of N aren’t needed, but I have used the function in another program to verify that it correctly reproduces OEIS sequence A019318.

• Jim Randell 14 March 2017 at 2:52 pm

That’s neat. I ended up on that page on StackExchange yesterday, but got lost in all the talk of the Orbit-counting Lemma, the Cycle Index Theorem, and Pólya enumeration, and eventually decided that it was a bit of overkill for the 3×3 grid anyway.

But thanks for extracting the formulae. Here’s a version that uses the [[ `Polynomial` ]] class from the enigma.py library, which saves having to pull in SymPy, so is a bit quicker.

(I added the polynomial routines after the discussion on generating polynomials for Pizza Puzzle).

The size of grid N can be specified on the command line (defaults to 3) and the number of different grids (patterns), red tiles and blue tiles are given for each n = 0..N².

The number of grids found corresponds with OEIS A054252.

```from enigma import Polynomial, arg, printf

# find the number of different 2-colourings on an NxN grid
# patterns that are the same when rotated/reflected are counted once
# return a tuple with N^2 elements corresponding to the number
# of different patterns with n elements selected
def solve(N):
# constants
k2 = Polynomial() # 2
k3 = Polynomial() # 3
k4 = Polynomial() # 4
# polynomials
p1 = Polynomial([1, 1]) # 1 + x
p2 = Polynomial([1, 0, 1]) # 1 + x^2
p4 = Polynomial([1, 0, 0, 0, 1]) # 1 + x^4
# exponents (that work with even and odd parity N)
e1 = N * N # N^2
e2 = e1 // 2 # (1/2)(N^2) or (1/2)(N^2 - 1)
e3 = (e1 - N) // 2 # (1/2)(N^2 - N)
e4 = e2 // 2 # (1/4)(N^2) or (1/4)(N^2 - 1)

# construct the generating polynomial
if N % 2 == 0:
# even N
p = (p1 ** e1) + (k3 * (p2 ** e2)) + (k2 * (p1 ** N) * (p2 ** e3)) + (k2 * (p4 ** e4))
else:
# odd N
p = (p1 ** e1) + (p1 * (p2 ** e2)) + (k4 * (p1 ** N) * (p2 ** e3)) + (k2 * p1 * (p4 ** e4))

# divide the coefficients by 8
(s, r) = zip(*(divmod(a, 8) for a in p))
assert all(x == 0 for x in r)
return s

# size of the grid
N = arg(3, 0, int)
N2 = N * N

# consider the NxN grid
for (n, g) in enumerate(solve(N)):
# number of red and blue squares
(rs, bs) = (n * g, (N2 - n) * g)
printf("[N={N}] n={n}: grids={g}, reds={rs}, blues={bs}")
```

For the N=3 case it runs in 42ms.

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