# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1444: Backslide

From New Scientist #2605, 26th May 2007 You may be familiar with the 15-tile puzzle  that starts as shown, with one gap, after which you can slide into the gap any one of the tiles adjacent to it.

Continuing in this way you can rearrange the tiles into all sorts of orders.

My nephew is so good at his 15-tile puzzle that I have given him a larger version. It is again a rectangle, with more than two tiles along each side, the tiles are numbered 1, 2, 3 …, and it starts with them in the natural order and with the gap in the bottom right-hand corner.

My nephew has mastered the new version. For example, in less than quarter of an hour he can rearrange the tiles into their reverse order, ending up with … 3, 2, 1 and gap in the bottom row. He has also looked into the properties of the numbers on the tiles and has noted, for example, that their sum is divisible neither by 2 nor by 3.

How many tiles are there in his new version of the puzzle?

[enigma1444]

### 3 responses to “Enigma 1444: Backslide”

1. Jim Randell 6 April 2013 at 10:50 am

By analysis we can place certain conditions on the dimensions of the puzzle. This Python program considers m×n puzzles for increasing m+n, and outputs those that match the conditions. By default it outputs the first 10 values it finds. I’m assuming that we want the smallest puzzle (by number of tiles) that satisfies the conditions. It runs in 40ms.

```# if the puzzle is m x n then there are t = mn - 1 tiles
# and the sum of the numbers on the tiles is T(t)
# (the mn-1 th triangular number).

# consider the number of "inversions" in the grid (an inversion
# occurs when a pair of tiles are out of their "natural" order).
#
# in the initial position there are zero inversions, when we make
# a horizontal move we do not change the inversion order of any tiles,
# but when we make a vertical move we change the relationship of the
# m - 1 tiles between the hole and the moved tile.
#
# so the change in the number of inversions is:
# before:     0      1      2   ...   m-3    m-2    m-1
# after:    m-1    m-2    m-3   ...     2      1      0
# change: +(m-1) +(m-3) +(m-5)      -(m-5) -(m-3) -(m-1)
#
# the blank tile starts off in the bottom row and ends up in the
# bottom row, so there are an even number of vertical moves, and
# so the number of inversions in any final position contains an
# even number of inversions.
#
# when the tiles are in reverse order there are T(t - 1) inversions
# so we need this to be even.

# both values are in terms of t, so we consider puzzles where m >= n.

from itertools import count
from enigma import irange, first, printf

def generate():
for x in count(6):
for m in irange(3, x // 2):
n = x - m
# number of tiles
t = m * n - 1
# sum of the tiles
s = t * (t + 1) // 2
# is not divisible by 2 or 3
if s % 2 == 0 or s % 3 == 0: continue

# number of inversions in a reversal
i = t * (t - 1) // 2
# must be even
if i % 2 == 1: continue

yield (m, n, t, s, i)

# number of solutions required
import sys
N = 10 if len(sys.argv) < 2 else int(sys.argv)

for (m, n, t, s, i) in first(generate(), count=N):
printf("tiles={t} [{m}x{n} grid, sum={s} inversions={i}]")
```

Solution: The new version of the puzzle has 49 tiles (in a 5×10 grid).

2. Jim Randell 6 April 2013 at 11:21 am

It’s all very well to solve the problem analytically, but I like constructive solutions, so I thought I would write a program to determine the moves to invert an m×n puzzle.

This program encapsulates a simple solving strategy (so it won’t find the shortest possible sequence of moves – but that’s an NP-hard problem), but even so it ended up being more fiddly than I’d imagined at the outset.

For a 5×10 puzzle it reverses the squares in 1394 moves (or 1300 if asked to reverse a 10×5 grid), so to solve the puzzle using this strategy in “less than quarter of an hour” (i.e. 900 seconds) you would have to be making moves pretty quickly (or use a cleverer strategy), but it would be possible.

The next smallest solution is 97 tiles in a 7×14 grid. This program takes 3872 moves (or 3828 for the 14×7 grid) to solve that, so it’s unlikely you would be able to use this strategy to solve larger puzzles in the required time.

