Yeah, that was what I tried with row-Hamming / col-Hamming (namely: treat entire rows / cols as matches or not). I then used the min of the two to address those issues.

Either way, I guess my implementation had a bug -- A* does yield a significant speedup, but adding the 0.25x scaling factor to ensure that the heuristic is admissible loses almost all of those gains.

For some concrete numbers: with the bug that basically reduced to BFS, it ran in about 7s; with the bug fixed but a wildly inadmissible heuristic, it ran in about 0.01s; with the heuristic scaled down by 4x to guarantee its admissibility, it ran in about 5s.

I think scaling it down by 2x would be sufficient: that lower bound would be tight if the problem is one row move and one column move away from the goal state, but potentially all four rows and columns would not match. In that case, it ran in about 1.6s.