# Does the last row of a N x N sliding puzzle need to be solved?

If I successfully arrange all the blocks of every row of a sliding puzzle except the last row in proper order, will the n-th row be automatically resolved? (Assuming that the puzzle is solvable in the 1st place, and the hole is in the last row).

Not necessarily!

In a 2x2 pattern, if you solve a row then you automatically solved the other too. Same for a 3x3 pattern, assuming that the hole is positioned in the last row, because swapping two blocks is an impossible move (it has been proven, only half configurations are solvable, as stated here). In a 4x4 or bigger pattern, there are valid permutations for the last row, so you can't assure that solving the other rows automatically completes the game.

• I forgot to mention in my question that the hole is in the last row. I assumed that the last row would resolve by itself, the reasoning being that if I solve the 1st row, the puzzle would essentially become (n - 1) x n puzzle, which I can solve without ever having to re-order the 1st row. So if I solved the (n-1) th row, the puzzle would become 1xN, but since that isn't solvable, so.. – curious Jul 10 '15 at 10:46
• As someone that plays a game that has a lot of sliding puzzles, I can guarantee that the last row can be out of order when all other rows are complete. The general strategy is to solve all but the last two rows, then solve the last two rows at the same time from left to right. – Deacon Jul 10 '15 at 12:26
• @curious This depends on what you mean by solving the first row. If you solve the rows in a manner that does not preclude solving the rest of the puzzle then the last row will be solved "automatically". However if solving the first row means getting the sequence right for the first row, then this answers shows that there you can end in configurations where the final row is not in correct sequence. For this reason solution algorithms for the 15 puzzle does not go row by row, or at least not row by row until there is only one row left. – Taemyr Jul 10 '15 at 12:28

As mentioned before. If you've done these kind of puzzles before a common strategy is to solve row by row but the final two rows together just because it won't always work out.

Consider this bottom right segment of any puzzle larger than 2x4 in correct order:

1234
567


you can now do this to make the top row still correct but the bottom not.

1234
567

234
1567

2 34
1567

2534
1 67

2534
167

253
1674

253
1674

1253
674

1253
67 4

12 3
6754

1234
675


No it's not automatically resolved (for N>3)

because

We can minimize the Problem to "can we mix all solved NxN sliding puzzle (with N>3) that way that the last row with the hole is not sorted!" and there is a way.

To make things easy: We shift the buttom row so that the hole is in the last column
We only look at the bottom 4x2 (the rest stays sorted):
a = (n-3,n-1)
b = (n-2, n-1)
c = (n-1, n-1)
d = (n, n-1)
e = (n-3,n)
f = (n-2, n)
g = (n-1,n)
_ = hole(n,n)

Lets begin sliding:

abcd
efg_

abcd
_efg

_bcd
aefg

b_cd
aefg

becd
a_fg

becd
afg_

bec_
afgd

_bec
afgd

abec
_fgd

abec
fg_d

ab_c
fged

abc_
fged

abcd
fge_

And that's it.
Now the n-1 row is sorted again and the n row is not. So in conclusion there is a way to slide the puzzle that n-1 rows are sorted but the last is not. Perhaps even fewer moves are necessary but that wasn't the question.

edited: I needed more than 23 Minutes to write this??? I didn't saw Ivo's solution...