Forming a Magic Square
Problem:-
We define a magic square to be an n * n matrix of distinct positive integers from 1 to n2 to where the sum of any row, column, or diagonal of length n is always equal to the same number: the magic constant. You will be given a 3*3 matrix of integers in the inclusive range [1,9]. We can convert any digit a to any other digit in the range [1,9] at cost of |a-b| . Given , convert it into a magic square at minimal cost. Print this cost on a new line.
Note: The resulting magic square must contain distinct integers in the inclusive range [1,9].
Solution:-
This problem was quite trick and had it own sub-challenges at each level. The first problem or question was ,what is magic square? I would recommend to go through some YouTube video. There are many video showing various pen-paper method to solve or verify the magic square.
In this problem I took help to find various combination of magic square for a 3*3 matrix, which made the task little-bit easy. We could easily generate the combination based on the dimension of matrix but the wasn’t the end goal and I didn’t wanted to make the code complicated by included the generation of combination of magic square in it.
def formingMagicSquare(s):
s1 = [j for sub in s for j in sub] #Step-1 #flating the 2-d list to 1-d list
magic=[[8, 1, 6, 3, 5, 7, 4, 9, 2], #genearted this by another program
[6, 1, 8, 7, 5, 3, 2, 9, 4],
[4, 9, 2, 3, 5, 7, 8, 1, 6],
[2, 9, 4, 7, 5, 3, 6, 1, 8],
[8, 3, 4, 1, 5, 9, 6, 7, 2],
[4, 3, 8, 9, 5, 1, 2, 7, 6],
[6, 7, 2, 1, 5, 9, 8, 3, 4],
[2, 7, 6, 9, 5, 1, 4, 3, 8]]
#minimumcost=1000
minimum_cost=sys.maxsize Step-2#setting up a max value can be any max val
for mag in magic: Step-3#iterate through the magic list
diff=0
for i,j in zip(s1,mag): #Step-4#we zip s1,mag to perform sub operation to calculate the diff
diff+=abs(i-j)
print("difference in iteration-",diff)
print("Max-",minimum_cost)
minimumcost=min(minimum_cost,diff) #Step-5 #keep on updating minimum_cost value as in 1st iteration it will be max value
return minimum_costLets move towards the code ,In step-1 I am trying to flatten/convert “s” list/matrix from 2D to 1D by using list comprehension method. There are many ways to do the flattening but I find it handy to use list comprehension for it. We can also use in-built function from numpy library.I have also declared all the magic square combinations in a list name “magic”.
In Step-3,I am declaring a variable “minimum_cost” which will hold a maximum value in python i. e 9223372036854775807.we can use any max value but i need to make this code robust and generic version of itself which can be implemented to any n*n matrix just by replacing the combination in “magic” variables.
In step-3,we iterate the magic list and also declared a variable “diff” and initialize it to 0.In step-4,we iterate through the zipped version of “S1" and “mag”(list present mag variable in that specific iteration).Inside this iteration we will substract s1 with the specific list mag variable holds in that specific iteration and we will update “diff” variable.
In Step-5,we will find the minimum among diff and minimum_cost in that specific iteration and update it in minimum_cost variable.
The catch for the problem is present in this for loop,we compare the given matrix with the magic combination which is present the variable “magic”.The difference will tell us how minimum values in give matrix we need to change to match the magic combination.
for i,j in zip(s1,mag):
diff+=abs(i-j)
minimumcost=min(minimum_cost,diff)Conclusion:-
My part-time hobby is quotes collection and this quotes suits perfect for this difficult problem “Problems may not bother you as long as you believe in yourself that you will find a solution”. Keep on learning and hustling….(cheers:-PN)
