A magic square is a matrix all of whose row sums, column sums and the sums of its two diagonals are the same. (One diagonal of a matrix goes from the top left to the bottom right, the other diagonal goes from top right to bottom left.) Each number in the magic square can only be used once. More information on magic squares and the distinction between "normal" and "non-normal" magic squares can be found at this linke:
Also of interest, this link outlines some of the history, many different flavors of magic squares and considerations for writing an algorithm to create them (a possible future enhancement to this notebook):
David Darling Magic Square research
In a "normal magic square", a $n \times n$ magic matrix is constructed by $(1, 2, 3 ... n^2)$. For example, here is a $3\times 3$ normal magic array: $$\left[ \begin{array}{cc} 8 & 1 & 6 \\ 3 & 5 & 7 \\ 4 & 9 & 2 \end{array} \right]$$
The code which follows was designed to test if a matrix is a magic square. To do this, it performs the following checks predominantly using Python numpy functions:
In [2]:
### write your code here
import numpy as np
def isMagic(mtrx1):
'''isMagic(mtrx1) -> \n\nexpects a matrix. Returns a tuple: (isMagic=T/F, string="Reason Failed" | "Magic Square").'''
if len(mtrx1.shape)!=2 or mtrx1.shape[0] != mtrx1.shape[1]:
# shape of square = 2 and both dimensions are equal (test)
return (False, "Not a Square, so not a Magic Square")
if mtrx1.max() != mtrx1.shape[0]**2 or mtrx1.min() != 1:
# automatically fails (1,2,3 ... n**2) test because largest or smallest does not match the sequence
return (False, "Failed: [1,2 ... sqr(n)] test (max/min incorrect).")
else:
# met first condition of (1,2,3 ... n**2), now we check whole matrix
# note: that this test is really for "normal magic squares", as per wikipedia, "non-normal" magic squares can
# violate this rule: https://en.wikipedia.org/wiki/Magic_square
mtrx1b = np.sort(mtrx1.reshape(1, mtrx1.shape[0]**2))
mtrx2 = np.mat(np.arange(1, mtrx1.shape[0]**2+1))
if np.equal(mtrx1b, mtrx2).all():
mtrx1b = np.zeros([1, mtrx1.shape[0]]) + (np.sum(mtrx1) // mtrx1.shape[0]) # comparison array for sums
if not np.equal(mtrx1b, np.sum(mtrx1, 0)).all(): # test sum of columns
return (False, "Failed: sum of columns test")
elif not np.equal(mtrx1b, np.sum(mtrx1, 1)).all(): # test sum of rows
return (False, "Failed: sum of rows test")
elif not np.equal(mtrx1b, sum(np.diag(mtrx1))).all(): # test main diagonal
return (False, "Failed: sum of diagonals test (main diagonal)")
elif not np.equal(mtrx1b, sum(np.diag(np.fliplr(mtrx1)))).all(): # test other diagonal
return (False, "Failed: sum of diagonals test (2nd diagonal)")
else:
return (True, "Magic Square")
else:
# if test sorts matrix values and compares them to the 1 ...n**2 sequence ... upon failure we land here:
return (False, "Failed: [1,2 ... sqr(n)] test (1+ values do not match)")
In [3]:
# a few test objects for our function (in addition to the ones provided):
noMagicSq = np.mat(np.arange(1,10)).reshape(3,3)
magicSq = np.mat([[8,1,6],[3,5,7],[4,9,2]])
oddmtrx = np.mat([[1,2],[3,4], [5,6]])
notNsqSeq = np.mat([[11,1,6],[3,5,7],[4,9,2]])
notNsqSeq2 = np.mat([[0,1,6],[3,5,7],[4,9,2]])
notNsqSeq3 = np.mat([[8,1,7],[3,5,7],[4,9,2]])
print(isMagic(oddmtrx))
print(isMagic(notNsqSeq))
print(isMagic(notNsqSeq2))
print(isMagic(notNsqSeq3))
print(isMagic(noMagicSq))
print(isMagic(magicSq))
Here are some tests:
In [4]:
test1 = np.array([[0, 1],
[1, 0]])
isMagic(test1) # False
Out[4]:
In [5]:
test2 = np.array([[8, 1, 6],
[3, 5, 7],
[4, 9, 2]])
isMagic(test2) # True
Out[5]:
In [6]:
test3 = np.array([[16, 2, 3, 13],
[5, 11, 10, 8],
[9, 7, 6, 12],
[4, 14, 15, 1]])
isMagic(test3) # True
Out[6]:
In [7]:
test4 = np.array([[17, 24, 1, 8, 15],
[23, 5, 7, 14, 16],
[4, 6, 13, 20, 22],
[10, 12, 19, 21, 3],
[11, 18, 25, 2, 9]])
isMagic(test4) # True
Out[7]:
In [8]:
test5 = np.array([[35, 1, 6, 26, 19, 24],
[3, 32, 7, 21, 23, 25],
[31, 9, 2, 22, 27, 20],
[8, 28, 33, 17, 10,15],
[30, 5, 34, 12, 14,16],
[4, 36, 29, 13, 18,11]])
isMagic(test5) # True
Out[8]:
In [9]:
# additional testing (just to see some of the other code in action)
test5b = np.array([[35, 1, 6, 26, 19, 24],
[3, 32, 7, 21, 23, 25],
[31, 9, 2, 22, 27, 20],
[8, 28, 33, 2, 10,15],
[30, 5, 34, 12, 14,16],
[4, 36, 29, 13, 18,11]])
isMagic(test5b) # False (changed one value to dupe of another)
Out[9]:
In [10]:
test5c = np.array([[35, 1, 6, 26, 19, 24],
[3, 32, 7, 21, 23, 25],
[31, 9, 2, 22, 27, 20],
[8, 28, 12, 17, 10,15],
[30, 5, 34, 33, 14,16],
[4, 36, 29, 13, 18,11]])
isMagic(test5c) # False (switched two diagonal values)
Out[10]:
In [11]:
test5d = np.array([[35, 1, 6, 26, 19, 24],
[3, 32, 7, 21, 23, 25],
[31, 9, 2, 22, 27, 15],
[8, 28, 33, 17, 10,20],
[30, 5, 34, 12, 14,16],
[4, 36, 29, 13, 18,11]])
isMagic(test5d) # False (flipped values from two different rows)
Out[11]:
In [13]:
test6 = np.array([[16, 3, 2, 13],
[5, 10, 11, 8],
[4, 15, 14, 1],
[9, 6, 7, 12]])
isMagic(test6) # False: "semimagic square": only rows and column = the magic number
Out[13]:
More resources on magic squares:
In [ ]: