How can we solve the 8 puzzle problem using Branch & Bound approach?

Question

We want to solve the 8-puzzle, or generally, the n-puzzle (where n is m*m - 1 for some integer) problem.  How can we use B&B to solve this problem, and what are the lower/upper bounds?

Answer 1

It seems not a good idea, because different action series may lead to the same state. And for BB to an 8-puzzle problem, there will be many nodes in the tree represent the same states for the chess board. This situation will not happen for a heuristic algorithm because it will not lead to a situation with the same state. In very special circumstances， like do some action "harmful" will lead to a good result, BB may work well. But very special, it can happen only in certain conflict situations.

Answer 2

Solution Space:

Imagine a tree structure where each node represents the arrangement of the n-puzzle tiles. The root node represents the starting arrangement. Each node branches out into child nodes, representing the possible moves (in this case it is sliding a tile). Using this tree structure we explore all possible paths to reach the required arrangement of tiles(solution).

Bounds:

Lower Bound:  we use misplaced tile heuristic which calculates the number of tiles not in their correct goal positions. So we explore paths requiring least number of moves.

Upper Bound:  we use manhattan distance heuristic which calculates the sum of distances of misplaced tiles from their goal positions. This gives us the upper limit on remaining moves.

Estimated Cost will be the sum of the lower and upper bounds. Using this we can prioritize paths with fewer estimated moves to complete the puzzle.

3. Ordering Criteria:

Explore the nodes with lower estimated costs first so we complete puzzle with the minimum number of moves. Prune any node whose estimated cost exceeds the current best solution. This eliminates exploring paths that will require more moves than the best solution so far.

references: Analyzing the A* Search Heuristics with the Solutions of the 8-Puzzle, 
looking-into-k-puzzle-heuristics.