title: Composite heuristic for the 8-puzzle
body: <p>While reading Artificial Intelligence a Modern Approach I came across the concept of deriving a heuristic from the solution cost of a sub-problem of a given problem.</p>
  
  <p>For example, the following puzzles shows a sub problem of the 8-puzzle instance where the goal is to place tiles 1, 2, 3, 4 into their correct positions.</p>
  
  <pre><code>Start State = [ * 2 4 ]    Goal State = [   1 2 ]                      
                [ *   * ]                 [ 3 4 * ]
                [ * 3 1 ]                 [ * * * ]  
  </code></pre>
  
  <p>Then, the author expand this concept by saying that these heuristics derived from the sub-problems can be combined by taking the maximum value.</p>
  
  <pre><code>h(n)= max{ h1(n), . . , hm(n) }
  </code></pre>
  
  <p>Moreover, by using this approach the performance is improved greatly when compared to a simple heuristic like <a href="https://en.wiktionary.org/wiki/Manhattan_distance" rel="nofollow">Manhattan distance</a>.</p>
  
  <p>I have been trying to wrap my head around the composite heuristics and the reasoning behing them. Let's say we have two heuristics derived from the solution cost of the following sub-problems:</p>
  
  <pre><code>h1234(n) = [   1 2 ]     h5678(n) = [   * * ]                    
             [ 3 4 * ]                [ * * 5 ]
             [ * * * ]                [ 6 7 8 ]
  </code></pre>
  
  <p>Will a composite heuristic like:</p>
  
  <pre><code>h1...8(n)= max{ h1234(n), h5678(n) }
  </code></pre>
  
  <ol>
  <li>Really work in finding a solution for the complete 8-puzzle problem?</li>
  </ol>
  
  <p>It seems to me that using a heuristic like <em>h1...8(n)</em> we will end up alternating between heuristics <em>h1234(n)</em> and <em>h5678(n)</em> which in turn might lead to one heuristic messing up the work of the other and never reaching a solution.</p>
  
  <ol start="2">
  <li>Or will the heuristics help each other towards the complete solution?</li>
  </ol>
  
  <p>Honestly, I do no see how this could work...</p>