@mearnest/

Magic Square Preserving Permutations

Python 2.7

A brute force search to find all permutations which preserve magic squares of order 4.

fork
loading
Files
  • main.py
  • order4magicsquares.txt
main.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def main():
  #This part just processes the raw data
  with  open('order4magicsquares.txt') as f:
    data = f.read().split('\n')
    def prepare(raw_string):
      return map(lambda x:int(x)-1,raw_string.split(' '))
    all_squares = map(prepare,data)
  #Find the permutations taking the first square
  #to all other squares
  first_square = all_squares[0]
  perms = [permutation_between(first_square,sq) 
          for sq in all_squares[1:]]
  #see which of these permutations, when applied to 
  #all magic squares, result in a magic square.
  magic_preserving_perms = []   
  for (i,p) in enumerate(perms):
    if i % 88 == 0:
      print(str(10*i/88)+' % complete')
    if all([is_magic(apply_perm(p,s)) for s in all_squares]):
      magic_preserving_perms.append(p)
  #Display them all
  for m in magic_preserving_perms: 
    nice_print(m) 
    
def is_magic(s):
    row_sums = [sum(s[4*i:4*(i+1)]) for i in range(4)]
    col_sums = [sum(s[i::4]) for i in range(4)]
    diag_sums = [sum(s[::5]),sum(s[3:15:3])]
    return len(set(row_sums+col_sums+diag_sums))==1
    
def apply_perm(permutation,square):
    return [square[permutation[i]] for i in range(16)]
    
def permutation_between(square1,square2):
    return mult_perm(invert(square1),square2)
    
def invert(P):
    aux = [ [P[i],i] for i in range(len(P))]
    aux.sort()
    return [ x[1] for x in aux]
    
def mult_perm(P,Q):
    """Given permutations P,Q of [0,..,n-1], returns P of Q"""
    return [P[Q[i]] for i in range(len(P))]
    
def nice_print(m):
  print
  def space_out(n):
    return ' '*(len(str(n))==1)+str(n)
  for i in range(4):
    print ' '.join(map(space_out,m[4*i:4*(i+1)]))

main()