Manhattan Distance + Linear Conflicts scoring function for sliding tile puzzle solver
Bug: if statement always false

I'm confused about this if statement:


            if (goalRow[j] == row &amp;&amp; b._tiles[i] &gt; b._tiles[j] &amp;&amp;
                    goalRow[i] &lt; goalRow[j]) {
                md += 2;
            }



and in particular the last condition goalRow[i] &lt; goalRow[j].  When the last condition is checked, we already know that goalRow[i] == row (from above) and goalRow[j] == row (from the first condition), so that last condition will always be false.  I think that perhaps you meant to use goalCol instead:

            if (goalRow[j] == row &amp;&amp; b._tiles[i] &gt; b._tiles[j] &amp;&amp;
                    goalCol[i] &lt; goalCol[j]) {
                md += 2;
            }


Bug 2: if statement still always false

After looking over the corrected if statement another time, I found that it is still always false.  The problem is that b._tiles[i] &gt; b._tiles[j] implies that goalCol[i] &gt; goalCol[j] because goalCol[x] is derived in a linear fashion from b._tiles[x].  I believe that you really meant this:

            if (goalRow[j] == row &amp;&amp; i &gt; j &amp;&amp; goalCol[i] &lt; goalCol[j]) {
                md += 2;
            }


But the simpler way to do this is to just make your loop run from the start of the row to i, like this:

        for (uint8_t j = row * b._width, l = j + col; j &lt; l; j++) {
            if (b._tiles[j] == 0) {
                continue;
            }
            if (goalRow[j] == row &amp;&amp; goalCol[i] &lt; goalCol[j]) {
                md += 2;
            }
        }


I'm surprised that your program seemed to run faster after only changing goalRow to goalCol.  You may want to print something out if it ever reaches the md += 2 line to make sure you are ever getting there.  I ran a little test program to generate random boards and it never hit that statement until I fixed it with both fixes.