I'm not sure if A* is applicable here, unless you can think up some permissible heuristic for it. BFS on the other hand is a viable option.

The approach to writing a BFS solver is always pretty much the same basic idea...

Start with your data-modelling - Build something that can represent the state of the puzzle at a single point in time. Be sure to implement the equals and hashCode methods because we'll want to use dynamic programming techniques to ensure we don't get stuck testing out the same puzzle states that we've already tried before.

class PuzzleState {
    public boolean equals(Object o) { }
    public int hashCode() { }
}

Next write an 'expand' function. Such a function takes a single state object (from above) and returns the set of state objects that are reachable from the provided state. These are basically the "next moves" that could be made.

Set<PuzzleState> generateNextMoves(PuzzleState state);

Also write a function that can validate a given PuzzleState to check to see if it is a completed solution:

boolean isSolved(PuzzleState state);

Next up, put together the basic BFS algo. Use a queue as an 'open list' of states that you need to explore. Write a loop that polls the queue, works out the next moves, checks them for being solved and (if no solution found) offers them onto the queue. Keep going till you find a solution or have explored all options:

Queue<PuzzleState> queue = new ArrayDeque<>();

while (!queue.isEmpty()) {
    // pop the next available state off the queue that we will 'expand'
    PuzzleState currentState = queue.remove();

    // work out the reachable states
    Set<PuzzleState> nextStates = generateNextMoves( currentState );

    // check for solutions, but add them to the queue for further exploration otherwise
    for (PuzzleState s : nextStates) {
        if (isSolved(s)) { return SOLVED; }
        queue.add(s);
    }
}

// if we exhaust the queue then we've explored all moves without finding a solution.
return NO_SOLUTION_FOUND;

Then we augment that with dynamic programming optimisation to ensure that we don't explore states if we have already encountered them before. This is where our equals and hashCode come in handy for a contains() check against a HashSet of already-encountered states:

Set<PuzzleState> encountered = new HashSet<>();
Queue<PuzzleState> queue = new ArrayDeque<>();

while (!queue.isEmpty()) {
    // pop the next available state off the queue that we will 'expand'
    PuzzleState currentState = queue.remove();

    // work out the reachable states
    Set<PuzzleState> nextStates = generateNextMoves( currentState );

    // check for solutions, but add them to the queue for further exploration otherwise
    for (PuzzleState s : nextStates) {
        if (encountered.contains(s)) { continue; } // this arrangement has been added to the queue already, so skip
        if (isSolved(s)) { return SOLVED; }
        queue.add(s);
        encountered.add(s);
    }
}

// if we exhaust the queue then we've explored all moves without finding a solution.
return NO_SOLUTION_FOUND;

Finally, we need to seed the search using the starting arrangement of the puzzle. Of course there's a possibility that the puzzle is already solved to start with, so we must check for that too:

PuzzleState initialState = getInitialStateSomehow();

if (isSolved(initialState)) { return SOLVED; }

queue.add(initialState);
encountered.add(initialState);

Hope that helps, good luck with it.

@dmatter Thank you so much! That's a very clear and helpful explanation, i'm going to try it out right away. Thanks!