What can be the efficient approach to solve the 8 puzzle problem?

Answer 1

Donut's got it! IDDFS will do the trick, considering the relatively limited search space of this puzzle. It would be efficient hence respond to the OP's question. It would find the optimal solution, but not necessarily in optimal complexity.

Implementing IDDFS would be the more complicated part of this problem, I just want to suggest an simple approach to managing the board, the games rules etc. This in particular addresses a way to obtain initial states for the puzzle which are solvable. An hinted in the notes of the question, not all random assignemts of 9 tites (considering the empty slot a special tile), will yield a solvable puzzle. It is a matter of mathematical parity... So, here's a suggestions to model the game:

Make the list of all 3x3 permutation matrices which represent valid "moves" of the game. Such list is a subset of 3x3s w/ all zeros and two ones. Each matrix gets an ID which will be quite convenient to keep track of the moves, in the IDDFS search tree. An alternative to matrices, is to have two-tuples of the tile position numbers to swap, this may lead to faster implementation.

Such matrices can be used to create the initial puzzle state, starting with the "win" state, and running a arbitrary number of permutations selected at random. In addition to ensuring that the initial state is solvable this approach also provides a indicative number of moves with which a given puzzle can be solved.

Now let's just implement the IDDFS algo and [joke]return the assignement for an A+[/joke]...

Answer 2

You can use the heuristic that is based on the positions of the numbers, that is the higher the overall sum of all the distances of each letter from its goal state is, the higher the heuristic value. Then you can implement A* search which can be proved to be the optimal search in terms of time and space complexity (provided the heuristic is monotonic and admissible.) http://en.wikipedia.org/wiki/A*_search_algorithm

Answer 3

This is an example of the classical shortest path algorithm. You can read more about shortest path here and here.

In short, think of all possible states of the puzzle as of vertices in some graph. With each move you change states - so, each valid move represents an edge of the graph. Since moves don't have any cost, you may think of the cost of each move being 1. The following c++-like pseudo-code will work for this problem:

{
int[][] field = new int[3][3];
//  fill the input here
map<string, int> path;
queue<string> q;
put(field, 0); // we can get to the starting position in 0 turns
while (!q.empty()) {
    string v = q.poll();
    int[][] take = decode(v); 
    int time = path.get(v);
    if (isFinalPosition(take)) {
        return time;
    }
    for each valid move from take to int[][] newPosition {
        put(newPosition, time + 1);
    }
}
// no path
return -1;
}

void isFinalPosition(int[][] q) {
    return encode(q) == "123456780"; // 0 represents empty space
}
void put(int[][] position, int time) {
    string s = encode(newPosition);
    if (!path.contains(s)) {
        path.put(s, time);
    }
}

string encode(int[][] field) {
    string s = "";
    for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) s += field[i][j];
    return s;
}

int[][] decode(string s) {
    int[][] ans = new int[3][3];
    for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) field[i][j] = s[i * 3 + j];
    return ans;
}

Answer 4

See this link for my parallel iterative deepening search for a solution to the 15-puzzle, which is the 4x4 big-brother of the 8-puzzle.