By considering the distances that each square has to move in order to invert the grid we can place a lower bound of 357 moves on the 5×10 puzzle, and 1003 moves on the 7×14 puzzle, so it’s possible that a larger puzzle could be solved manually in 15 minutes.

```from enigma import chunk, flatten, printf

class Impossible(Exception): pass

class Puzzle(object):

def __init__(self, m, n, target, initial=None):
if initial is None: initial = list(range(1, m * n)) + 
assert len(initial) == m * n, "invalid initial grid"
assert len(target) == m * n and target[-1] == 0, "invalid target grid"
# if m > n flip the puzzle around
self.flipped = (m > n)
if self.flipped:
target = flatten(zip(*chunk(target, m)))
initial = flatten(zip(*chunk(initial, m)))
m, n = n, m
self.m = m
self.n = n
self.grid = initial
self.target = target
self.b = initial.index(0)
self.moves = list()

(m, n) = (self.m, self.n)
(p0, p1) = divmod(p, m)
if p0 > 0: yield p - m
if p0 + 1 < n: yield p + m
if p1 > 0: yield p - 1
if p1 + 1 < m: yield p + 1

# move by sliding the tiles at positions <ps>
def move(self, ps):
(b, g, ms) = (self.b, self.grid, self.moves)
for p in ps:
# check the blank is adjacent to position p
assert any(b == x for x in self.adjacent(p)), "invalid move"
# update moves
ms.append(g[p])
# swap the blank and the tile
g[b], g[p], b = g[p], g[b], p
# remove any duplicate moves
while len(ms) > 1 and ms[-1] == ms[-2]: del ms[-2:]
# update blank position
self.b = b

# move the blank to one of the positions <ps>
# without disturbing tiles in positions <fs>
def blank(self, ps, fs):
(m, n, g, b) = (self.m, self.n, self.grid, self.b)
# is the blank already in position?
if b in ps: return
# an empty grid to record distances from the blank
h = [None] * len(g)
# mark any fixed tiles
for p in fs: h[p] = m + n
# and the initial position of the blank
h[b] = 0
# and propagate distances from the blank
d = 0
while h.count(d) > 0:
for (p, x) in enumerate(h):
if x != d: continue
# mark any adjacent empty squares with d + 1
if h[q] is None: h[q] = d + 1
d += 1
# find the position with a minimal distance
(d, p) = min((h[p], p) for p in ps)
# now traverse the grid to find the moves needed
ms = [p]
while d > 1:
# find an adjacent square with a distance of d - 1
d -= 1
if h[p] == d:
ms.insert(0, p)
break
# make the moves
self.move(ms)

# place the tile labelled <t> in position <p>
# without disturbing tiles in positions <fs>
# (presumed to be in the top row on the left)
def place(self, t, p, fs):
(g, m) = (self.grid, self.m)
# find the tile
s = g.index(t)
# move the piece to the right (if necessary)
while s % m < p % m:
self.blank([s + 1], fs + [s])
self.move([s])
s += 1
# move the piece up (if necessary)
while s // m > p // m:
self.blank([s - m], fs + [s])
self.move([s])
s -= m
# move the piece left (if necessary)
while s % m > p % m:
self.blank([s - 1], fs + [s])
self.move([s])
s -= 1

# solve a reduced puzzle by removing the top row
def reduce(self):
(m, n, g, t) = (self.m, self.n, self.grid, self.target)
# create a reduced puzzle
p = Puzzle(m, n - 1, t[m:], initial=g[m:])
# solve it
p.solve()
# and incorporate the results (unflipping as necessary)
if p.flipped: p.grid = flatten(zip(*chunk(p.grid, p.m)))
self.grid = self.grid[:m] + p.grid
self.b = self.grid.index(0)
self.moves.extend(p.moves)

# solve a 2x2 grid
def solve2x2(self):
# place the right tile in position 0
self.place(self.target, 0, [])
# and the blank in the bottom right
self.blank(, )
# is it solved?
if self.grid != self.target: raise Impossible

# solve a 2x3 grid
def solve2x3(self):
t = self.target
# place the right tile in position 0
self.place(t, 0, [])
# if the next tile is not already in position
if self.grid.index(t) != 1:
# get the tile for position 1 in position 3
self.place(t, 3, )
# if the blank is in position 1, just move the piece into place
if self.b == 1:
self.move()
else:
# get the blank into position 2 and then move the piece into position
self.blank(, [0, 3])
self.move([0, 1, 3, 5, 4, 2, 0, 1, 3, 2, 4, 5, 3, 1, 0, 2])
# and solve the remaining 2x2 grid
self.reduce()

# general case solver for larger grids
def solveit(self):
(m, n, t) = (self.m, self.n, self.target)
# get the first m - 1 tiles in the right position
fs = []
for i in range(0, m - 1):
self.place(t[i], i, fs)
fs.append(i)
# if the final tile of the row is not in position
if self.grid.index(t[m - 1]) != m - 1:
# then get it underneath its target position
p = m - 3
self.place(t[m - 1], p + 2 + m, fs)
# get the blank in the right position and complete the top row
if self.b == p + 2:
self.move([p + 2 + m])
else:
self.blank([p + m], fs + [p + 2 + m])
self.move((p + x for x in (0, 1, 2, 2 + m, 1 + m, 1, 0, m)))
# and solve the rest of the puzzle
self.reduce()

def solve(self):
(m, n) = (self.m, self.n)
if (m, n) == (2, 2):
self.solve2x2()
elif (m, n) == (2, 3):
self.solve2x3()
else:
self.solveit()
return self.moves

def main(m, n, t=[]):
if len(t) == 0: t = list(range(m * n - 1, 0, -1))
if len(t) < m * n: t += 
p = Puzzle(m, n, t)
try:
p.solve()
except Impossible:
printf("impossible target {p.target}")
return

printf("moves = {p.moves}")
printf("solved in {n} moves", n=len(p.moves))

import sys
args = [5, 10] if len(sys.argv) < 2 else list(int(x) for x in sys.argv[1:])

main(args, args, args[2:])
```

