Enigmatic Code

Programming Enigma Puzzles

Enigma 54: Grid halving

From New Scientist #1197, 6th March 1980 [link]

“Cut the figure to make two identical parts” is a problem put in 100 Geometric Games, by Pierre Berloquin, which I have been reading. Having done so — not without difficulty — I looked up the solution and found it was quite different from mine.

Interpreting “identical” as including “identical when turned over”, how many ways can you find of cutting the figure into two identical parts?

[enigma54]

One response to “Enigma 54: Grid halving”

1. Jim Randell 7 February 2013 at 8:28 pm

This is one that I’ve not been able to fully solve programatically in a satisfactory way. But by considering a simplified version of the problem I am able to find the required solutions in a reasonable time.

The following Python program assumes that the cut divides the figure along the grid lines shown in to two contiguous pieces, and further instead of considering the full 10×6 grid (48 squares) it considers a scaled down 5×3 grid (12 squares). Any solution thus found can obviously be scaled up to become a solution of the original problem. This program runs in 41ms.

```from enigma import printf

# label the pieces:
# [XX][11][12][13][14]
# [XX][ 6][ 7][ 8][ 9]
# [ 0][ 1][ 2][ 3][XX]

# then the adjacency matrix is:
0: (1,),
1: (0, 2, 6),
2: (1, 3, 7),
3: (2, 8),
6: (1, 7, 11),
7: (2, 6, 8, 12),
8: (3, 7, 9, 13),
9: (8, 14),
11: (6, 12),
12: (7, 11, 13),
13: (8, 12, 14),
14: (9, 13),
}

# extract a shape from a grid
def extract(g, c):
s = []
for r in g:
s.append(list('#' if c == i else ' ' for i in r))
# prune away unused elements
while '#' not in s[0]:
s.pop(0)
while '#' not in s[-1]:
s.pop(-1)
while '#' not in list(t[0] for t in s):
for t in s: t.pop(0)
while '#' not in list(t[-1] for t in s):
for t in s: t.pop(-1)
# return the shape
return s

# rotate a shape
def rotate(s):
r = [[] for i in range(len(s[0]))]
for t in s:
for (i, c) in enumerate(reversed(t)):
r[i].append(c)
return r

# mirror a shape
def mirror(s):
return list(list(reversed(t)) for t in s)

# check for a solution
def check(ps, ss):
# plot the shape on a 5 x 3 grid
g = [ [-1] * 5 for i in range(3) ]

j, i = divmod(p, 5)
g[j][i] = 1 if p in ps else 0

# extract the shape
s1 = extract(g, 1)
# and its rotations
s2 = rotate(s1)
s3 = rotate(s2)
s4 = rotate(s3)
# and mirror images
m1 = mirror(s1)
m2 = mirror(s2)
m3 = mirror(s3)
m4 = mirror(s4)
# extract the remaining shape
s0 = extract(g, 0)
# is it the same?
if s0 not in (s1, s2, s3, s4, m1, m2, m3, m4): return

s = max(s1, s2, s3, s4, m1, m2, m3, m4)
if s in ss: return
ss.append(s)

# print the grid
for r in g:
print(''.join(' .X'[i + 1] for i in r))
print()

def solve(ps, ss):
# have we selected half the grid?
if len(ps) == 6:
check(ps, ss)
return