Must be in PYTHON

Assignment: Print out 4x4 magic squares from permutations

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 you will prompt the user to enter n the number of magic squares of order 4 that he wants. The number n must be between 1 and 10 inclusive. Prompt the user repeatedly so that the number is in the given range. Your program will generate n magic squares of order 4 through permutation. The process is straight forward but time consuming. Here are the steps:

Prompt the user to enter the number of magic squares.

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.

Stop when you have the required number of magic squares.

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 only one user input - the number of magic squares. 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.

Enter number of magic squares (1 - 10): 2 1 2 15 16 12 14 3 5 13 7 10 4 8 11 6 9 1 2 15 16 13 14 3 4 12 7 10 5 8 11 6 9 

For grading purposes, your prompt should end in a colon character then a space character (': '). Do not place any colons in any other places in any prompt or printed output. Matching the provided sample prompt will expedite grading.

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.