title: Puzzle Programming - Impossible to optimize?
body: <p>I've been writing programs to solve various number puzzles, but I'm constantly designing unreasonably complex search algorithms that I can't optimize.</p>
  
  <p>For example, in one puzzle, you are given a 3x3 grid of numbers 1 through 9 below:</p>
  
  <pre><code>123
  456
  789
  </code></pre>
  
  <p>You're allowed to cycle the numbers in any row or column in any direction. Below is an example of shifting the <strong>top row</strong> of numbers to the <strong>right</strong>. The numbers will loop if they are at the edge of the grid.</p>
  
  <pre><code>123 -&gt; 312
  456    456
  789    789
  </code></pre>
  
  <p>You must move the numbers in this manner until you create a <strong>magic square</strong> in which the sum of the numbers in each column, row, and diagonal is 15.</p>
  
  <p>I've written a DFS brute-force algorithm to test all possible sequences of moves, though the number of available moves at each turn increases exponentially (approx. 12 ^ [current turn]), rendering it useless.</p>
  
  <p>It seems a BFS would be optimal to find the correct moves, but that would require me to store hundreds if not thousands of <strong>copies</strong> of the grid in order to backtrack!</p>
  
  <hr>
  
  <p>I run into these kinds of problems all the time. Both BFS and DFS algorithms use too much memory and time, respectively. I need help optimizing algorithms like these so they run faster and efficiently. Maybe recognizing patterns and relations of the numbers or giving the algorithm logic to work towards a goal would help? (I don't know what that would entail).</p>
  
  <p><strong>EDIT:</strong></p>
  
  <p>My fixed algorithm works like a charm. Learning how to number my permutations was essential. Thank you all!</p>