I am working on solvability problem. I realize that not every permutation is possible to solve. Even more I found algorithm for checking if permutation is possible to solve.
Algorithm: http://mathworld.wolfram.com/15Puzzle.html
Algorithm with proof: https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html
I want to know if this algorithm will work for rectangle version of puzzles and if not how to check it. Anyone can help?
Finally I found an analysis for rectangle puzzle sliding game. Everything is explained here: http://kevingong.com/Math/SixteenPuzzle.html
Generalizations of the 15-puzzle on arbitrary graphs were studied by Richard M. Wilson (citation below). By Theorem 1, since rectangular grid graphs are bipartite, the inversions criterion applies.
Richard M Wilson, Graph puzzles, homotopy, and the alternating group, Journal of Combinatorial Theory, Series B, Volume 16, Issue 1, February 1974, Pages 86-96, ISSN 0095-8956, http://dx.doi.org/10.1016/0095-8956(74)90098-7. (//www.sciencedirect.com/science/article/pii/0095895674900987)