Is the algorithm for determining if an $N\times N$ ($15$) puzzle is solvable the same as $M \times N$?

Question

Most of the algorithms I've seen discuss $N\times N$ grids only.

This is the method I'm talking about:

An inversion is when a tile precedes another tile with a lower number on it. The solution state has zero inversions. ... To explain it another way, an inversion is a pair of tiles (a,b) such that a appears before b, but a>b. Count the number of inversions in the grid. ...

The formula says:

1. If the grid width is odd, then the number of inversions in a solvable situation is even.
2. If the grid width is even, and the blank is on an even row counting from the bottom (second-last, fourth-last etc), then the number of inversions in a solvable situation is odd.
3. If the grid width is even, and the blank is on an odd row counting from the bottom (last, third-last, fifth-last etc) then the number of inversions in a solvable situation is even.

There's one article I read that discusses $M\times N$ grids but I'm not a math expert so I'm not really sure if the $N\times N$ algorithm applies to $M\times N$.

Answer 1

Since you're not describing the algorithms you've seen, it we can't say for sure whether they can be applied to non-square puzzles.

In most cases I can't imagine that will be a problem, though -- you can adapt existing algorithms to solve a single row at a time until you have only a square at the end left, and then ignore the rows you have already solved while you solve the final square.

The general theory of sliding puzzles applies just fine to non-square puzzles: The usual checkerboard argument shows that only positions that are even permutations can be solved, and as long as each of the sides is at least 2 tiles long, one can prove that all even permutations can be solved.

Your favorite concrete method may or may not depend on having more space to work with than just two rows, though.

---

After edit: The rule you quote works no matter whether the height and width are equal.

However, it is rather more convolutedly phrased than I would prefer. We can give a rule that doesn't look like it's full of special cases by:

1. When you count inversions, pretend the empty space is a tile with a higher number than any others.
2. Count the distance between the empty space and the lower-right cell, following the grid lines. For example in a 15-puzzle with the empty space at the far upper left this distance would be $6$ because you need to go $3$ right, $3$ down.
3. The configuration is solvable if and only if the number of inversions plus the empty-space distance from the lower right is an even number.