title: How to programmatically solve the 15 (moving numbers) puzzle?
body: <p>all of you have probably seen the moving number/picture puzzle. The one where you have numbers from 1 to 15 in a 4x4 grid, and are trying to get them from random starting position to</p>
  
  <pre><code>1   2  3  4
  5   6  7  8
  9  10 11 12
  13 14 15 
  </code></pre>
  
  <p>My girlfriend or some of my non-programmer friends can solve this with some mumbo-jumbo magic, that they can't explain to me. I can't solve the puzzle. </p>
  
  <p>The most promising approach I have found out is to solve first row, then I'd get</p>
  
  <pre><code>1   2  3  4
  X   X  X  X
  X   X  X  X
  X   X  X 
  </code></pre>
  
  <p>then first column without touching solved cells</p>
  
  <pre><code>1   2  3  4
  5   X  X  X
  9   X  X  X
  13  X  X 
  </code></pre>
  
  <p>then second row to</p>
  
  <pre><code>1   2  3  4
  5   6  7  8
  9   X  X  X
  13  X  X 
  </code></pre>
  
  <p>then second column</p>
  
  <pre><code>1   2  3  4
  5   6  7  8
  9   10  X  X
  13  14  X 
  </code></pre>
  
  <p>the problem is, that remaining X (random) tiles are sometimes in unsolvable position and this is where my solution fails. But I feel as if I'm on the right path.</p>
  
  <p>My program does the solving of specified row/column by trying to get number X to specified position without messing up the correct cells, if possible. But it can't do the last 3 tiles on 2x2 grid. What am I missing?</p>