1

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

Improve this question
1
  • You should consider taking into account equations satisfied by magic squares, to reduce complexity : use backtracking. Commented Jan 26, 2013 at 18:23

3 Answers 3

Reset to default
1

Just pull the placed numbers out of the permutation set. Then insert them into their proper position in the generated permutations.

For your example you'd take out 1, 16, 4, 13. Permute on (2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15), for each permutation, insert 1, 16, 4, 13 where you have pre-selected to place them.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Thanks but the problem is I can't store all the permutations of a set {1-16}. Because that requires 16!*16*32 bits of memory. :S
No, it wouldn't be 16!, we're taking out 4 numbers so it's 12!, which is still big. So don't deal with them all at once. itertools.permutations returns an iterator. Don't create a list, iterate over the permutations with for. Half a billion loops will not be quick, but not impossible either.
Guys should I post my finished work here for others to see or is that considered bad here?
So instead of having corner elements set static, I cycle them around... see code
1

Recently I have made the research for most-perfect magic squares 4x4.

You don't need to generate 16! permutations, most of them are not useful for your goal. You can use only 4! permutations of { 1, 2, 4, 8 }. Here is how:

A B AT BT 
0 1 1 0
1 0 0 1
0 1 1 0
1 0 0 1
 
0 0 1 1
1 1 0 0
0 0 1 1
1 1 0 0
 
0 1 0 1
1 0 1 0
1 0 1 0
0 1 0 1
 
0 1 0 1
0 1 0 1
1 0 1 0
1 0 1 0
  1. Use matrices { A, B, AT, BT } multiplied by values { 1, 2, 4, 8 } in any order;
  2. Add them (A*v0 + B*v1 + AT*v2 + BT*v3);
  3. Increase all values of the matrix by lowest value you want (sum +1).

If you will use all permutations of { 1, 2, 4, 8 } you will get all most-perfect magic squares 4x4 (in range [L..L+15]) with the lowest value in top left corner. Examples (3/24):

v A v[0] B v[1] AT v[2] BT v[3] S S+1 
1
2
4
8
 
_ 1 1 
1 1
 1 1 
1 1
 
_ 2 2
2 2 
 2 2
2 2 
_ 4 4
4 4 
4 4 
 4 4
 
_ 8 8
 8 8
8 8 
8 8 
 0 13 3 14
 7 10 4 9
12 1 15 2
11 6 8 5
 
 1 14 4 15
 8 11 5 10
13 2 16 3
12 7 9 6
 
1
4
2
8
 
_ 1 1 
1 1
 1 1 
1 1
 
_ 4 4
4 4 
 4 4
4 4 
_ 2 2
2 2 
2 2 
 2 2
 
_ 8 8
 8 8
8 8 
8 8 
 0 11 5 14
 7 12 2 9
10 1 15 4
13 6 8 3
 
 1 12 6 15
 8 13 3 10
11 2 16 5
14 7 9 4
 
2
4
1
8
 
_ 2 2 
2 2
 2 2 
2 2
 
_ 4 4
4 4 
 4 4
4 4 
_ 1 1
1 1 
1 1 
 1 1
 
_ 8 8
 8 8
8 8 
8 8 
 0 11 6 13
 7 12 1 10
 9 2 15 4
14 5 8 3
 
 1 12 7 14
 8 13 2 11
10 3 16 5
15 6 9 4

To get magic squares with the lowest value in certain location you can shift matrices { A, B, AT, BT } to that location. Examples:

v A# v[0] B# v[1] AT# v[2] BT# v[3] S# S#+1 
2
4
8
1
 
2 2
 2 2 
2 _ 2
 2 2 
4 4 
 4 4
4 4 _ 
 4 4
 
8 8 
 8 8
 8 _ 8
8 8 
1 1 
1 1 
 1 _ 1
 1 1
 
15 4 9 2
 1 10 7 12
 6 13 0 11
 8 3 14 5
 
16 5 10 3
 2 11 8 13
 7 14 1 12
 9 4 15 6
 
4
8
1
2
 
4 4
 4 4 
4 _ 4
 4 4 
8 8 
 8 8
8 8 _ 
 8 8
 
1 1 
 1 1
 1 _ 1
1 1 
2 2 
2 2 
 2 _ 2
 2 2
 
15 8 3 4
 2 5 14 9
12 11 0 7
 1 6 13 10
 
16 9 4 5
 3 6 15 10
13 12 1 8
 2 7 14 11
 
8
2
4
1
 
8 8
 8 8 
8 _ 8
 8 8 
2 2 
 2 2
2 2 _ 
 2 2
 
4 4 
 4 4
 4 _ 4
4 4 
1 1 
1 1 
 1 _ 1
 1 1
 
15 2 5 8
 1 12 11 6
10 7 0 13
 4 9 14 3
 
16 3 6 9
 2 13 12 7
11 8 1 14
 5 10 15 4

Python 3:

def B_f(x, y): return x >> 1 & 1 ^ y & 1 def A_f(x, y): return B_f(x + 1, y) def AT_f(x, y): return A_f(y, x) def BT_f(x, y): return B_f(y, x) def magic_square_4x4_f(v, l, x0, y0, w = 4, h = 4): return [ [ + A_f(x - x0, y - y0) * v[0] + B_f(x - x0, y - y0) * v[1] + AT_f(x - x0, y - y0) * v[2] + BT_f(x - x0, y - y0) * v[3] + l for x in range(w) ] for y in range(h) ] from itertools import permutations def print_all_4x4(x0, y0): for v in permutations({ 1, 2, 4, 8 }): print(magic_square_4x4_f(v, +1, x0, y0)) # print_all_4x4(0, 0) # 24/384 for y in range(4): for x in range(4): print_all_4x4(x, y) # 24 * 4 * 4 = 384 magic squares

This code generates all magic squares 4x4 efficiently. Here is couple first and last lines of the output:

[[1, 15, 10, 8], [12, 6, 3, 13], [7, 9, 16, 2], [14, 4, 5, 11]] [[1, 15, 10, 8], [14, 4, 5, 11], [7, 9, 16, 2], [12, 6, 3, 13]] [[1, 14, 11, 8], [12, 7, 2, 13], [6, 9, 16, 3], [15, 4, 5, 10]] [[1, 14, 11, 8], [15, 4, 5, 10], [6, 9, 16, 3], [12, 7, 2, 13]] ... [[4, 9, 7, 14], [5, 16, 2, 11], [10, 3, 13, 8], [15, 6, 12, 1]] [[10, 3, 13, 8], [5, 16, 2, 11], [4, 9, 7, 14], [15, 6, 12, 1]] [[4, 9, 6, 15], [5, 16, 3, 10], [11, 2, 13, 8], [14, 7, 12, 1]] [[11, 2, 13, 8], [5, 16, 3, 10], [4, 9, 6, 15], [14, 7, 12, 1]]
Improve this answer

Comments

0 
#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()
Improve this answer

1 Comment

Is there a better way of doing the last loop?

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.