Print all 3 by 3 sturdy squares

Question

A sturdy square (akin to a magic square) is an arrangement of the integers 1 to \$N^2\$ on an \$N\$ by \$N\$ grid such that every 2 by 2 subgrid has the same sum.

For example, for \$N = 3\$ one sturdy square is

1 5 3
9 8 7
4 2 6

because the four 2 by 2 subgrids

1 5
9 8

5 3
8 7

9 8
4 2

8 7
2 6

all sum to the same amount, 23:

$$23 = 1 + 5 + 9 + 8 = 5 + 3 + 8 + 7 = 9 + 8 + 4 + 2 = 8 + 7 + 2 + 6$$

Now there are sturdy squares for higher values of N and even rectangular versions but your only task in this challenge is to output all possible 3 by 3 sturdy squares. There are exactly 376 distinct 3 by 3 sturdy squares, including those that are reflections or rotations of others, and not all of them have the same sum of 23.

Write a program or function that takes no input but prints or returns a string of all 376 sturdy squares in any order, separated by empty lines, with up to two optional trailing newlines. Each square should consist of three lines of three space separated nonzero decimal digits.

Here is a valid output example:

Your program must produce these same 376 sturdy squares, just not necessarily in this order. The output does not need to be deterministic, i.e. you could output them in different orders on different runs as long as they are all there.

The shortest code in bytes wins.

