Solving the 8-Puzzle Problem: Implementing Classic AI Search Algorithms with BFS and DFS

This article introduces the open-source 8-puzzle problem Python implementation project by GabrelGarcia on GitHub, based on the textbook Artificial Intelligence: A Modern Approach. It uses two blind search algorithms—BFS and DFS—to solve the classic 8-puzzle problem, covering core AI search concepts such as state space modeling and solvability detection. It is an ideal reference material for learning AI search algorithms.

The 8-puzzle problem is a classic search problem in the AI field. It involves rearranging tiles in a 3×3 grid by moving the blank cell (represented as 0) to reach the target state. This project is maintained by GabrelGarcia and published on GitHub (link: https://github.com/GabrelGarcia/Puzzle8-Problem-Python) on May 26, 2026. Its theoretical foundation is the textbook Artificial Intelligence: A Modern Approach by Peter Norvig and Stuart Russell.

State Representation: Use a list/tuple to represent the 3×3 layout (e.g., initial state [1,2,3,4,5,6,0,7,8]); Successor Function: Generate new states by moving the blank cell (considering boundaries); Frontier Management: BFS uses a FIFO queue (collections.deque) to ensure optimality, while DFS uses a LIFO stack for deep search; Solvability Check: Calculate the number of inversions (solvable if even, unsolvable if odd) to terminate invalid searches early; Goal Test: Check if the current state equals the target state.

The code is implemented in pure Python, relying on standard libraries, with modular design to separate logic; it supports command-line interaction (e.g., python puzzle.py 1 2 3 4 5 6 0 7 8 to specify the initial state); performance optimizations: use deque for efficient queues, set to store visited states (O(1) lookup), and tuple as state representation. Execution steps: Install Python3 → Clone the code → Pass the initial state via command line → Output the solution path.

This project is an excellent teaching tool combining theory and practice, helping to understand state space search, algorithm differences (BFS is optimal vs. DFS is not), and the roles of the frontier and visited set. Although the 8-puzzle problem is simple, the core concepts involved are the foundation of complex AI systems, and the project demonstrates how to translate classic AI theory into runnable code.

Learning Suggestions: 1. Understand the problem rules and state representation; 2. Read the code to see how concepts are implemented; 3. Modify the initial state to observe the search process; 4. Compare the performance of BFS and DFS; 5. Try implementing A* search. Extension Directions: Add heuristic functions (e.g., Manhattan distance) to implement A* search, support the 15-puzzle, visualize the search process, and analyze algorithm performance metrics.