We are given two matrices $R^{N \times N}$, each containing unique integers from $0$ to $N^2 - 1$ (except $0$, it does not need to be unique). The $0$ in the matrices will be called $blank$. The task is to determine a sequence of moves (not necessarily optimal) that transforms the configuration of the first matrix into that of the second. Moves consist of sliding a (orthogonally adjacent) tile into the $blank$ square.
This problem is a variant of the Sliding Puzzle, which typically involves a single $blank$ tile. It is known that a configuration is solvable iff the invariant (parity invariant) is the same in both matrices: the parity of the permutation of the numbered tiles combined with the parity of the blank’s Manhattan distance from its goal position.
For the one-$blank$ case, a constructive algorithm exists that can transform one state into another using at most $O(N^3)$ moves. Briefly: solve the board layer-by-layer (peel off outer rows/columns), place each tile into its goal using local cyclic move patterns that shift the tile one step at a time without disturbing already-fixed tiles, and repeat until only a $2\times2$ region remains. Each tile requires $O(N)$ local steps and there are $O(N^2)$ tiles, giving the $O(N^3)$ bound.
When the puzzle contains two or more $blanks$ the situation changes significantly: it has been proven that the state graph with two $blanks$ is connected, so any configuration can be reached from any other (see “Books, Hallways, and Social Butterflies: A Note on Sliding Block Puzzles”). The remaining challenge is to produce a practical (preferably $O(N^3)$), constructive algorithm that outputs an explicit sequence of moves in the multi-$blank$ setting. Can someone lend a helpful hand?
