Have you ever actually tried to do one of these puzzles? That strategy doesn't work. Ex 15-puzzle:

[ 1] [ 2] [ 3] [15]
[ x] [ x] [ ] [ 4]
[ x] [ x] [ x] [ x]
[ x] [ x] [ x] [ x]

There is no way to move 4 into place without moving 3.

The algorithm is only worked when the puzzle is solvable, I'm not sure if your example is a solvable one or not... and yes I have actually coded this algorithm few years ago, I don't remember the details but that's the main idea. Perhaps, we can move 3 (or even 1, 2) in some immediate steps, but after the steps are done, we should have 1, 2, 3, 4 in line.

1) Your post distinctly said "while keeping the previous tiles at the correct position." If you need to move a previous tile in an intermediary step, then that isn't the same algorithm you originally said would work.

2) An N-puzzle is solvable if the parity is even. A puzzle can be change in parity from odd to even or vice versa by swapping the values of two adjacent tiles. Since the value of 8 positions are left unspecified then that puzzle configuration can map to any number of solvable puzzles.

1) Your post distinctly said "while keeping the previous tiles at the correct position." If you need to move a previous tile in an intermediary step, then that isn't the same algorithm you originally said would work.

2) An N-puzzle is solvable if the parity is even. A puzzle can be change in parity from odd to even or vice versa by swapping the values of two adjacent tiles. Since the value of 8 positions are left unspecified then that puzzle configuration can map to any number of solvable puzzles.

Yes, my mistake. Let me change it to "some previous tiles can be moved in intermediary steps". So basically there's a function moveTile(i), i = 1..N*N, with the precondition that 1, 2, i-1 is already in place, and the postcondition should be 1, 2, ..., i in place - any tiles can be moved in an intermediary step, though. I can't remember the details on how to implement this function, perhaps there're few cases, depending on the current position of i and the correct position of i.