Got it, let's walk through how to adapt your existing BFS solver for the 8-puzzle to use Depth-First Search (DFS). The key difference between the two algorithms is how they manage the frontier of nodes to explore—and that's where the code changes will happen.

Core Concept: Queue vs. Stack #

• BFS uses a queue (FIFO: First-In, First-Out) to explore all nodes at the current depth before moving to deeper levels. This guarantees the shortest path, but uses more memory.
• DFS uses a stack (LIFO: Last-In, First-Out) to dive as deep as possible along a single path before backtracking. It uses less memory but doesn't guarantee the shortest path (unless you use a depth-limited variant like IDFS).

Modified DFS Code (Based on Your BFS Snippet) #

Here's how to adjust your code to use DFS. I'll keep the structure similar to your original BFS code, with key changes highlighted:

public direction[] Solve(nPuzzle puzzle) {
    // Replace queue with a stack for DFS frontier management
    Stack<PuzzleState> frontier = new Stack<>();
    
    // Add the initial state to the stack (instead of queue)
    frontier.push(puzzle.StartState);
    
    // Track visited states to avoid cycles (critical for both BFS and DFS)
    Set<PuzzleState> visited = new HashSet<>();
    visited.add(puzzle.StartState);
    
    while (!frontier.isEmpty()) {
        // Pop the LAST added node (DFS explores the most recent path first)
        PuzzleState currentState = frontier.pop();
        
        // Check if we've reached the goal state
        if (currentState.isGoalState()) {
            // Reconstruct and return the path (same as BFS—relies on parent pointers)
            return reconstructPath(currentState);
        }
        
        // Generate all valid next states (same logic as your BFS code)
        ArrayList<PuzzleState> newStates = generateNextStates(currentState);
        for (PuzzleState state : newStates) {
            if (!visited.contains(state)) {
                visited.add(state);
                // Push the new state to the stack to explore it next
                frontier.push(state);
                // Don't forget to set parent/direction for path reconstruction
                state.setParent(currentState);
                state.setDirectionTaken(getDirectionFromMove(currentState, state)); // Adjust to your method
            }
        }
    }
    
    // No solution found (shouldn't happen for solvable 8-puzzle instances)
    return null;
}

Key Notes for Your Implementation #

• Cycle Prevention: The visited set is non-negotiable here. Without it, DFS could loop between the same states indefinitely (e.g., moving the blank tile back and forth).
• Path Reconstruction: Just like in BFS, each PuzzleState needs to track its parent state and the direction taken to reach it. This lets you trace back from the goal to the start once you find a solution.
• Depth Limitation (Optional but Recommended): Standard DFS can get stuck exploring very deep, non-optimal paths. To fix this, add a depth limit (this becomes Iterative Deepening DFS, or IDFS, which combines DFS's memory efficiency with BFS's optimal path guarantee):

// Depth-limited DFS (IDFS foundation)
public direction[] SolveWithDepthLimit(nPuzzle puzzle, int maxDepth) {
    Stack<PuzzleState> frontier = new Stack<>();
    puzzle.StartState.setDepth(0);
    frontier.push(puzzle.StartState);
    
    Set<PuzzleState> visited = new HashSet<>();
    visited.add(puzzle.StartState);
    
    while (!frontier.isEmpty()) {
        PuzzleState currentState = frontier.pop();
        
        if (currentState.isGoalState()) {
            return reconstructPath(currentState);
        }
        
        // Stop exploring this path if we've hit the depth limit
        if (currentState.getDepth() >= maxDepth) {
            continue;
        }
        
        ArrayList<PuzzleState> newStates = generateNextStates(currentState);
        for (PuzzleState state : newStates) {
            if (!visited.contains(state)) {
                visited.add(state);
                state.setDepth(currentState.getDepth() + 1);
                state.setParent(currentState);
                frontier.push(state);
            }
        }
    }
    
    // No solution found within the depth limit
    return null;
}

Quick Recap #

1. Swap the queue for a stack to change the exploration order.
2. Keep the visited set to avoid cycles.
3. Add depth limits if you want to guarantee finding the shortest path (IDFS).

内容的提问来源于stack exchange，提问作者Gianni Tripodi