# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1085: Cut and run

From New Scientist #2241, 3rd June 2000 [link] Place your finger in the starting box in the grid and follow each instruction. You will find that you visit each square before finishing in the appropriate box.

Now cut up the board into six rectangles each consisting of two adjacent squares. Then put them back together to form a new three-by-four grid with the starting square one place lower than it was before. Do all this in such a way that, once again, if you follow the instructions you visit each square.

In your new grid, what instruction is in the top left-hand corner, and what is the instruction in the bottom right-hand corner?

[enigma1085]

### 2 responses to “Enigma 1085: Cut and run”

1. Jim Randell 4 December 2017 at 8:17 am

I tackled this puzzle in two parts. The first part is to arrange the squares in the grid so that you can start in row 2, column 2 and complete the gird. The second part is to look at the grid made from the first part and see if it can be made from the original grid by cutting it into dominoes.

This Python 3 code runs in 124ms.

Run: [ @repl.it ]

```from enigma import irange, update, ordered, chunk, printf

# label the squares:
#
#   0  1  2  3
#   4  5  6  7
#   8  9 10 11

squares = set(irange(0, 11))

# then the corresponding move functions are
def move(k, i):
(r, c) = k
moves = {
# 0: "go down one"
0: (r + 1, c),
# 1: "start here, and go right one"
1: (r, c + 1),
# 2: "go diagonally one, down + right"
2: (r + 1, c + 1),
# 3: "go down two if possible: if not, go up one"
3: (r + 2, c) if r < 2 else (r - 1, c),
# 4: "go right two"
4: (r, c + 2),
# 5: "go diagonally one, down + left"
5: (r + 1, c - 1),
# 6: "go diagonally one, up + right"
6: (r - 1, c + 1),
# 7: "go left two"
7: (r, c - 2),
# 8: "go up two"
8: (r - 2, c),
# 9: "go right one"
9: (r, c + 1),
# 10: "finish here", so we don't need it
# 11: "go left two"
11: (r, c - 2)
}
(r1, c1) = moves.get(i, (0, 0))
assert 0 < r1 < 4 and 0 < c1 < 5
return (r1, c1)

def solve(g, k, squares):
# are we done?
if not squares:
yield (g, k)
# choose a square to place at (r, c)
for i in squares:
try:
k2 = move(k, i)
except AssertionError:
continue
if k2 not in g:
yield from solve(update(g, [(k, i)]), k2, squares.difference([i]))

# choose a value from dict <d>
def choose(d):
for x in d.items():
return x

# find value <v> in dict <d>
def find(d, v):
for (k, v1) in d.items():
if v == v1:
return k

# remove items from dict <d>
def remove(d, ks):
d = d.copy()
for k in ks:
del d[k]
return d

# can g1 and g2 be made from the same set of dominoes?
def dominoes(g1, g2, ds=set()):
# are we done?
if not g1:
if not g2:
yield sorted(ds)
else:
# choose a square from g1
((r1, c1), s1) = choose(g1)
for (r2, c2) in ((r1 - 1, c1), (r1 + 1, c1), (r1, c1 - 1), (r1, c1 + 1)):
s2 = g1.get((r2, c2))
if s2 is None: continue
# are they adjacent squares in g2?
((r1x, c1x), (r2x, c2x)) = (find(g2, s1), find(g2, s2))
(r, c) = (abs(r1x - r2x), abs(c1x - c2x))
if (r == 0 and c == 1) or (c == 0 and r == 1):
# remove the domino from each grid, and solve the remaining squares
yield from dominoes(remove(g1, [(r1, c1), (r2, c2)]), remove(g2, [(r1x, c1x), (r2x, c2x)]), ds.union([ordered(s1, s2)]))

# the diagram grid
g0 = dict()
for i in squares:
(r, c) = (x + 1 for x in divmod(i, 4))
g0[(r, c)] = i

# set up the new grid
(k, i) = ((2, 2), 1)
grid = { k: i }

# place all the squares (except the final square) in the grid
for (g, k) in solve(grid, move(k, i), squares.difference([i, 10])):
# place the final square
g = update(g, [(k, 10)])
# try to match the grids dominowise
for ds in dominoes(g0, g):
printf("top left = {tl}, bottom right = {br}", tl=g[(1, 1)], br=g[(3, 4)])
printf("  grid = {g}", g=list(chunk((g[(r, c)] for r in irange(1, 3) for c in irange(1, 4)), 4)))
printf("  dominoes = {ds}")
```

