Solving the 8-Puzzle

There exists a 17-step solution, RRDLLURRDLLUURRDD. Here U, D, L, R means moving the empty space up, down, left, right respectively.

Now, observe that if we color the squares in a chessboard fashion, the empty space will always change color every step, so we need an odd number of steps in order to bring the empty space to bottom-right. Also, each move changes the position of exactly one numbered tile.

We can see the number of moves required to bring a tile to its correct position. This is simply the Manhattan distance of the current position to the actual position. For example, 1 needs one move, and 3 needs three moves. Since each move changes the position of exactly one numbered tile, we can put a lower bound on the number of moves required; that is, the sum of the distances of all tiles to their correct positions. This sum is $1+1+3+1+2+3+3+1 = 15$ . Since we also need an odd number of moves, it remains to prove that 15 steps is impossible (so that the next candidate is 17, which we have shown to satisfy the problem).

Notice that 15 is the exact minimum, so all tiles must take the shortest paths. In particular, this means the 8 must move down, so our first move cannot be to the right. Also, we may not move the 3 to the left, so if our first move is down, we're stuck on the bottom-left corner (the 6 must go straight to the right, and the 3 cannot be moved to the bottom-left corner). So our first move is up, and the second move is naturally right because we shouldn't undo our progress by going down. Also, since the 8 cannot move up either, our third move must be right; left undoes progress while down makes the 8 further from its goal. But now we're stuck at the top-right corner; moving the 7 to the top-right corner makes its journey longer.

So we have proven that 15-step solution cannot exist, and hence the minimum is $\boxed{17}$ steps.

Haskell. Slow (~2.1 seconds for me), but I think it's cuter than stuffing everything into a long long with bitmasks.

import Data.Array
import Data.Maybe
import qualified Data.Set as S

type Pos = (Int, Int)
type Config = Array Pos (Maybe Int)

boardBounds = ((1,1),(3,3))

initConfig :: Config
initConfig = listArray boardBounds [
    Just 4 , Just 1 , Just 2 ,
    Nothing, Just 8 , Just 7 ,
    Just 6 , Just 3 , Just 5 ]

finalConfig :: Config
finalConfig = listArray boardBounds [
    Just 1 , Just 2 , Just 3 ,
    Just 4 , Just 5 , Just 6 ,
    Just 7 , Just 8 , Nothing]

maybeSwap :: Pos -> Pos -> Config -> Maybe Config
maybeSwap p1 p2 cfg = case (cfg ! p1, cfg ! p2) of
    (Just a, Nothing) -> Just $ cfg // [(p1, Nothing), (p2, Just a)]
    (Nothing, Just a) -> Just $ cfg // [(p1, Just a), (p2, Nothing)]
    _ -> Nothing

swaps :: [(Pos, Pos)]
swaps =
    [((r,c),(r,c+1)) | r <- [1..3], c <- [1..2]] ++
    [((r,c),(r+1,c)) | r <- [1..2], c <- [1..3]]

moves :: Config -> [Config]
moves cfg = catMaybes [maybeSwap p1 p2 cfg | (p1, p2) <- swaps]

levels :: Config -> [S.Set Config]
levels cfg = levels' (S.singleton cfg) S.empty
    where levels' cur used = cur : levels' (next S.\\ used) (S.union next used)
        where next = S.fromList (concatMap moves $ S.toList cur) S.\\ used

main = print $ length $ takeWhile (S.notMember finalConfig) $ levels initConfig

i just did reversing the correct position to the given problem and by counting the number of moves to make it to the first image

Hint : Play Reverse ;)