Enigmatic Code

Programming Enigma Puzzles

Enigma 1760: Squares and cubes

From New Scientist #2928, 3rd August 2013 [link]

Enigma 1760

Each of the 12 white squares in the cross-figure grid shown is to be filled with a single digit. The four two-digit numbers and the four three-digit numbers created are either perfect squares or perfect cubes. These squares and cubes are all distinct, and one of the down answers is both a square and a cube. What are the answers to 6 across and 7 across?

[enigma1760]

Advertisements

7 responses to “Enigma 1760: Squares and cubes

  1. Jim Randell 31 July 2013 at 6:49 pm

    I wrote a generic cross-figure solver for Enigma 1755 (which can also be used to solve Enigma 1740 and Enigma 1730 – all also set by Peter Chamberlain). Here it is used to solve this puzzle. It runs in 66ms.

    from enigma import irange, printf
    
    # a generic cross figure solver
    
    def match(t, ns):
      for n in ns:
        if all(a in ('?', b) for (a, b) in zip(t, n)):
          yield n
    
    def update(g, t, n):
      g = list(g)
      for (i, d) in zip(t, n):
        g[i] = d
      return g
    
    class CrossFigure(object):
    
      def __init__(self, grid):
        self.grid = list(grid)
        self.answers = list()
        self.groups = list()
        self.fn = (lambda grid: True)
    
      # set answers and their candidate solutions
      def set_answer(self, answers, candidates):
        candidates = list(str(x) for x in candidates)
        for a in answers: self.answers.append((a, candidates))
    
      # set groups of distinct digits
      def set_distinct(self, groups):
        self.groups.extend(groups)
    
      # set final check for a solution
      def set_check(self, fn):
        self.fn = fn
    
      # check the distinct groups
      def _check_distinct(self, grid):
        for d in self.groups:
          s = tuple(grid[i] for i in d if grid[i] != '?')
          if len(s) > 0 and len(set(s)) < len(s): return False
        return True
    
      # check the answers match their candidates
      def _check_answers(self, grid):
        # check all answers match the candidates
        for (ans, cs) in self.answers:
          t = ''.join(grid[i] for i in ans)
          if t not in cs: return False
        # and run any final check
        return self.fn(grid)
    
      # the solver
      def solve(self, grid=None, seen=None):
        if grid is None: grid = self.grid
        if seen is None: seen = set()
        # is the grid complete?
        if '?' not in grid:
          # skip duplicated solutions
          s = ''.join(grid)
          if s not in seen:
            seen.add(s)
            if self._check_answers(grid):
              yield grid
        else:
          # find a partially filled out answer
          ts = list()
          for (ans, cs) in self.answers:
            t = tuple(grid[i] for i in ans)
            n = t.count('?')
            if n > 0: ts.append((n, t, ans, cs))
          # with the fewest missing letters
          (n, t, ans, cs) = min(ts)
          # and fill it out
          for n in match(t, cs):
            grid2 = update(grid, ans, n)
            if self._check_distinct(grid2):
              for x in self.solve(grid2, seen):
                yield x
    
      def get_answers(self, grid):
        for (ans, cs) in self.answers:
          yield ''.join(grid[i] for i in ans)
    
    # consider the grid:
    #
    #  A B # C
    #  # D E F
    #  G H I #
    #  J # K L
    
    # label the indices to make things easier
    (A, B, C, D, E, F, G, H, I, J, K, L) = irange(0, 11)
    
    # 2- and 3- digit squares and cubes
    squares2 = list(i ** 2 for i in irange(4, 9))
    squares3 = list(i ** 2 for i in irange(10, 31))
    cubes2 = list(i ** 3 for i in irange(3, 4))
    cubes3 = list(i ** 3 for i in irange(5, 9))
    
    # and numbers that are both
    sc = set(squares2 + squares3).intersection(cubes2 + cubes3)
    
    # create an empty grid
    p = CrossFigure('????????????')
    # solutions that are 2-digit squares or cubes
    p.set_answer([(A, B), (C, F), (G, J), (K, L)], squares2 + cubes2)
    # solutions that are 3-digit squares or cubes
    p.set_answer([(B, D, H), (D, E, F), (E, I, K), (G, H, I)], squares3 + cubes3)
    
    # final check
    def check(g):
      (A, B, C, D, E, F, G, H, I, J, K, L) = g
      return all((
        # 2-digit solutions are distinct
        len(set((A+B, C+F, G+J, K+L))) == 4,
        # 3-digit solutions are distinct
        len(set((B+D+H, D+E+F, E+I+K, G+H+J))) == 4,
        # one of the down answers is both a square and a cube
        any(int(x) in sc for x in (B+D+H, C+F, E+I+K, G+J)),
      ))
    
    p.set_check(check)
    
    # solve it
    for (A, B, C, D, E, F, G, H, I, J, K, L) in p.solve():
      printf("[{A} {B} # {C}]\n[# {D} {E} {F}]\n[{G} {H} {I} #]\n[{J} # {K} {L}]")
      printf("6ac = {G}{H}{I}, 7ac = {K}{L}\n")
    

    Solution: The answer to 6 across is 324. The answer to 7 across is 16.

    This is what the completed grid looks like:

    Enigma 1760 - Solution

    • Jim Randell 1 August 2013 at 9:31 am

      I’ve added this code to my enigma.py library, so that it can be used to solve similar puzzles.

      from enigma import CrossFigure, irange, printf
      
      # consider the grid:
      #
      #  A B # C
      #  # D E F
      #  G H I #
      #  J # K L
      
      # label the indices to make things easier
      (A, B, C, D, E, F, G, H, I, J, K, L) = irange(0, 11)
      
      # 2- and 3- digit squares and cubes
      squares2 = list(i ** 2 for i in irange(4, 9))
      squares3 = list(i ** 2 for i in irange(10, 31))
      cubes2 = list(i ** 3 for i in irange(3, 4))
      cubes3 = list(i ** 3 for i in irange(5, 9))
      
      # and numbers that are both
      sc = set(squares2 + squares3).intersection(cubes2 + cubes3)
      
      # create an empty grid
      p = CrossFigure('????????????')
      # solutions that are 2-digit squares or cubes
      p.set_answer([(A, B), (C, F), (G, J), (K, L)], squares2 + cubes2)
      # solutions that are 3-digit squares or cubes
      p.set_answer([(B, D, H), (D, E, F), (E, I, K), (G, H, I)], squares3 + cubes3)
      
      # final check
      def check(g):
        (A, B, C, D, E, F, G, H, I, J, K, L) = g
        return all((
          # 2-digit solutions are distinct
          len(set((A+B, C+F, G+J, K+L))) == 4,
          # 3-digit solutions are distinct
          len(set((B+D+H, D+E+F, E+I+K, G+H+J))) == 4,
          # one of the down answers is both a square and a cube
          any(int(x) in sc for x in (B+D+H, C+F, E+I+K, G+J)),
        ))
      
      p.set_check(check)
      
      # solve it
      for (A, B, C, D, E, F, G, H, I, J, K, L) in p.solve():
        printf("[{A} {B} # {C}]\n[# {D} {E} {F}]\n[{G} {H} {I} #]\n[{J} # {K} {L}]")
        printf("6ac = {G}{H}{I}, 7ac = {K}{L}\n")
      
      • geoffrounce 12 March 2016 at 2:28 pm
        % A solution in MiniZinc
        include "globals.mzn";
        solve satisfy;
        
        %    GRID       ANSWER
        %  A B # C     2 5 # 6
        %  # D E F     # 1 4 4
        %  G H I #     3 2 4 #
        %  J # K L     6 # 1 6
         
        var 1..9:A; var 1..9:B; var 1..9:C; var 1..9:D; var 1..9:E; 
        var 1..9:F; var 1..9:G; var 1..9:H; var 1..9:I; var 1..9:J; 
        var 1..9:K; var 1..9:L;
        
        array[1..12] of var int : digits = [A,B,C,D,E,F,G,H,I,J,K,L];
        
        % 2 digit numbers
        var 10..99: AB; var 10..99: CF; var 10..99: GJ; var 10..99: KL; 
        
        % 3 digit numbers
        var 100..999: DEF; var 100..999: GHI; var 100..999: BDH;
        var 100..999: EIK;
         
        constraint alldifferent([AB,CF,GJ,KL]) /\ alldifferent([DEF,GHI,BDH,EIK]);
        
        % Sets of 2 and 3 digit squares and cubes
        set of int: sq2 = {16,25,36,49,64,81};
        set of int: sq3 = {100, 121, 144, 169, 196, 225, 256, 289, 324, 361,
        400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961};
        
        set of int: cb2 = {27, 64};
        set of int: cb3 = {125, 216, 243, 512, 729};
        
        % Form 2 and 3 digit numbers in the grid
        constraint AB = 10*A + B /\ CF = 10*C + F /\ GJ = 10*G + J /\ KL = 10*K + L;
        constraint DEF = 100*D + 10*E + F /\ GHI = 100*G + 10*H + I
        /\ BDH = 100*B + 10*D + H /\ EIK = 100*E + 10*I + K;
        
        % 2 digit numbers are square or cube numbers
        constraint (AB in sq2 \/ AB in cb2) /\ (CF in sq2 \/ CF in cb2) 
        /\ (GJ in sq2 \/ GJ in cb2)  /\ (KL in sq2 \/ KL in cb2);
        
        % 3 digit numbers are square or cube numbers
        constraint (DEF in sq3 \/ DEF in cb3) /\ (GHI in sq3 \/ GHI in cb3)
        /\ (BDH in sq3 \/ BDH in cb3) /\ (EIK in sq3 \/ EIK in cb3);
        
        % one answer down is both a square and a cube number
        constraint (GJ in sq2 /\ GJ in cb2) \/ (CF in sq2 /\ CF in cb2)
        \/ (BDH in sq3 /\ BDH in cb3) \/ (EIK in sq3 /\ EIK in cb3);
        
        output["A,B,C,D,E,F,G,H,I,J,K,L = " ++ show(digits)];
        
        % A,B,C,D,E,F,G,H,I,J,K,L = [2, 5, 6, 1, 4, 4, 3, 2, 4, 6, 1, 6]
        % Finished in 82msec
        %
        
  2. Ahmet Saracoğlu 31 July 2013 at 6:50 pm

    Same approach before, it is easy to modify the previous code, but I like to change the algorithm this time,

  3. ahmet çetinbudaklar 2 August 2013 at 8:42 pm

    a^2=16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484,529,576,625,676,729,784,841,900,961

    b^3=27,64,125,216,343,512,729

    64 is the only common number for a^2 and b^3

    By trial and error we can solve the full grid.

  4. ahmet çetinbudaklar 3 August 2013 at 2:43 pm

    Jim thank you for your warning , very true , there are two common numbers the other being 729 as you say, however the solution lies in one of them only.

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: