# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1210: ELITE TILE

From New Scientist #2366, 26th October 2002 [link]

You are probably familiar with the puzzle consisting of 15 sliding tiles as shown. By sliding the tiles around you can make various arrangements and then read off each row as one long number. For example, the first row might consist of 3, 1, 8 and 13, which could be read as the palindromic number 31813.

I formed one arrangement recently in which the numbers formed by three of the four rows were palindromic and the number formed by the remaining row was exactly six times a palindrome.

What was that non-palindromic row?

[enigma1210]

### One response to “Enigma 1210: ELITE TILE”

1. Jim Randell 15 August 2015 at 8:56 am

As discussed in Enigma 1444, an arrangement of the 15-puzzle is only possible if the parity (i.e. odd or even) of the number of “inversions” is the opposite of the parity of the row number of the empty space.

This Python program runs in 367ms.

```from itertools import permutations, chain
from collections import Counter
from enigma import irange, concat, printf

# the tiles
ts = set(str(i) for i in irange(1, 15))

# check the arrangement is a valid 15-puzzle
# the number of inversions should have opposite parity from the row the empty space is in
def check(s):
s = list(s)
# where is the empty space?
r = s.index(0)
s.pop(r)
# count the inversions
n = sum(sum(1 for x in s[i + 1:] if v > x) for (i, v) in enumerate(s))
# check the parities
return (((n + (r // 4)) % 2) == 1)

# look for 3 and 4 tile palindromes
ps = { 3: [], 4: [] }
for n in ps.keys():
for p in permutations(ts, n):
s = concat(*p)
if s == s[::-1]:
ps[n].append(p)
printf("[{p} -> {s}]")

# the arrangement we are interested in must have two 4-tile palindromes
# and a third 3- or 4-tile palindrome, none of them must share tiles

c = Counter()

for r1 in ps:
t1 = set(r1)

for r2 in ps:
if not(r1 > r2): continue
if t1.intersection(r2): continue
t2 = t1.union(r2)

for r3 in chain(ps, ps):
if not(len(r3) == 3 or r2 > r3): continue
if t2.intersection(r3): continue
t3 = t2.union(r3)

# remaining row need to be arranged into 6x a palindrome
for r4 in permutations(ts.difference(t3)):
n = int(''.join(r4))
(d, r) = divmod(n, 6)
if r > 0: continue
s = str(d)
if s != s[::-1]: continue

# check that the rows (in some order) make a viable puzzle
for rs in permutations((r1, r2, r3, r4)):
s = []
for r in rs:
s.extend(map(int, r))
if len(r) == 3:
s.append(0)
if check(s):
c[n] += 1
printf("{rs} n={n} d={d}")

# output solutions
for (k, v) in c.most_common():
printf("n={k} [{v} solutions]")
```

Solution: The non-palindromic row is: 7, 9, 8, 6.

When read as a number 7986 = 6 × 1331.

There are many ways to arrange the puzzle. My program finds 1296 solutions, but in all cases the non-palindromic row is (7, 9, 8, 6). (Thanks to Brian Gladman for pointing out a flaw in my original program that cause it to miss some of the solutions).

Here is one arrangement which I made using the sliding-puzzle.py program I wrote for Enigma 1444. 