15-Puzzle Solver using Branch & Bound
Initial State
Solvable: ✅ Yes
Uses A* with Manhattan distance heuristic
Target State
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
15-Puzzle using Branch & Bound
The 15-puzzle is a classic sliding puzzle that uses branch and bound with A* algorithm to find the optimal solution.
Theory & Concepts
Definition:
Branch and bound with A* algorithm explores the state space systematically, using a heuristic function to guide the search towards the goal state while maintaining optimality.
Key Points:
- Uses Manhattan distance as heuristic function
- Explores states in order of f(n) = g(n) + h(n)
- Guarantees optimal solution if heuristic is admissible
- Pruning reduces the search space significantly
Applications:
- Puzzle solving games
- Path planning in robotics
- AI game playing algorithms
- Optimization problems with constraints
University Guidelines
Exam Weightage
15-20 marks MarksSyllabus Coverage:
- Branch and bound technique
- A* algorithm and heuristics
- State space search
- Admissible heuristics
Common Questions:
- Explain branch and bound for 15-puzzle
- What is Manhattan distance heuristic?
- How does A* guarantee optimal solution?
- Compare branch and bound with other search methods
Exam Tips:
Understand Manhattan distance calculation
Draw state space tree with f, g, h values
Explain pruning conditions clearly
Practice with small puzzle instances
Algorithm Details
O(b^d) where b is branching factor and d is depth
Time Complexity
O(b^d) for storing the frontier
Space Complexity
Algorithm Steps:
- 1Initialize priority queue with initial state
- 2Calculate f(n) = g(n) + h(n) for each state
- 3Select state with minimum f(n) value
- 4Generate all possible moves from current state
- 5Add new states to queue if not visited
- 6Repeat until goal state is reached or queue is empty
Test Your Understanding
Key Concepts to Remember:
- Manhattan distance is an admissible heuristic for 15-puzzle
- A* algorithm guarantees optimal solution with admissible heuristics
- Branch and bound prunes suboptimal paths early
- State space can be very large (16! possible states)
- f(n) = g(n) + h(n) guides the search strategy