^{The topic of sturdy squares originated with this chat message of mine which led to a large amount of discussion on their properties and how to generate them. Props to Peter Taylor, feersum, and Sp3000 for continuing the discussion, and especially to El'endia Starman for drafting a corresponding OEIS sequence.}

I'm not sure if I interpreted the trailing newline rule correctly. The output of my previous revision ended with 5 7 3\n\n, so there is one blank line after the last square. Is that admissible? — Dennis, Oct 22, 2015 at 1:04
Maybe host the output somewhere else so that it is not too long on this page. — Ryan Dougherty, Oct 22, 2015 at 18:41

El'endia Starman · Accepted Answer · 2015-10-23 01:03:28Z

Python 3, 169 168 164 bytes

Took the program I used to investigate these sturdy squares/rectangles and golfed it wayyyy down. Golfed off 4 bytes thanks to otakucode.

from itertools import*
r=range(1,10)
for p in permutations(r,6):
 x,y=p[0],p[5];q=p[:5]+(x+p[3]-p[2],y,y+p[1]-x,p[2]+y-x)
 if set(q)==set(r):print('%s %s %s\n'*3%q)

Explanation

Given a partially-filled sturdy square like this,

a b c
d e ?
g ? ?

The remaining three entries are uniquely determined, and are a+d-c, a+b-g, and c+g-a. So I generate all permutations of 0..8 with six elements, calculate the rest, and then check to see whether the set of this is the same as the set of 0..8. If it is, I print out the grid.

For reference, here's the original (with comments and extraneous code removed):

from itertools import permutations as P

n = 3
m = 3
permutes = P(range(m*n), m+n)

counter = 0
for p in permutes:
    grid = [p[:n]]
    for i in range(m-1):
        grid.append([p[n+i]]+[-1]*(n-1))
    grid[1][1] = p[-1]

    s = p[0]+p[1]+p[n]+p[-1]

    has = list(p)

    fail = 0
    for y in range(1,m):
        for x in range(1,n):
            if x == y == 1: continue

            r = s-(grid[y-1][x-1] + grid[y-1][x] + grid[y][x-1])

            if r not in has and 0 <= r < m*n:
                grid[y][x] = r
                has.append(r)
            else:
                fail = 1
                break

        if fail: break

    if not fail:
        counter += 1

print(counter)

Very nice approach! You can still save a few bytes though... in the loop, x,y=p[0],p[5] then q=p+(y+p[3]-p[2],y+p[1]-x,p[2]+x-y) — otakucode, Oct 23, 2015 at 0:18

isaacg · Accepted Answer · 2015-10-23 16:25:36Z

9

Pyth, 38 34 33 32 bytes

Vfq2l{sMX2.DR2.:T5b.pS9Vc3NjdH)k

5 bytes saved in formatting by Jakube

1 byte saved by switching to Peter Taylor's substrings of length five, remove the middles approach

Takes about a minute and a half to run on my machine.

How it works at the high level:

Generate all permutations (.pS9)
Form length 5 substrings (.:T5)
Remove the center element of each (.DR2)
Append a newline to the center element, marking it with a necessarily different sum (X2 ... b)
Filter for the squares where all such sums are equal (fq2l{)
Format and print (V ... Vc3NjdH)k)

edited Oct 23, 2015 at 16:25

answered Oct 22, 2015 at 7:21

isaacg

42k5 gold badges71 silver badges213 bronze badges

\$\begingroup\$ Chop N inside the loop (V...Vc3N) instead of before the loop (VcL3...VN). Saves one additional byte. \$\endgroup\$
– Jakube
Oct 23, 2015 at 10:01

Add a comment |

Dennis · Accepted Answer · 2015-10-22 14:22:56Z

CJam, 40 38 bytes

A,1>e!3f/{2{2few:::+z}*:|,1=},Ma*Sf*N*

Thanks to @PeterTaylor for golfing off 2 bytes!

This finishes instantly using the Java interpreter. It works using the online interpreter as well, but it requires a little patience. Try it online.

Test run

$ cjam sturdy-squares.cjam | head -n 8
1 5 3
9 8 7
4 2 6

1 5 6
8 7 3
4 2 9

$ cjam sturdy-squares.cjam | tail -n 8

9 5 4
2 3 7
6 8 1

9 5 7
1 2 3
6 8 4
$

How it works

A,1>     e# Push [1 ... 9].
e!       e# Push the array of all permutations of that array.
3f/      e# Split each into rows of length 3.
{        e# Filter; push the permutation, then:
  2{     e#   Do the following twice:
    2few e#     Split each row into overlapping splices of length 2.
         e#       [a b c] -> [[a b] [b c]]
    :::+ e#     Reduce each innermost vector to its sum.
         e#       [[a b] [b c]] -> [a+b b+c]
    z    e#     Transpose rows with columns.
  }*     e#   The result is [[s t] [u v]], the sums of all 2x2 squares.
  :|     e#   Perform set union of the pairs of sums.
  ,1=    e#   Check if the length of the result is 1 (unique sum).
},       e# Keep the array if the result was 1.
{        e# For each kept array:
  Sf*    e#   Join the elements of its rows, separating by spaces.
  ~M     e#   Dump the resulting strings and an empty string on the stack.
}%       e# Collect everything in an array.
N*       e# Join the strings, separating by linefeeds.

Now that I've managed to golf my answer enough to stay one char ahead: Ma*Sf*N* saves two over {Sf*~M}%N* — Peter Taylor, Oct 22, 2015 at 14:07

Sp3000 · Accepted Answer · 2015-10-23 00:01:48Z

6

Python 3.5, 135 bytes

from itertools import*
for x in permutations(range(1,10)):eval((("=="+"+x[%s]"*3)*4)[2:]%(*"013125367578",))and print("%d %d %d\n"*3%x)

Directly checks the sum of each square, minus the middle. Most likely still golfable by the "itertools is unnecessary" rule-of-thumb.

edited Oct 23, 2015 at 0:01

answered Oct 22, 2015 at 5:23

Sp3000

61.9k13 gold badges114 silver badges287 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

5

Mathematica 147 166 155 149 bytes

This generates the permutations of {1,2,3...9} and selects cases for which

(sum of digits at positions {1,2,4,5}) =

(sum of digits at positions {2,3,5,6}) =

(sum of the digits at positions {4,5,7,8}) =

(sum of the digits at positions {5,6,8,9})

f@s_:=Length@Tally[Tr@Extract[s,#]&/@Table[{{0},{1},{3},{4}}+k,{k,{1,2,4,5}}]]>1;
Row[Grid/@(#~Partition~3&/@Select[Permutations@Range@9,f@#&]),"\n"]

Output (a partial look)

Length[%]

376

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Oct 22, 2015 at 0:44

DavidC

25.3k2 gold badges52 silver badges105 bronze badges

Add a comment |

Peter Taylor · Accepted Answer · 2015-10-22 14:06:57Z

5

CJam (39 37 bytes)

A,1>e!{5ew{2Mtz}2*::+)-!},3f/Ma*Sf*N*

Online demo (warning: may take over a minute to run, triggering "Abort this script?" prompts from the browser).

Works by filtering all possible grids using 5ew to map

[a b c d e f g h i]

to

[[a b c d e]
 [b c d e f]
 [c d e f g]
 [d e f g h]
 [e f g h i]]

and then discarding the middle element and the middle element of each other element to get

[[a b d e]
 [b c e f]
 [d e g h]
 [e f h i]]

which are the four squares.

edited Oct 22, 2015 at 14:06

answered Oct 22, 2015 at 12:33

Peter Taylor

43.1k4 gold badges70 silver badges168 bronze badges

\$\begingroup\$ Wow, that's brilliant. \$\endgroup\$
– El'endia Starman
Oct 23, 2015 at 1:05

Add a comment |

Community · Accepted Answer · 2017-04-13 12:39:09Z

Python2 327 271 270 263 260 bytes

z,v,s={},3,range(1,10)
while len(z)<376:
 for i in range(8):v=hash(`v`);s[i],s[v%9]=s[v%9],s[i]
 m=map(lambda i:sum(s[i:i+5])-s[i+2],[0,1,3,4]);T=tuple(s)
 if all(x==m[0] for x in m) and not T in z:
  z[T]=1;print '%i %i %i\n'*3 % tuple(s[0:3]+s[3:6]+s[6:9])

------------

This is... not so short but it uses no libraries. This randomly permutes a square, checks it for magicness, prints it, and records it to prevent duplicates. After it has printed 376 unique magic squares, it stops.

I borrowed the Pseudo Random Number Generator from Keith Randall's entry for the golf named " Build a random number generator that passes the Diehard tests "

z,v={},3
def R(x,y):global v;v=hash(`v`);return v
while len(z)<376:
 s=sorted(range(1,10),cmp=R)
 m=[sum(q) for q in map(lambda p:s[p[0]:p[1]+1]+s[p[2]:p[3]+1], [[i,i+1,i+3,i+4] for i in [0,1,3,4]] )]
 if all(x==m[0] for x in m) and not tuple(s) in z.keys():
  z[tuple(s)]=1;print '%i %i %i\n'*3 % tuple(s[0:3]+s[3:6]+s[6:9])

De-golfed

# each magic square is an array of 9 numbers
#
#for example [1 9 3 7 2 5 6 4 8] 
#
#represents the following square
#
#1 9 3
#7 2 5
#6 4 8
#
# to generate a random square with each number represented only once,
# start with [1 2 3 4 5 6 7 8 9] and sort, but use a random comparison
# function so the sorting process becomes instead a random permutation.
# 
# to check each 2x2 subsquare for sums, look at the indexes into the
# array: [[0,1,3,4] = upper left,[1,2,4,5] = upper right, etc.
#
# to keep track of already-printed magic squares, use a dictionary    
# (associative array) where the 9-element array data is the key. 

from random import *
def magic(s):
 quads=[]
 for a,b,c,d in [[0,1,3,4],[1,2,4,5],[3,4,6,7],[4,5,7,8]]:
  quads+=[s[a:b+1]+s[c:d+1]]
 summ=[sum(q) for q in quads]
 same= all(x==summ[0] for x in summ)
 #print quads
 #print 'sum',summ
 #print 'same',same
 return same

magicsquares={}
while len(magicsquares.keys())<376:
        sq = sorted(range(1,10),key=lambda x:random())
        if magic(sq) and not magicsquares.has_key(tuple(sq)):
                magicsquares[tuple(sq)]=1
                print sq[0:3],'\n',sq[3:6],'\n',sq[6:9],'\n'

Nothing random needs to be happening. There are exactly 376 distinct square solutions and you need to output each of them exactly once. — Calvin's Hobbies, Oct 22, 2015 at 2:48
i did print exactly 376 distinct square solutions, and i output each of them exactly once. randomness is not banned in the description, nor is it banned in the 'standard loopholes' meta.codegolf.stackexchange.com/questions/1061/… — don bright, Oct 22, 2015 at 2:58
You can use a worse random number generator as long as it gives you all of the squares you need. — lirtosiast, Oct 22, 2015 at 4:22

Cristian Lupascu · Accepted Answer · 2015-10-22 11:29:33Z

1

Ruby 133

a=[]
[*1..9].permutation{|x|[0,1,3,4].map{|i|x[i]+x[i+1]+x[i+3]+x[i+4]}.uniq.size<2&&a<<x.each_slice(3).map{|s|s*' '}*'
'}
$><<a*'

'

Straightforward brute force approach. Test it here.

answered Oct 22, 2015 at 11:29

Cristian Lupascu

8,6792 gold badges25 silver badges52 bronze badges

Add a comment |

miles · Accepted Answer · 2016-07-07 07:58:02Z

J, 83 bytes

([:;@,(<LF),.~[:(<@(LF,~":)"1@#~([:*/2=/\[:,2 2+/@,;._3])"2)(3 3)($"1)1+!A.&i.])@9:

This is a function that outputs a string containing the 376 sturdy squares. Uses brute-force, generates all permutations of 1 thru 9, shape each into a 3x3 array, and filters it by checking if the sums of each 2x2 subarray are equal. Completes in half a second.

Usage

   f =: ([:;@,(<LF),.~[:(<@(LF,~":)"1@#~([:*/2=/\[:,2 2+/@,;._3])"2)(3 3)($"1)1+!A.&i.])@9:
   $ f ''  NB. A function has to take something to be invoked,
           NB. but in this case it is not used by the function
   37 {. f ''  NB. Take the first 37 characters
1 5 3
9 8 7
4 2 6

1 5 6
8 7 3
4 2 9

   _38 {. f ''  NB. Take the last 38 characters
9 5 4
2 3 7
6 8 1

9 5 7
1 2 3
6 8 4


   NB. The output string ends with two newlines

Razetime · Accepted Answer · 2020-10-30 05:59:40Z

APL (Dyalog Extended), 38 bytes

s⌿⍨1=≢∘∪⍤1⍪+/,⍤⊢⌺1 2 2⊢s←3 3⍴⍤1⌂pmat 9

Try it online!

Uses the builtin dfns.pmat to generate required permutations.

Will add an explanation soon.

Made with golfing help from Adám, who also ran the program on his machine for checking. ↓

Explanation

s⌿⍨1=≢∘∪⍤1⍪+/,⍤⊢⌺1 2 2⊢s←3 3⍴⍤1⌂pmat 9
                             1⌂pmat 9 matrix of permutations of 1..9
                      s←3 3⍴⍤         convert each to 3x3 matrix, and store in s
              ⊢⌺1 2 2⊢                get all overlapping 2x2 squares in each of those   
        1⍪+/,⍤                        sum the flattened 2x2's of each
  1=≢∘∪⍤                              is there only 1 unique sum?
                                      this creates a bitmask for filtering each 3x3
s⌿⍨                                   filter s by that

caird coinheringaahin g · Accepted Answer · 2020-10-12 15:49:46Z

Jelly, 22 bytes

9Œ!s€3+Ɲ€Z$⁺FEƲƇG€j⁾¶¶

Try it online!

Very inefficient. Times out on TIO, and takes around 4m30s on my local computer. Uses Dennis' method for finding the sums of the 2x2 submatrices. The last 6 bytes could be removed if the output format was more permissive. Outputs in the same order as in the question.

How it works

9Œ!s€3+Ɲ€Z$⁺FEƲƇG€j⁾¶¶ - Main link. No arguments
9Œ!                    - Yield all permutations of [1, 2, 3, 4, 5, 6, 7, 8, 9]
   s€3                 - Split each into a 3x3 matrix
              ƲƇ       - Keep those for which the following is true:
       Ɲ€              -   Over each neighbouring pair in each row:
      +                -     Take the sum
         Z             -    Transpose
          $⁺           -    Do this again
            F          -    Flatten
             E         -    Are all elements equal?
                G€     - Join each row by spaces and then join rows by newlines
                  j⁾¶¶ - Join the final matrices with two newlines

Shaggy · Accepted Answer · 2020-10-12 16:17:58Z

0

Japt, 34 bytes

+9 bytes for the output formatting :\

9õ á mò3 kÈ®ä+ÃÕ®ä+Ãrâ ÊÉÃ®m¸·ÃqR²

Try it

answered Oct 12, 2020 at 16:17

Shaggy

41.9k4 gold badges34 silver badges93 bronze badges

Add a comment |

Stack Exchange Network

Print all 3 by 3 sturdy squares

12 Answers 12

Python 3, 169 168 164 bytes

Explanation

Pyth, 38 34 33 32 bytes

CJam, 40 38 bytes

Test run

How it works

Python 3.5, 135 bytes

Mathematica 147 166 155 149 bytes

CJam (39 37 bytes)

Python2 327 271 270 263 260 bytes

------------

Ruby 133

J, 83 bytes

Usage

APL (Dyalog Extended), 38 bytes

Explanation

Jelly, 22 bytes

How it works

Japt, 34 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
number
arithmetic
number-theory
grid
or ask your own question.

Linked

Hot Network Questions

Print all 3 by 3 sturdy squares

12 Answers 12

Python 3, 169 168 164 bytes

Explanation

Pyth, 38 34 33 32 bytes

CJam, 40 38 bytes

Test run

How it works

Python 3.5, 135 bytes

Mathematica 147 166 155 149 bytes

CJam (39 37 bytes)

Python2 327 271 270 263 260 bytes

------------

Ruby 133

J, 83 bytes

Usage

APL (Dyalog Extended), 38 bytes

Explanation

Jelly, 22 bytes

How it works

Japt, 34 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfnumberarithmeticnumber-theorygrid or ask your own question.

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
number
arithmetic
number-theory
grid
or ask your own question.