What is the hardest possible initial state for 15-puzzle?

I have a written an n-puzzle or 'sliding tile puzzle solver and I'm trying to optimize it. I have read that the worst case initial state for a 15-puzzle (i.e. 4x4) requires 80 moves to solve where a move is defined as sliding one tile into the blank space. What does that initial state look like? I thought it was this:

 1  5  9 13
 2  6 10 14
 3  7 11 15
 4  8 12 --

But my program solves it in 46 moves. Which means:

1. I'm a genius. My heuristic function quickly dismissed this probability. :-)

2. I'm counting moves wrong. Could be, but the count is correct for other test cases.

3. This is not in fact the hardest initial state. Which seems to be the most likely alternative to me.

Oh I also came accross a suggestion that this is one needs an 80 move solution:

-- 12  9 13
15 11 10 14
 3  7  5  6
 4  8  2  1

That's better as it takes 65 moves. That's still not 80 though.