4
\$\begingroup\$

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;
}
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Ah yes, thankyou, good catch! It was indeed supposed to be the column not the row. Because of the mistake my heuristic was no better than plain Manhattan Distance and must have frequently been underestimating thus causing many additional nodes to be searched. With the fix, the time to solve a 40-move puzzle goes down from 0.105 seconds to 0.083 seconds -- a substantial speed up! \$\endgroup\$ – Jaldhar Oct 19 '16 at 5:18
  • \$\begingroup\$ The 50-move puzzle has gone down from 8s to ~6s. Harder puzzles (80 moves is the theoretical maximum) still take several minutes or more so there is room for improvement if anyone has more ideas. \$\endgroup\$ – Jaldhar Oct 19 '16 at 5:22
  • \$\begingroup\$ @Jaldhar See my latest edit. \$\endgroup\$ – JS1 Oct 19 '16 at 6:01
  • \$\begingroup\$ Sadly I was mistaken and you were right. The performance gains I was seeing were probably due to caching effects or something like that. Now I test by creating some random boards instead of using the same one each time. \$\endgroup\$ – Jaldhar Oct 21 '16 at 3:32
  • \$\begingroup\$ Oops pressed enter too soon. With your second suggestion I think I am finally seeing proper results for linear conflicts. While the solver is very fast in most cases, very difficult boards still take too long but I don't think I can get too much more performance out of this heuristic and am going to look at something else such as a pattern database instead. \$\endgroup\$ – Jaldhar Oct 21 '16 at 3:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.