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.
(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).