Enigmatic Code

Programming Enigma Puzzles

Enigma 1444: Backslide

From New Scientist #2605, 26th May 2007

Enigma 1444You 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]

Advertisements

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[1])
    
    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)) + [0]
        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()
    
      # positions adjacent to <p>
      def adjacent(self, p):
        (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
            for q in self.adjacent(p):
              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
          for p in self.adjacent(p):
            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], 0, [])
        # and the blank in the bottom right
        self.blank([3], [0])
        # 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], 0, [])
        # if the next tile is not already in position
        if self.grid.index(t[1]) != 1:
          # get the tile for position 1 in position 3
          self.place(t[1], 3, [0])
          # if the blank is in position 1, just move the piece into place
          if self.b == 1:
            self.move([3])
          else:
            # get the blank into position 2 and then move the piece into position
            self.blank([2], [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 += [0]
      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[0], args[1], 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.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: