Enigmatic Code

Programming Enigma Puzzles

Enigma 1553: Squares from squares

From New Scientist #2716, 11th July 2009 [link]

Your task is to place a digit in each of these 16 squares (above).

When you have finished, the grid should have the following properties:

• no digit occurs more than once in any row

• the sum of the four digits in each row is the same

• the sum of the four digits in each column is the same

• each row should form a different four-figure perfect square

Find the four perfect squares, in increasing order.

[enigma1553]

Advertisements

4 responses to “Enigma 1553: Squares from squares

  1. Jim Randell 12 March 2012 at 10:35 pm

    Here’s my original Perl program. It runs in 11ms.

    use strict;
    
    my ($n, $r, $s);
    
    # each row is a 4 digit square
    # the digits sum to the same value
    my %sum = ();
    for $n (36..99) {
      $r = $n * $n;
      # no repeated digits in a row
      next if $r =~ /(.).*\1/;
    
      # sum the digits
      $s = 0;
      for (split '', $r) {
        $s += $_;
      }
    
      # and group by the sum
      push @{$sum{$s}}, $r;
    }
    
    my ($k, $v, $c);
    my ($i1, $i2, $i3, $i4);
    my ($r1, $r2, $r3, $r4);
    my (@r1, @r2, @r3, @r4);
    while (($k, $v) = each %sum) {
      # we need 4 rows
      $n = @{$v};
      next if $n < 4;
    
      # find 4 rows where the columns sum to the same value
      for $i1 (0..$n-4) {
        $r1 = $v->[$i1];
        @r1 = split '', $r1;
        for $i2 ($i1+1..$n-3) {
          $r2 = $v->[$i2];
          @r2 = split '', $r2;
          for $i3 ($i2+1..$n-2) {
            $r3 = $v->[$i3];
            @r3 = split '', $r3;
            for $i4 ($i3+1..$n-1) {
              $r4 = $v->[$i4];
              @r4 = split '', $r4;
    
              # columns sum to the same value
              $c = $r1[0] + $r2[0] + $r3[0] + $r4[0];
              next unless $c == $r1[1] + $r2[1] + $r3[1] + $r4[1];
              next unless $c == $r1[2] + $r2[2] + $r3[2] + $r4[2];
              next unless $c == $r1[3] + $r2[3] + $r3[3] + $r4[3];
    
              print "($r1 $r2 $r3 $r) r=$k c=$c\n";
            }
          }
        }
      }
    }
    

    Solution: The four squares are 1764, 3249, 5184 and 9801.

    • Jim Randell 12 March 2012 at 10:37 pm

      And this is how I would write it now in Python. It runs in 43ms.

      from collections import defaultdict
      from itertools import combinations
      from enigma import irange, is_duplicate, split, printf
      
      # 4 digit squares grouped by sum
      s4 = defaultdict(list)
      for n in irange(36, 99):
        r = n ** 2
        # no repeated digits
        if is_duplicate(r): continue
        # group by sum (as strings)
        s4[sum(split(r, int))].append(str(r))
      
      # we need 4 rows with the same sum
      for (r, v) in s4.items():
        if len(v) < 4: continue
      
        for rs in combinations(v, 4):
          # find the sums of the columns
          cs = set(sum(int(r[i]) for r in rs) for i in irange(0, 3))
          # and check they are all the same
          if len(cs) > 1: continue
      
          printf("{rs} r={r} c={c}", rs=sorted(int(s) for s in rs), c=cs.pop())
      
  2. Hugh Casement 23 February 2016 at 7:56 am

    If we place the rows in the right order, one column reads 6084 = 78².
    The column sum is the same as the row sum (18).
    Only one column (the last) contains a repeated digit.
    So additional conditions could have been imposed.  Would that have made the puzzle easier or harder to solve without a computer?

    • geoffrounce 24 February 2016 at 6:17 pm
      % A solution in MiniZinc
      
      include "globals.mzn";
      solve satisfy;
      
      predicate is_square(var int: c) =
         let {
            var 1..ceil(pow(int2float(ub(c)),(1/2.0))): z
         } in z * z = c ;
      
      % rows of square grid are abcd, efgh, ijkl and mnop
      % 16 square grid variables
      var 0..9: a;  var 0..9: b;  var 0..9: c;  var 0..9: d; 
      var 0..9: e;  var 0..9: f;  var 0..9: g;  var 0..9: h; 
      var 0..9: i;  var 0..9: j;  var 0..9: k;  var 0..9: l; 
      var 0..9: m;  var 0..9: n;  var 0..9: o;  var 0..9: p; 
      
      % four perfect squares
      var 1000..9999: sq1;  var 1000..9999: sq2; 
      var 1000..9999: sq3;  var 1000..9999: sq4; 
      
      % check rows have have different digits
      constraint all_different ([a,b,c,d]) /\ a > 0;
      constraint all_different ([e,f,g,h]) /\ e > 0;
      constraint all_different ([i,j,k,l]) /\ i > 0;
      constraint all_different ([m,n,o,p]) /\ m > 0;
      
      % check sums of digits in rows are the same
      constraint a + b + c + d == e + f + g + h /\
                 e + f + g + h == i + j + k + l /\
                 i + j + k + l == m + n + o + p; 
                 
      % check sum of digits in columns are the same
      constraint  b > 0 /\ c > 0 /\ d > 0 /\
                  a + e + i + m == b + f + j + n /\
                  b + f + j + n == c + g + k + o /\
                  c + g + k + o == d + h + l + p;
      
      % build four perfect squares
      constraint sq1 = 1000*a + 100*b + 10*c + d;
      constraint sq2 = 1000*e + 100*f + 10*g + h;
      constraint sq3 = 1000*i + 100*j + 10*k + l;
      constraint sq4 = 1000*m + 100*n + 10*o + p;
      
      % check squares 
      constraint is_square(sq1) /\ is_square(sq2) /\ 
      is_square(sq3) /\ is_square(sq4) /\
      sq1 < sq2 /\ sq2 < sq3 /\ sq3 < sq4;
      
      output ["Four perfect squares are " ++ show(sq1) ++ ", " 
      ++ show(sq2) ++ ", " ++ show (sq3) ++ " and " ++ show(sq4)];
      
      % Four perfect squares are 1764, 3249, 5184 and 9801
      % ----------
      % Finished in 83msec
      %
      

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: