Enigmatic Code

Programming Enigma Puzzles

Enigma 1529: Square corbel

From New Scientist #2692, 24th January 2009 [link]

I invite you to fill in the grid with non-zero digits so that each row is a perfect square with different digits and each row contains all the digits in all rows below it. In no case must a digit be identical with the one below or above it. This can be done in several different ways.

(a) Find an example with the number in the top row divisible by 3.

(b) Find an example in which the number in the right-hand column is palindromic.

In each case what is the number in the top row?

[enigma1529]

Advertisements

2 responses to “Enigma 1529: Square corbel

  1. Jim Randell 15 July 2012 at 5:55 pm

    My original Perl code is too ugly and too slow (and too embarrassing) to show. Here’s a recursive solution in Python. It runs in 48ms.

    from itertools import count
    from collections import defaultdict
    from enigma import is_duplicate, concat, printf
    
    # find squares up to 5 digits, and store them by length and digits
    squares = defaultdict(lambda: defaultdict(list))
    for i in count(1):
      n = str(i * i)
      l = len(n)
      if l > 5: break
      if '0' in n or is_duplicate(n): continue
      squares[l][tuple(sorted(n))].append(n)
    
    
    # check a list for a solution
    a, b = set(), set()
    def check(l):
      n = list(int(x) for x in l)
      # (a) the top row is divisible by 3
      if n[0] % 3 == 0:
        printf("(a) {n}")
        a.add(n[0])
      # (b) the right column is palindromic
      p = concat(*(x[-1] for x in l))
      if p[::-1] == p:
        printf("(b) {n}")
        b.add(n[0])
    
    def solve(i=1, l=[], d=set()):
      # are we done?
      if i == 6:
        check(l[::-1])
        return
      # try and add another layer
      for ds, ns in squares[i].items():
        ds = set(ds)
        # digits in the new layer should superset the previous layer
        if not ds.issuperset(d): continue
        for n in ns:
          # and no digit can be in the same position as the previous layer
          if i > 1 and any(n[-j] == l[-1][-j] for j in range(1, i)): continue
          solve(i + 1, l + [n], ds)
    
    solve()
    printf("a: {a}, b: {b}")
    

    Solution: (a) 13689, (b) 96721.

  2. Brian Gladman 16 July 2012 at 4:26 pm

    I don’t normally try the old ones that you publish but this one caught my interest. Here is my version:

    from itertools import permutations
    
    sqr = {str(x * x):1 for x in range(1, 100)}
    
    def solve(s, seq, l3, lp):
      ln = len(s) - 1
      if not ln:
        # if in last row check the single digit is a non-zero square
        if s in sqr:
          # form solution as a tuple of integers
          t = tuple(map(int, seq[:] + [s]))
          # add to l3 if the top row is divisible by three
          if t[0] % 3 == 0:
            l3 += [t]
          # add to lp if the last column is a paalindrome
          if not (t[0] - t[4]) % 10 and not (t[1] - t[3]) % 10:
            lp += [t]
      else:
        # now permute digits of s to find squares with one less digit
        for p in permutations(s, ln):
          sq = ''.join(p)
          # check for a square and that its digits don't match those above
          if sq in sqr and all(sq[i] != s[i + 1] for i in range(ln)):
            # and repeat for the next lower row
            solve(sq, seq + [s], l3, lp)
            
    # output solutions in grid format
    def outs(h, s):
      print(h)
      for j in range(5):
        print(''.join('{0:7d}'.format(s[i][j]) for i in range(len(s))))
    
    l3, lp = [], []
    for i in range(100, 317):
      sq = str(i * i)
      if '0' not in sq and len(set(sq)) == 5:
        solve(sq, [], l3, lp)
    outs('The top row is divisible by three:', l3)
    outs('The last column is a palindrome:', lp)
    

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: