n-puzzle

I programmed up an n-puzzle solver that uses A*. It doesn't work. I am sad. I am trying to implement the Manhatten distance with linear conflicts heuristic, but the brute force approach seems to me to be a waste of time. I'm sure that there's a smart way to do this, but I can only think of an O(n^3) {or so} solution. Can you guys tell me to stop being a dumbass and figure it out?

>>5
Even for bruteforcing, you should get O(n^2).