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.

Enigma 1210

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]

Advertisements

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[4]:
      t1 = set(r1)
    
      for r2 in ps[4]:
        if not(r1 > r2): continue
        if t1.intersection(r2): continue
        t2 = t1.union(r2)
    
        for r3 in chain(ps[3], ps[4]):
          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.

    Enigma 1210 - Solution

    See also Enigma 106, Enigma 1275, Enigma 1444.

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: