MUST BE IN PYTHON

In the first assignment we worked on an algorithm that produced magic squares of odd order. We avoided generating magic squares of even order because the algorithm for generating them is more complicated.

Here is a very famous magic square that is featured in the painting Melancholia by Albrecht Durer.

16 3 2 13 5 10 11 8 9 6 7 12 4 15 14 1 

In this assignment we will generate all magic squares of order 4 through permutation. The process is straight forward but time consuming. Here are the steps:

Create a 1-D list of integers 1 through 16.

Permute this list of integers.

For each permutation convert the 1-D list into a 2-D list that is 4 x 4.

Check if that 2-D list is a magic square. If it is, then print it out.

The magic constant is given by n * (n² + 1) / 2, where n is the dimension of the magic square. For a 4 x 4 magic square the constant is 34.

In this program there is no user input. You may reuse any code that you have written for the first assignment. Your magic squares must be neatly printed out. Make sure that there is an empty line between each magic square that you print out.

After everything is working correctly, optimize your code so that it does not go through all the permuations. For example, if the first row does not add to the magic constant 34 stop that permutation and go to the next one. If the second row does not add to the magic constant then stop that permutation and go to the next one. And similarly for the sum of the third row.