Minimum number of moves algorithm in Java

Question

I'm looking to implement the minimum number of moves algorithm for the java game I'm developing but I can't quite figure it out.

Here's an example picture:

There are also some specifications about this:

The solution in the example above is not unique; other solutions would also be valid as long as the "final character layout (or the positioning of the characters in the nodes)" matches a certain condition (I don't think that's very relevant now so won't go into detail). Also, the nodes aren't actually moved, only it's content.

Adjacent elements cannot be swapped (i.e. in the example above, on the starting side's first swap, 'E' couldn't be swapped with neither 'A' or 'B'; B could be swapped with any character but 'E' and so on.)

The same character can be swapped as many times as one wishes. So, for example, 'B', in the starting side of the picture, could be swapped with 'D' in the first move (B and D trade places) and then 'B' could be swapped with, let's say, 'E' (so B and E trade places).

So how exactly should I approach this, in order to get the minimum moves? I don't need a full solution, but some pseudo-code or a couple of hints would be greatly appreciated!

Answer 1

As people have said in comments section, A* or (AStar) is a viable algorithm for this, and a good waypoint.

Here you have a generic AStar implementation in Java so you can start with something. Please, ask if you have any question.

import java.util.*;


public class AStar {


  public static class PriorityList extends LinkedList {

    public void add(Comparable object) {
      for (int i=0; i<size(); i++) {
        if (object.compareTo(get(i)) <= 0) {
          add(i, object);
          return;
        }
      }
      addLast(object);
    }
  }

  protected List constructPath(AStarNode node) {
    LinkedList path = new LinkedList();
    while (node.pathParent != null) {
      path.addFirst(node);
      node = node.pathParent;
    }
    return path;
  }

  public List findPath(AStarNode startNode, AStarNode goalNode) {

    PriorityList openList = new PriorityList();
    LinkedList closedList = new LinkedList();

    startNode.costFromStart = 0;
    startNode.estimatedCostToGoal =
      startNode.getEstimatedCost(goalNode);
    startNode.pathParent = null;
    openList.add(startNode);

    while (!openList.isEmpty()) {
      AStarNode node = (AStarNode)openList.removeFirst();
      if (node == goalNode) {
        // construct the path from start to goal
        return constructPath(goalNode);
      }

      List neighbors = node.getNeighbors();
      for (int i=0; i<neighbors.size(); i++) {
        AStarNode neighborNode =
          (AStarNode)neighbors.get(i);
        boolean isOpen = openList.contains(neighborNode);
        boolean isClosed =
          closedList.contains(neighborNode);
        float costFromStart = node.costFromStart +
          node.getCost(neighborNode);

        // check if the neighbor node has not been
        // traversed or if a shorter path to this
        // neighbor node is found.
        if ((!isOpen && !isClosed) ||
          costFromStart < neighborNode.costFromStart)
        {
          neighborNode.pathParent = node;
          neighborNode.costFromStart = costFromStart;
          neighborNode.estimatedCostToGoal =
            neighborNode.getEstimatedCost(goalNode);
          if (isClosed) {
            closedList.remove(neighborNode);
          }
          if (!isOpen) {
            openList.add(neighborNode);
          }
        }
      }
      closedList.add(node);
    }

    return null;
  }

}