Solution algorithm for Unblock Me game for c#?

Question

Algorithms

Good time of the day!
Tell me the solution algorithm for the Unblock Me game, if there are any code examples for C #, I will be grateful!

Answer 1

The algorithm, in short, is this: breadth-first traversal along the state graph. Imagine that each position of all the cars on the field corresponds to a vertex in some graph. Each possible move is a directed edge in the graph. The initial specified state is the initial vertex. Any vertex where the desired car is right next to the exit from the field is considered to be the final one. To find the shortest path, you need to run a breadth-first walk in this graph.
Now the details. The graph itself does not need to be stored. You just need to be able to somehow store that a certain state of the field has already been viewed (if you also need to find the solution moves themselves, then you also need to store for each state preceding it in the path). Some kind of hash map or map will do here.
To bypass in width, you will also need a queue. It remains only to learn from a given state to get everything where you can go from it in one move. For this, it is convenient to consider as a state not a rectangular matrix - but a set of numbers: for each machine where in its row / column it is located. According to this state, it is very easy to restore the matrix itself. Then we simply sort through each typewriter and all its possible shifts. We look in the matrix that all the cells of the new position are not occupied by anything else. If all is well, here is the new state.
In practice, this will work quite quickly. If there are a lot of machines, then there will be few admissible states. If there are few cars, then the answer will be found quite quickly, which means that not many states will be viewed. The problem is only if there is no solution, and there are not too many cars. Then this algorithm will work slowly. But, the upper estimate is N^K states, where N is the size of the field, and K is the number of cars. For small fields (N=6) will solve everything instantly.