# Minimum number of moves algorithm in Java

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: 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!

• What constitutes a correct "solution"? You say the "final character layout (or the positioning of the characters in the nodes) matches a certain condition"... but you'll have to explain that. No one can give you a solution to a problem that isn't explained. – Foggzie Dec 22 '15 at 22:23
• It sounds like you might want to use a search algorithm like A* - it's not only useful for path finding. – Adam Dec 23 '15 at 0:30
• @Adam Hey, thanks for the tip, i'm going to take a look at it! – Francisco Dec 23 '15 at 0:56
• Yeah; for A*, instead of having the nodes be "locations" they are "game states" where the "destination" is a "win state". And the "arcs" are not "paths" but "moves". You have to compute all the moves and game states that can be achieved from the current state and find the least "moves" to get to the "win" state. – Vaillancourt Dec 23 '15 at 7:29

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

import java.util.*;

public class AStar {

public static class PriorityList extends LinkedList {

for (int i=0; i<size(); i++) {
if (object.compareTo(get(i)) <= 0) {
return;
}
}
}
}

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

public List findPath(AStarNode startNode, AStarNode goalNode) {

PriorityList openList = new PriorityList();

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

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) {
}
}
}