Given a text file containing the layout of the map of the Sokoban, a solution as optimal as possible has to be obtained with the developed Algorithm.
Initial considerations of the algorithm
The algorithm input is the map itself, and the output is the path that the robot must follow in order to solve it.
The algorithm evolves through consecutive states, defined by the XY position of the robot and the diamonds. On each step, the robot position is moved to a new valid one. Valid movements are:
An adjacent goal or walkable position (Without a diamond on top).
An adjacent position with a diamond, only if the position next to the box is walkable.
NOTE: A new kind of symbol may be defined, for the positions containing both a goal and a diamond.
Another possible solution may be creating a boolean flag for every position, which is set to True when there is a diamond on it. This functionality can be extended, creating a common struct for every position, containing a boolean for the existence of a diamond, another for the existence of a goal, and a last one representing whether it is walkable or not.
Another alternative, more memory-consuming, would be to add to each position information, also the information regarding the adjacent positions, so the software for checking the possibilities is probably easier to develop.
The algorithm may try different random solutions until a valid path is obtained.
If at a given state, every diamond coordinates share the same coordinates as the goals, the path is considered valid.
If at a given state, one of the diamonds is not at a goal position and it cannot be moved as well (There is a wall in 2 consecutive sides of the diamond), the path is considered non-valid.
Given a text file containing the layout of the map of the Sokoban, a solution as optimal as possible has to be obtained with the developed Algorithm.
Initial considerations of the algorithm