Here are the number of moves this program generates for the first ten possible solutions.

```tiles grid      moves

49   5x10   1394 /  1300
97   7x14   3874 /  3828
109  10x11   4348 /  4122
109   5x22   6752 /  6344
169  10x17   8424 /  8686
181  13x14   9102 /  9354
181   7x26  13346 / 12598
229  10x23  15272 / 14982
241  11x22  15872 / 15520
265  14x19  16534 / 16314
```
• Jim Randell 10 April 2013 at 10:36 am

I coded up a simple Tk UI to see this code in action (and allow you play with general m×n puzzles). Rather than post the code here (adding the UI makes it about twice as long), you can download it from my blog [ jimpulse.blogspot.co.uk/2013/04/sliding-puzzle-in-python.html ] which also contains a description of how the code operates.

You can use the program to slide tiles around yourself, or get the algorithm given above to solve a puzzle.

I used this program to demonstrate that it is indeed possible to reverse a 10×5 puzzle in less than 15 minutes, and this is the configuration that the program is set to solve by default. Just fire it up, hit “Solve” and sit back and enjoy the show. It takes 1300 moves and on my machine it runs in about 4 minutes.

The default animation speeds mean you would have to pretty nimble-fingered to keep up with the program in real life (or use a cleverer algorithm to solve puzzles in fewer moves), as it makes around 5 moves per second. (There are command line parameters if you want to change the speed of moves). I manually reversed a 5×5 puzzle in 3 minutes (three times slower than my program), so a 10×5 puzzle should certainly be possible in under 15 minutes by hand, even using this simple algorithm.

The next smallest solutions are also solved in less than 15 minutes by the program (but only just). A 14×7 puzzle is solved in 3828 moves, and a 11×10 puzzle is solved in 4122 moves. These both take about 14 minutes. After that a 22×5 solution is solved in 6344 moves and takes about 21 minutes.

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