Lufia II: Puzzle - What kind of knowledge helps to create this kind of puzzle?

Question

In the super nintendo game "Lufia II", game developers included multiple little block puzzles throughout the game. However, one in particular is considered a standout:

This is a kind of sliding puzzle similar to the "15 puzzle" (https://en.wikipedia.org/wiki/15_puzzle). Here, your goal is to bring the biggest block (the one with the treasures) all the way to the lower middle of the space (so your character can access them).

What I was wondering was not the solution itself, but more: how does one create a problem like this? I mean, it doesn't seem trivial at first glance if there is or not a solution to some particular configuration (specially one with uneven shapes). Is there some kind of mathematical area that is suited to analyse if, given some set of shapes, initial configuration and goal, a sliding block puzzle has a solution?

Or maybe even going a step further: is there some analytical way that could help one construct these kind of problems with different "difficulties" (in some well-defined way)?

==== Edit: after posting the question, i found out that this is not an original puzzle - this example is called Klotski (https://en.wikipedia.org/wiki/Klotski). Nevertheless, i guess the question still stands.

Answer 1

The fields involved

There is another answer here that links to this paper which refers to these as "sliding-block puzzles". I am not sure that term is widespread (it may have no widespread term).

For certain, this seems to be well in the domain of computational game theory in particular a subset of combinatorial game theory (although, typically combinatorial game theory studies two player games, it is not required. See the Wikipedia entry for more information.)

It seems the paper "Solving sliding-block puzzles" uses searching heuristics extensively like IDA* search and A* search along with other experiments.

Also, mentioned in the paper "Solving sliding-block puzzles" Rubik's cubes amongst other puzzles are related. And Rubik's cubes, for instance, have interesting connections with group theory. I am not certain if group theory is really being used here, but I believe it is worth mentioning.

Coming up with games

One idea to come up with a game is to establish an initial configuration and then also define a computer procedure that gives a list of valid moves one can make at any given point in time with the current configuration. One can randomly walk through the game tree (well more precisely, puzzle tree). Observe that at any point you reach a valid configuration, and you can approximate the difficulty of getting from the initial configuration to the final position by how long the walk taken was. I should note however, this is certainly, by no means, a perfect difficulty approximation, since you could for instance slide a block from one configuration to another, then back again to the same configuration. Certainly, there are a lot of ways around this (such as keeping a table to prevent visiting previously visited configurations).

This idea is mentioned in this MIT AI lecture as a means of generating different calculus problems of vary degrees of difficulty.