title: python idastar vs astar solving 8 puzzle
body: <p>I started to refresh my ai knowledge so i implemented some pathfind algorithms to solve 8-Puzzle.</p>
  
  <ul>
  <li><a href="http://en.wikipedia.org/wiki/A%2a_search_algorithm" rel="nofollow">A*</a> </li>
  <li><a href="http://en.wikipedia.org/wiki/IDA%2a" rel="nofollow">IDA*</a> </li>
  <li><a href="http://en.wikipedia.org/wiki/Breadth-first_search" rel="nofollow">BFS</a>  </li>
  <li><a href="http://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search" rel="nofollow">IDFS</a> </li>
  </ul>
  
  <p>I was wondering why my implementation of IDA* has a longer path. It should be optimal like A*.</p>
  
  <pre><code>% python puzzle8.py -a idastar -d hard
  IDASTAR - RESULT in 161.6099:
  1 | 2 | 3
  4 | 5 | 6
  7 | 8 | N
  
  cost: 0 total_cost: 121
  ...
  nodes 28
  
  % python puzzle8.py -a astar -d hard
  Max nodes 665 loops 1085
  ASTAR - RESULT in 0.3148:
  1 | 2 | 3
  4 | 5 | 6
  7 | 8 | N
  
  cost: 0 total_cost: 115
  ...
  nodes 24
  </code></pre>
  
  <p>Code is on gist <a href="https://gist.github.com/1629405" rel="nofollow">https://gist.github.com/1629405</a></p>
  
  <p><em><strong>Update:</em></strong></p>
  
  <p>Code is now pointing to a <strong>working</strong> version.</p>
  
  <pre><code>% python puzzle8.py -a idastar -d hard
  IDASTAR - RESULT in 234.4490: 
  
  1 | 2 | 3
  4 | 5 | 6
  7 | 8 | N
  ...
  nodes 24
  </code></pre>
  
  <p>But i'm still wondering why IDA* takes so much longer under <strong>python</strong> than A*.</p>
  
  <p><em><strong>Update 2:</em></strong></p>
  
  <p>Code is changed prints now visited nodes. </p>
  
  <p>IDASTAR creates <strong>4184368</strong> ASTAR <strong>1748</strong> nodes.</p>