A* 15-puzzle return path

[1stuntctmm]

I have to write a program that returns the optimal path from the input 4x4 matrix to the solution of the 15-puzzle using A* algorithm (in C/C++).
Now, I managed to write a program that finds a solution to the 15-puzzle (although it's really slow for more complicated inputs, is that normal?), but I'm not sure how to return the optimal path.
I'm using a structure which consists of a 4x4 matrix and the cost of that matrix.
http://en.wikipedia.org/wiki/A*_search_algorithm
If you look at the pseudocode on that link, my openset and closedset are actually two lists of (the structure I defined)'s... Maybe I should have used something else instead of lists, but now it's too late and I don't have the time to code everything from the beginning. Anyway, I don't know how to remember the parent of/path to every node in my path. In the above link, the pseudocode suggests using a map of navigated nodes, but using maps in my situation would be messy because you have to define operators like <= because maps only work with something that has (weak?) ordering... And even if I define something like that (I actually tried that), the whole thing still doesn't work for me: If A is a member of the structure I defined, and I write something like map[A] = B and try to print out map[A], I won't get B.
Another thing I tried was adding a pointer to parent as a part of my structure, but for some reason that doesn't work either.
So, what do you suggest, how should I remember paths?
Sorry for not providing any snippets of code, ask me if you need some parts of it in order to respond to my question properly and I'll post them.
Thanks.

[weaknessforcats]

Use a stack. Push as you go and pop as you return.

[1stuntctmm]

Yeah, but WHEN should I push something on my optimal stack? I can't know that some node belongs to the optimal path until I reach the end (and that's when I have to recursively reconstruct the optimal path).

Anyway, I returned to the idea of having pointer_to_parent as a part of my structure and then reconstructing the path by printing last node, last node's parent, last node's parent's parent... The problem is: My program will print the last node's parent correctly, but last node's parent's parent and everything after that will be the same as last node's parent. :/

Again, sorry for not providing any code, but there's a lot of code and I have no idea in which part of it the problem lies.

[1stuntctmm]

Looks like I had some dangling pointers. =) Problem solved...