What is a good approach to demonstrate solvability of this type of puzzle without use of brute-force?

Question

I chanced upon this puzzle in this question on the Anime & Manga site, and, like the OP, tried to solve it without any success. Here is a representation of the puzzle: the blocks may only be moved forward or backward along their shorter sides, and we must get the block labelled with a black X to the exit.

I then tried to prove that the puzzle wasn't solvable using the following framework:

1. Argue that at some time the block we must move to the exit will be exactly one space away from it, and that moreover, we will only need to move the other blocks at most once to remove any obstructions to the exit.

2. Use proof by contradiction and the layout of the puzzle to argue that none of the possible configurations for which the block is at the space I specify are actually at most a single move away from making the exit.

I ran into a brick wall with this: there were four possible cases to consider (based on the placement of (IV)), and while I could easily apply (2) to two of them, I didn't have nearly as much success with the other two.

I was wondering if I simply should have chosen a different position to work from, but it occurred to me that unless I had extremely lucky intuition, it would be difficult to make arguments from anything other than the penultimate placement of the blocks. (Naturally, it also occurred to me that I could probably just check for solvability by writing a computer program to check for all possible configurations of this puzzle, but my programming skills are iffy, and I found such a "brute-force" method too uninsightful.) Moreover, my proof-strategy would only have worked if the puzzle were indeed unsolvable.

I don't suppose that there is necessarily a very intuitive generalization of finding the solvability of such puzzles, but at the very least: what would be a good strategy for me to use to determine whether or not this puzzle can be solved, without too much brute-force?

Answer 1

Is this an instance of Rush Hour? $\:$ If yes, then:

There is probably no general way to check solvability of this
type of puzzle in much less time than brute-force would take.

There is a general way to solve solvable puzzles of this type (and discover
non-solvability when that's the case) with an amount of space corresponding to some
constant times the amount of space needed to represent a configuration of the puzzle.
(Note: $\:$ The algorithm I just linked to is highly impractical.)


There is a randomized algorithm with a time-space tradeoff for this type of puzzle
that provably has a high probability of recognizing solvable puzzles as solvable and
will never incorrectly claim that an unsolvable puzzle is solvable, although there
will be a small probability of it failing to recognize a solvable puzzle as solvable.
I don't know whether or not that can be turned into solving solvable puzzles of this type.

There is a less efficient
time-space tradeoff for (deterministically) checking solvability of this type of puzzle
and solving solvable puzzles of this type (even though the paper I just linked to
doesn't make the claim that corresponds to "solving solvable puzzles").
At one extreme of the tradeoff, this paper's algorithm reduces to brute-force.

Answer 2

This survey lists this kind of puzzle as PSPACE-complete, a class which is at least as hard as the class of NP-complete problems (and perhaps even harder, but we don't know that).

It means that there even a small increase in the puzzle size might cause a tremendous increase in difficulty, such that even computers won't be able to solve it "reasonable" time. I'm unaware of any methods of demonstrating solvability of unsolvability in the general case that don't resemble a brute-force approach. Perhaps such methods exists for subclasses of such problems (e.g. when the starting configuration is constructed with some known method), but that is the best we can hope for unless we break the rest of the world.

Anyway, this instance is solvable, hints below. (By the way, isn't asking on math.SE some way to check if the puzzle is solvable?)

Move 8 left:

6u 57r 1d 2l 36u 4r 3d 2r 1u 5l 10u 5r 1d 2l 39u 8l

Move 6 down:

39d 2r 1u 5l 10d 5r 1d 2l 3u 4l 3d 2r 1u 57l 6d

Move 10 up:

57r 1d 2l 3u 4r 3d 2r 1u 5l 10u

I hope this helps $\ddot\smile$