title: How to optimize recursive permutation algorithm for all 4x4 "magic squares"
body: <p>A "magic square" consists of an n x n matrix where the rows, columns, and diagonals all equal a constant. For 4 x 4 magic squares, that constant is 34. I'm attempting to optimize my permutation algorithm, which currently lists all possible 4 x 4 matrices using digits ranging from 1-16, to skip over certain permutations if the current matrix doesn't match the magic square criteria.</p>
  
  <p>I already have the recursive algorithm to permute all combinations. This function takes a length 16 array, which is representative of the square, and prints all possible combinations that fit the "magic" criteria. I'm not sure how to implement a check in the recursive call to optimize it though. For example, I want it so that if the first row of the matrix doesn't sum up to 34, skip that permutation and proceed to the next one (and so on and so forth for the proceeding rows). </p>
  
  <pre><code>def permute(a, lo, hi):
      if(lo == hi) and (isMagic(a)):
          print(a)
      else:
          for i in range(lo, hi):
              # this is where I imagine the exceptions would be made
              a[lo], a[i] = a[i], a[lo]
              permute4(a, lo + 1, hi, count, n)
              a[lo], a[i] = a[i], a[lo]
  </code></pre>
  
  <p>When removing the "isMagic" check, which simply prints all combinations, including those that arent "magic", it takes a painfully long time for the function to print the squares. I ultimately would like to speed this up by excluding unnecessary permutations. How would I implement this check?</p>