Enigmatic Code

Programming Enigma Puzzles

Enigma 1316: Clueless

From New Scientist #2474, 20th November 2004

I gave a copy each to my niece and nephew of the following grid and instructions to see what different answers they might produce.

Enigma 1316

“Follow these instructions, in each case writing a number, larger than 10, across or down, within the grid, and with one digit in each box:

A. Starting at a box number which is a square, write a square.

B. Starting at a box number which is a cube, write a cube.

C. Starting at a box number which is a prime, write a prime whose digits add up to an even number.

D. Starting at a box number which is even, write an even number.

Your answers should fill the grid, with no two answers overlapping.”

Unfortunately, one of the copies had instruction D completely missing. Each child gave me a 3-by-3 grid which was correct for the copy they had been given. By coincidence they gave me identical grids.

What was their completed grid?

Enigma 1772 is also called “Clueless”.

[enigma1316]

Advertisements

2 responses to “Enigma 1316: Clueless

  1. Jim Randell 17 June 2014 at 7:50 am

    This direct approach, programmed in Python 3, runs in 5.1s. With a bit of analysis we can do better than this, but I like this approach as it doesn’t need to make assumptions to solve the problem.

    from enigma import irange, Primes, chunk
    
    # squares
    squares = list(i ** 2 for i in irange(1, 31))
    
    # cubes
    cubes = list(i ** 3 for i in irange(1, 9))
    
    # primes
    primes = Primes(999)
    
    # evens
    evens = list(irange(2, 998, step=2))
    
    # update grid <g> at index <i> in direction <d> with string <s>
    # g - grid
    # i - position to fill out
    # d - direction (1 = x, 3 = y)
    # s - string
    def update(g, i, d, s):
      g = list(g)
      for (j, v) in enumerate(s):
        p = i + j * d
        if g[p]: return
        g[p] = v
      return g
    
    # fit a number from <ns> into grid <g>
    # g - grid
    # z - co-ordinate (x or y)
    # i - index into grid
    # d - direction (1 = x, 3 = y)
    # ns - set of numbers
    # fn - filter function
    def fit(g, z, i, d, ns, fn):
      for n in ns:
        if not fn(n): continue
        s = str(n)
        l = len(s)
        if not(z + l < 4): break
        g2 = update(g, i, d, s)
        if g2:
          yield g2
    
    # fit a number from <ns> (filtered by <fn>) into grid <g>
    def fill(g, ns, fn):
      for (i, v) in enumerate(g):
        # the square must be unoccupied
        if v is not None: continue
        # and must be in the set
        if i + 1 not in ns: continue
        (y, x) = divmod(i, 3)
        # try to fit horizontally
        if x < 2:
          yield from fit(g, x, i, 1, ns, fn)
        # and vertically
        if y < 2:
          yield from fit(g, y, i, 3, ns, fn)
    
    # initial grid
    g0 = [None] * 9
    
    # for A, B, D the numbers must be > 10
    def f1(n):
      return (n > 10)
    
    # for C the numbers must also have an even digit sum
    def f2(n):
      return f1(n) and (sum(int(d) for d in str(n)) % 2 == 0)
    
    # record the results: r1 = without instruction D, r2 = with instruction D
    (r1, r2) = (set(), set())
    # A. fill out the square
    for g1 in fill(g0, squares, f1):
      # B. fill out the cube
      for g2 in fill(g1, cubes, f1):
        # C. fill out the prime
        for g3 in fill(g2, primes, f2):
          # is the grid completed without D?
          if None not in g3:
            r1.add(''.join(g3))
          # D. fill out evens
          for g4 in fill(g3, evens, f1):
            # is the grid completed with D?
            if None not in g4:
              r2.add(''.join(g4))
    
    # print solution grids common to both
    for r in r1.intersection(r2):
      print(' / '.join((r[:3], r[3:6], r[6:])))
    

    Solution: The completed grid is shown below:

    Enigma 1316 - Solution

    The two different ways of filling out the grid are shown below:

    Enigma 1316 - Solution 2

    A: (red) A square, starting from a box numbered with a square.
    B: (green) A cube, starting from a box numbered with a cube.
    C: (blue) A prime with an even digit sum, starting from a box numbered with a prime.
    D: (yellow) An even number, starting from a box numbered with an even number.

  2. Brian Gladman 18 June 2014 at 2:35 pm
    from enigma import Primes
    
    # two and three digit squares
    sq2 = tuple(str(x ** 2) for x in range( 4, 10))
    sq3 = tuple(str(x ** 2) for x in range(10, 32))
    
    # two and three digit cubes
    cb2 = tuple(str(x ** 3) for x in range(3,  5))
    cb3 = tuple(str(x ** 3) for x in range(5, 10))
    
    # two and three digit primes
    pr2 = tuple(str(x) for x in Primes(100) if x > 10 and 
                sum(int(y) for y in str(x)) % 2 == 0)
    pr3 = tuple(str(x) for x in Primes(1000) if x > 100 and 
                sum(int(y) for y in str(x)) % 2 == 0)
    
    # two and three digit even numbers
    ev2 = tuple(str(x) for x in range( 10,  100, 2))
    ev3 = tuple(str(x) for x in range(100, 1000, 2))
    
    # add numbers to the grid
    # g    - the current grid 
    # ix   - the list of positions to be considered
    # val2 - possible two digit values 
    # val3 - possible three digit values 
    
    def add_to_grid(g, ix, val2, val3):
      for i in ix:
        # is the position empty?
        if not g[i - 1]:
          # can we fit a horizontal two digit value
          if i % 3 and not g[i]:
            gg = g[:]
            for n in val2:
              gg[i - 1 : i + 1] = n
              yield gg
          # can we fit a horizontal three digit value
          if i % 3 == 1 and not (g[i] or g[i + 1]):
            gg = g[:]
            for n in val3:
              gg[i - 1 : i + 2] = n
              yield gg
          # can we fit a vertical two digit value
          if i < 7 and not g[i + 2]:
            gg = g[:]
            for n in val2:
              gg[i - 1 : i + 5 : 3] = n
              yield gg
          # can we fit a vertical three digit value
          if i < 4 and not (g[i + 2] or g[i + 5]):
            gg = g[:]
            for n in val3:
              gg[i - 1 : i + 8 : 3] = n            
              yield gg
    
    # add values to the grid
    def solve(g, l):
      if l == 0:
        # add a square
        for gg in add_to_grid(g, (1, 4, 9), sq2, sq3):
          yield from solve(gg, 1)
      elif l == 1:
        # add a cube
        for gg in add_to_grid(g, (1, 8), cb2, cb3):
          yield from solve(gg, 2)
      elif l == 2:
        # add a prime
        for gg in add_to_grid(g, (2, 3, 5, 7), pr2, pr3):
          yield from solve(gg, 3)
      elif l != 4 and 0 in g:
        # add an even number - is there room?
        i = g.index(0)
        if i % 3 != 2 and not g[i + 1] or i < 6 and not g[i + 3]:
          for gg in add_to_grid(g, (2, 4, 6, 8), ev2, ev3):
            yield from solve(gg, 4)
      else:
        yield l, tuple(g)
    
    # split into three and four number grids
    s1, s2 = set(), set()
    for l, g in solve([0] * 9, 0):
      if l == 3:
        s1.add(g)
      else:
        s2.add(g)
    # and find grids that are common to both
    for g in s1 & s2:
      print('{} {} {}\n{} {} {}\n{} {} {}\n\n'
            .format(*tuple(int(x) for x in g)))
    

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: