Manhattan Distance + Linear Conflicts scoring function for sliding tile puzzle solver I have written yet another n-puzzle solver.  I used the A* algorithm to search with the Manhattan Distance heuristic.  It worked very well for the 9-puzzle (3x3) but was unusable for most instances of the 15-puzzle (4x4.)  In fact I would exhaust all RAM before I got anywhere near the result.

So I switched to IDA* and the Manhattan Distance + Linear Conflicts heuristic.  Now I can solve most puzzles reasonably fast.  (e.g. one with a 50-move solution takes about 8s.)  However more difficult puzzles (the worst case for the 15-puzzle is 80 moves.) are still much too slow.  Profiling my code with Callgrind I saw that by far the most expensive part of the algorithm is calculating the heuristic which has to be done once for every node.  Any win here would be a tremendous improvement to the solvers overall speed.  So I present to you the current state of my code.  Can it be improved?

One thing you need to know to understand this function is that Board is a struct
with three members.  _height and _width which are the dimensions of the board.  and _tiles which is one-dimensional C-style array of uint8_t which represents the state of the board with each cell containing a number from 1 to (_height * _width - 1) or 0 to represent the blank square.

int ManhattanLinearConflict(Board&amp; b) {
    int md = 0;

    // Pre-compute goals.
    uint8_t goalRow[b._height * b._width];
    uint8_t goalCol[b._height * b._width];

    for (uint8_t i = 0, length = b._height * b._width; i &lt; length; i++) {
        if (b._tiles[i] == 0) {
            continue;
        }
        goalRow[i] = (b._tiles[i] - 1) / b._height;
        goalCol[i] = (b._tiles[i] - 1) % b._width;
    }

    for (auto row = 0; row &lt; b._height; row++) {
        for (auto col = 0; col &lt; b._width; col++) {
            // This part is just Manhattan distance.
            auto i = row * b._width + col;
            if (b._tiles[i] == 0) {
                continue;
            }
            md += abs(long(row - goalRow[i]));
            md += abs(long(col - goalCol[i]));

            // Two tiles I and J are in a linear conflict if I and J are
            // in the same line, the goal positions of I and J are both in
            // that line, I is to the right of J and goal position of I is
            // to the left of the goal position of J.
            if (goalRow[i] != row) {
                continue;
            }
            for (uint8_t j = row * b._width, l = j + b._width; j &lt; l; j++) {
                if (j == i || b._tiles[j] == 0) {
                    continue;
                }
                if (goalRow[j] == row &amp;&amp; b._tiles[i] &gt; b._tiles[j] &amp;&amp;
                goalRow[i] &lt; goalRow[j]) {
                    md += 2;
                }
            }
        }
    }

    return md;
}
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.