Manhattan Distance + Linear Conflicts scoring function for sliding tile puzzle solver

Question

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& 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 < 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 < b._height; row++) {
        for (auto col = 0; col < 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 < l; j++) {
                if (j == i || b._tiles[j] == 0) {
                    continue;
                }
                if (goalRow[j] == row && b._tiles[i] > b._tiles[j] &&
                goalRow[i] < goalRow[j]) {
                    md += 2;
                }
            }
        }
    }

    return md;
}

Answer 1

Bug: if statement always false

I'm confused about this if statement:

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

and in particular the last condition goalRow[i] < 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 && b._tiles[i] > b._tiles[j] &&
                    goalCol[i] < 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] > b._tiles[j] implies that goalCol[i] > 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 && i > j && goalCol[i] < 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 < l; j++) {
            if (b._tiles[j] == 0) {
                continue;
            }
            if (goalRow[j] == row && goalCol[i] < 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.