Rotating vectors for solving riddles

[Tathe1999]

Hi,
I asked a teacher of mine for a task which I could code at home as I'm awfully fast out of ideas what to code (please note that it is no homework or project, it's just for fun) and he gave me some kind of riddle and asked me to write a program which solves any given riddle with as few steps as possible. The riddle is a given 2-dimensional field which has an opening on one side. In the field there are a varying number of rods. The task is to rotate the field, which makes the rods follow gravity until one rod can exit the field through the hole.

Example:
(Can't add as text because the format won't persist...)
https://gyazo.com/935a922792b4d4ab014b4e7291c9649f

Reading such a field from a file already works and is no problem, but now I wonder how I could
a) achieve the turning of the field (I read it into a vector<vector<char> > ) (figured that one out)
b) find out which way I'd have to turn the field to solve it with the least amount of steps.

I do not ask for code, just the general idea of how to accomplish these two tasks, as I'm (hopefully) able to code it myself.

Thank you in advance,
Tathe.

[Tathe1999]

After some fiddling I found out how to rotate the vectors, but I still have no idea how I could find the solution with the fewest rotations. Could anybody please point me in the right direction?

Thank you,
Tathe.

[mbozzi]

You could make the formatting of your example diagram persist if you use code tags.

The hint is dynamic programming, with the caveat that you'll never want to undo your last moves. Each rotation you make will form four links in the problem graph (at least one of which -- the always-cyclic one -- you need to cull).

Start by finding the minimum number of moves. You'll end up with something from which you can work backwards.
If you don't see it, try drawing out the problem graph.

This pseudocode will get you the number of moves. Don't read it if you don't want the help. ;)

function min_rotations(field F, last_rotation_direction L) {
  /* Base case of the recurrence */
  if (problem_solved (i.e., a 1 has fallen out)) return 0;

  /* A cycle will never result in an optimal solution.  
     Terminate the recursion immediately. */
  if (F has been seen before) return infinity;

  /* Save what the field looks like for later, in-case we see it again. */
  record_field_state(F);

  /* Evaluate any other available branch */
  return 1 + min(min_rotations(face_exit_up(F), up),
                 min_rotations(face_exit_down(F), down),
                 min_rotations(face_exit_left(F), left),
                 min_rotations(face_exit_right(F), right));
}

face_exit_XXXX is intended to rotate the field and "settle" the pieces down. If a one falls out, than the recurrence terminates.
It isn't too hard to keep track of precisely which rotations got you to the optimal solution.

Note that if you find any cycle you can simply terminate the recursion immediately (returning infinity) for that branch; a cycle will never result in an optimal solution.

[Tathe1999]

Thank you very much for your reply, the explanation really helped me.