natmaster is suggesting a Depth-First Search. Looking at the brief description of the problem, I'd go for a Breadth First approach, wioth a recursive fn:
Solve Routine:
==============
LET v be a set (ArrayList, Hashtable, what-have-you);
Add the starting board configuration to v;
RETURN the result of doit(v, 0);

doit Routine:
=============
Parameters:
edge: a set (ArrayList, Hashtable, what-have-you) of the current possible position(s);
n: the number of moves done so far;

LET nextEdge be an empty set;
FOREACH boardConfiguration in edge:
  IF the boardConfiguration is the goal
    RETURN n;
  LET children be the set of board configuration that may be created from boardConfiguration
  by applying all the possible moves;
  ADD to nextEdge all the element of children;
LET nn be n+1;
RETURN doit(nextEdge, nn);

HTH,
Olorin