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).
$\begingroup$
$\endgroup$
0
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
3
The answer is
Not necessarily!
Additional info:
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.
-
$\begingroup$ 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.. $\endgroup$– curiousJul 10, 2015 at 10:46
-
$\begingroup$ 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. $\endgroup$– DeaconJul 10, 2015 at 12:26
-
$\begingroup$ @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. $\endgroup$– TaemyrJul 10, 2015 at 12:28
$\begingroup$
$\endgroup$
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
answered Jul 10, 2015 at 12:39
$\begingroup$
$\endgroup$
The Answer is
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...