Solution: In the new grid the instruction in the top left-hand corner is “GO RIGHT TWO”, and the instruction in the bottom right-hand corner is “GO LEFT TWO”.

There is only one way to make up the grid so that you can start in row 2, column 2 and complete the grid, even if you cut the original grid into single squares, so we know what the solution is, if it is possible.

There are two tiles that read “GO LEFT TWO”, so these tiles can be interchanged without changing the pattern. But by cutting the original grid into 2×1 “dominoes” only one of these tiles can appear in the bottom right-hand square, but there are multiple ways to make the cuts. We can cut the square into 2 2×1 rectangles and 2 2×2 rectangles which re-arrange to make the solution grid, as shown below: The 2×2 tiles can be cut either horizontally or vertically to make dominoes, which gives us 4 different sets of dominoes that can be arranged to make the grid.

2. Brian Gladman 6 December 2017 at 5:26 pm
```# the (x, y) increments for the different moves
A, B, C, D, E, F, G, H, I, J, K = (
( 0, -1), (1, 0), ( 1, -1), (0, -2), (2, 0),
(-1, -1), (1, 1), (-2,  0), (0,  2), (0, 0), (0, 1) )

# the twelve tile types (labelled 1 to 12)
tiles = ( (1, A, J), ( 2, B, J), ( 3, C, J), ( 4, D, K),
(5, E, J), ( 6, F, J), ( 7, G, J), ( 8, H, J),
(9, I, J), (10, B, J), (11, J, J), (12, H, J) )

# find a grid of tiles that can be fully traversed
def solve(g, pos, tiles):
x, y = pos
# are all tiles except the finish tile placed?
if not tiles:
# place the 'finish' tile and return the tile positions
g[4 * y + x] = 11
yield g
g[4 * y + x] = 0
else:
# consider unplaced tiles
for i, t1, t2 in tiles:
# try its possible moves
for t in (t1, t2):
xx, yy = pp = (x + t, y + t)
# is the move valid?
if pp != pos and (0 <= xx < 4 and 0 <= yy < 3) and not g[4 * yy + xx]:
# place the tile and proceed to the next move
g[4 * y + x] = i
yield from solve(g, (xx, yy), [z for z in tiles if z != i])
g[4 * y + x] = 0
break

# adjacent positions for in the grid for the indexed position
adj = [ (1, 4), (0, 2, 5), (1, 3, 6), (2, 7),
(0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
(4, 9), (5, 8, 10), (6, 9, 11), (7, 10) ]

# pair the same tiles in two grids
def pair_tiles(g1, g2, pt=[]):
if len(pt) == 6:
yield tuple(sorted(pt))
else:
# pick a tile
p1, t1 = g1.popitem()
# ... and consider adjacent tiles
t2 = g1.get(p2)
if t2:
# find the tiles in the second grid
q1, q2 = (p for p, t in g2.items() if t in {t1, t2})
# if this tile is also adjacent in the second grid
# remove the tiles and continue to the next pairing
h1 = {p:t for p, t in g1.items() if p not in {p1, p2}}
h2 = {p:t for p, t in g2.items() if p not in {q1, q2}}
yield from pair_tiles(h1, h2, pt + [tuple(sorted((t1, t2)))])

# position for the first tile
x, y = pos = (1, 1)
# form the grid and place the first tile
g =  * 12
g[4 * y + x] = 2
# list tiles that remain to be placed (except the finish tile)
sm = [x for x in tiles if x not in {2, 11}]
# find solutions
for g in solve(g, (x + 1, y), sm):
print(f'Grid: (r1 r2 r3): {g[8:]} {g[4:8]} {g[:4]}')
# the initial and re-arranged grids as dictionaries (position:tile)
g0 = {i:i + 1 for i in range(12)}
g1 = {i:v for i, v in enumerate(g)}
for pl in pair_tiles(g0, g1):
print(f'  Top Left = {g}, bottom Right = {g}')
print(f'  Tile Pairings {pl}')
```

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