Jump to content
  • Advertisement
Sign in to follow this  
devO6

Minimum number of moves algorithm in Java

This topic is 1005 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello there, 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 o the puzzle mechanic:  https://gyazo.com/86fb7262b06cf92e48f0a3be5cf39b1f
 
There are some specifications about this:
 
  •  There isn't a single solution; any solution will be valid as long as the final layout of the numbers in the nodes matches the condition described in the picture ( i.e. the two examples in the picture are valid solutions). Also, the nodes aren't actually moved, only the numbers inside them are swapped.

 

  •  Adjacent elements cannot be swapped (i.e. in the example above, on the example start, during the first swap / move, '12' couldn't be swapped with neither '15' or '13' or '7', as these three are connected to '12';  '10' could be swapped with any number but '7' and so on.)
 
  • The same number can be swapped as many times as one wishes. So, for example, '10', in the starting example of the picture, could be swapped with '12' in the first move ('10' and '12' trade places), and then '12' could be swapped with, let's say, '15' (so '12' and '15' trade places).
 
So how exactly should I approach this, in order to get the minimum moves to complete a puzzle? As there are various possible solutions, how could i check every single one and pick the one wish requires the least number of moves (swaps) to complete? I've seen that algorithms such as BFS and A* seem to be suitable for this kind of problem, but i'm not sure how to actually implement them in java code. unsure.png  
 
I don't need a full solution, but some pseudo-code or a couple of hints would be greatly appreciated!biggrin.png
Thanks in advance!
 
PS: If the explanation of the game isn't too clear please say so, i'll try to make it clearer!
 
Edited by devO6

Share this post


Link to post
Share on other sites
Advertisement
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. Edited by dmatter

Share this post


Link to post
Share on other sites

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! biggrin.png

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!