So far I have been using python to generate permutations of matrices for finding magic squares. So what I have been doing so far (for 3x3 matrices) is that I find all the possible permutations of the set {1,2,3,4,5,6,7,8,9} using itertools.permutations, store them as a list and do my calculations and print my results.
Now I want to find out magic squares of order 4. Since finding all permutations means 16! possibilities, I want to increase efficiency by placing likely elements in the corner, for example 1, 16 on diagonal one corners and 4, 13 on diagonal two corners.
So how would I find permutations of set {1,2....16} where some elements are not moved is my question
#Rajiv Ravishankar
#rravisha
#21-301 Assignment #1, Qns 4
from numpy import matrix
import itertools
def eligCheck(m):
#We know certain properties of magic squares that can help identify if a 3x3 matrix is a magic square or not
#These properties include the following checks listed below.
#
#
#The main purpose of this function is to check is a 3x3 matrix is a magic square without having to add all the
#rows, columns and diagonals.
flag=0
#Check 1 if the matrix is indeed 4x4
if (len(m)==4 and len(m[0])==4 and len(m[1])==4 and len(m[2])==4):
flag=flag+1
#Check 2 if the 2nd diagonal adds up
if (m[0][3] + m[1][2] + m[2][1] + m[3][0] == 34):
flag=flag+1
#Checks 2 if the first diagonal adds up
if (m[0][0] + m[1][1] + m[2][2] + m[3][3] == 34):
flag=flag+1
#To save resources and increase efficency, only if all three checks return true will we add the rows and columns to check.
if (flag==3):
return True
else:
return False
def elementAdder(m):
#This function is to be called only AFTER eligCheck() returns TRUE for a given matrix. Since a 4x4 matrix that satisfies the checks
#in eligCheck() does not mean that it is a magic square, we add each row, each column and both diagonals an see if the sum
#is equal to 15. Splitting into two function save processing power.
#
#
#Checking if all rows add up to 15
flag=0
#Check 1 if row 1 adds up
if (m[0][0]+m[0][1]+m[0][2]+m[0][3] == 34):
flag=flag+1
else:
return False
#Check 2 if row 2 adds up
if (m[1][0]+m[1][1]+m[1][2]+m[1][3] == 34):
flag=flag+1
else:
return False
#Check 3 if row 3 adds up
if (m[2][0]+m[2][1]+m[2][2]+m[2][3] == 34):
flag=flag+1
else:
return False
#Check if row 4 adds up
if (m[3][0]+m[3][1]+m[3][2]+m[3][3] == 34):
flag=flag+1
else:
return False
#Check 4 if column 1 adds up
if (m[0][0]+m[1][0]+m[2][0]+m[3][0] == 34):
flag=flag+1
else:
return False
#Check 5 if column 2 adds up
if (m[0][1]+m[1][1]+m[2][1]+m[3][1] == 34):
flag=flag+1
else:
return False
#Check 6 if column 3 adds up
if (m[0][2]+m[1][2]+m[2][2]+m[3][2] == 34):
flag=flag+1
else:
return False
#Check 7 if column 4 adds up
if (m[0][3]+m[1][3]+m[2][3]+m[3][3] == 34):
flag=flag+1
else:
return False
#Note that diagonal checks have already been verified in eligCheck() represents the diagonal from left to right
#The strategy here is to set flag as zero initially before the additiong checks and then run each check one after the other. If a
#check fails, the matrix is not a magic square. For every check that passes, flag is incremented by 1. Therefore, at the end of
#all the check, if flag == 8, it is added proof that the matrix is a magic square. This step is redundant as the program has been
#written to stop checks as soon as a failed check is encountered as all checks need to be true for a magic square.
if flag==8:
print m
return True
else:
print "**** FLAG ERROR: elementAdder(): Line 84 ***"
print m
def dimensionScaler(n, lst):
#This function converts and returns a 1-D list to a 2-D list based on the order. #Square matrixes only.
#n is the order here and lst is a 1-D list.
i=0
j=0
x=0
#mat = [[]*n for x in xrange(n)]
mat=[]
for i in range (0,n):
mat.append([])
for j in range (0,n):
if (j*n+i<len(lst)):
mat[i].append(lst[i*n+j])
return mat
#mtrx=[]
def matrixGen():
#Brute forcing all possible 4x4 matrices according to the previous method will require 16!*32*16 bits or 1.07e6 GB of memory to be allocated in the RAM (impossible today)./, we
#use an alternative methos to solve this problem.
#
#
#We know that for the sums of the diagonals will be 34 in magic squares of order 4, so we can make some assumtions of the corner element values
#and also the middle 4 elements. That is, the values of the diagonals.
#The strategy here is to assign one set of opposite corner elements as say 1 and 16 and the second as 13 and 4
#The remaining elements can be brute forced for combinations untill 5 magic squares are found.
setPerms=itertools.permutations([2,3,5,6,7,8,9,10,11,12,14,15],12)
final=[0]*16
count=0
#print final
for i in setPerms:
perm=list(i)
setCorners=list(itertools.permutations([1,4,13,16],4))
for j in range(0,len(setCorners)):
final[0]=setCorners[j][0]
final[1]=perm[0]
final[2]=perm[1]
final[3]=setCorners[j][1]
final[4]=perm[2]
final[5]=perm[3]
final[6]=perm[4]
final[7]=perm[5]
final[8]=perm[6]
final[9]=perm[7]
final[10]=perm[8]
final[11]=perm[9]
final[12]=setCorners[j][2]
final[13]=perm[10]
final[14]=perm[11]
final[15]=setCorners[j][3]
if eligCheck(dimensionScaler(4,final))==True:
elementAdder(dimensionScaler(4,final))
matrixGen()