I'm convinced there is only one way to solve this: Write a program to unroll the constrained state transition diagram into an unconditional state transition diagram and find the shortest path. The unrolled version would still be pretty small so you can just iterate over it.
In other words, BFS over the state space of the puzzle, skipping previously-visited states?
You don't actually gain anything by unrolling everything ahead of time; it'd actually be worse because you'd store all the memory and wouldn't stop when you get to the solution. And you can't really factor the state space into subproblems.
Anyway, for this puzzle BFS would work, but classical planning in general gets astronomically exponential fast. It's a neglected field, not yet thawed from the last AI winter.
That's an interesting statement. Because I actually don't think it's true.
(Well obviously it's not and you were joking, but let's say you were not, for the sake of argument.)
Humans do this differently from machines. We look for strategies and have smarts to on-the-fly develop and refine heuristics that rapidly allow us to intuitively do branch-and-bound like algorithms and in the end solve this even though we brute force very litte, if at all.
That's why it took so long for machines to surpass us at chess or similar. It's a different approach. That's what makes machines better at certain things and humans at others. And there is a lot to be gained by trying to have machines also try human-like approaches to problems (strategy-developing rather than brute force).
This can be easily solved by a class of algorithms called "search algorithms". Most famous ones are "Breadth-first search" and "Depth-first search". They have many variations like "Depth limited depth-first search" and "Iterative deepening depth-first search". If you include heuristics, then you have other variations like "A" and "Iterative deepening A". These are pretty well known and relatively easy to implement.
Hacker news change the star into italics. The variations are called 'A*' and 'iterative deepening A*' (Need a backslach prior to the star to show it properly)
You'd have to do that for VxVxV, because there are three different objects (although there's some symmetry). Solving a puzzle is often described as path finding.
The vast majority of states is not reachable, so you can roll out the full tree from the starting state and it's going to be very small. Even the super-naive approach of unrolling the full state space is only 6^7 which is a big waste because connections are very sparse but even that's not big, it just wouldn't scale to larger problems.
