I want to write a program in java to solve the "unblock me" game for a given state (assume that an initial state of the blocks and the board is given as input), my goal is to give the minimum number of moves that are needed to unblock the red block using A* algorithm.
I was thinking to design a good heuristic for this problem and I came up with manhattan distance witch I think is a good one, but I do not know if there can be better ones. Another problem that I have is that I do not know how to find the possible next state of a given state by coding. I hope that I could get good ideas with your help in this post!
Here is a link to the game if you are not familiar :
This particular puzzle is hard for people but not usually hard for computers. So, if you haven't implemented something like this before instead of A*, I'd recommend using a breadth-first search or a depth first search.
BFS: The data structures are relatively easy for a breadth-first search - you can just use a double-ended queue where you remove from the front and add to the back. You may want to check for duplicates, which requires something like a hash table to avoid generating the same state many times.
DFS: For a depth-first search you would use depth-first iterative deepening. That is, you'd limit the DFS to take at most 1 move, then at most 2 moves, etc, until you find the solution. This still guarantees the optimal solution. The only thing you have to do in a DFS is avoid generating moves back to your parent, as this will make the search much less efficient.
Generating moves: To generate moves you consider each piece in the puzzle and the four directions it could possibly move. (up/down/right/left) If the cells next to the piece are all blank, then it can move in that direction. A move is usually defined in a data structure as a piece plus a direction. Typically you can either write a function that returns a list of legal moves, and then you can apply them during the search. If you know the last move, then you can avoid applying the opposite move easily (since it will be the same piece but the opposite direction).
Heuristic: If you want to go with A*, Manhattan distance per piece would work well. If you want something better than that, you can solve the puzzle with 2-3 of the pieces from the puzzle removed and use the solution distance for that simpler puzzle as a heuristic for the full puzzle. But, as I said above, these puzzles are typically so simple that strong heuristics are not needed to solve them.