汉诺塔中途求解Python算法可行性及代码实现问询

Hey Sarah, great question—this is such a clever extension of the classic Towers of Hanoi problem, and totally doable for your class project! The key here is moving beyond the standard recursive approach (which runs to completion in one go) to an explicit stateful solution that tracks progress, so you can pause and resume without resetting the puzzle.

Core Idea: Explicit Call Stack Simulation #

The standard recursive Towers of Hanoi uses an implicit call stack to track subproblems (e.g., "move n-1 disks from A to B, then move the nth disk to C, then move n-1 from B to C"). To make this resumable, we need to make that stack explicit and track the progress of each subproblem. Each entry in our stack will represent a subproblem and which step it's currently in:

1. Step 0: Haven't started moving the n-1 disks to the auxiliary peg yet
2. Step 1: Ready to move the largest disk of this subproblem to the target peg
3. Step 2: Finished moving the largest disk, need to move the n-1 disks from auxiliary to target

Implementation Example (Python) #

Here's a concrete implementation using a class to manage the state stack, with methods to get the next move, save progress, and resume from a saved state:

class ResumableHanoi:
    def __init__(self, num_disks=None, saved_state=None):
        if saved_state is not None:
            # Resume from a previously saved state
            self.stack = saved_state
        else:
            # Initialize a new puzzle with num_disks
            # Stack entries: (n, source_peg, target_peg, auxiliary_peg, current_step)
            self.stack = [(num_disks, 'A', 'C', 'B', 0)]

    def get_next_move(self):
        while self.stack:
            n, source, target, auxiliary, step = self.stack[-1]
            
            if n == 0:
                # No disks to move in this subproblem—pop it from the stack
                self.stack.pop()
                continue

            if step == 0:
                # Step 0: First, we need to move n-1 disks from source to auxiliary
                # Update the current stack entry to mark we're moving to step 1
                self.stack[-1] = (n, source, target, auxiliary, 1)
                # Push the new subproblem onto the stack
                self.stack.append((n-1, source, auxiliary, target, 0))
            elif step == 1:
                # Step 1: Move the largest disk from source to target (this is a concrete move!)
                # Update the current stack entry to mark we're moving to step 2
                self.stack[-1] = (n, source, target, auxiliary, 2)
                return (source, target)
            elif step == 2:
                # Step 2: Now move n-1 disks from auxiliary to target
                # Pop the completed subproblem from the stack
                self.stack.pop()
                # Push the final subproblem onto the stack
                self.stack.append((n-1, auxiliary, target, source, 0))
        
        # If we exit the loop, all moves are complete
        return None

    def save_state(self):
        # Return a copy of the current stack state (can be serialized to JSON/file)
        return self.stack.copy()

How to Use It #

Initialize and Run Moves #

# Start a new puzzle with 3 disks
hanoi = ResumableHanoi(3)

# Get the first few moves
print(hanoi.get_next_move())  # Output: ('A', 'C')
print(hanoi.get_next_move())  # Output: ('A', 'B')
print(hanoi.get_next_move())  # Output: ('C', 'B')

Save and Resume Progress #

# Save the current state mid-solution
saved_progress = hanoi.save_state()

# Simulate an interruption—later, resume from the saved state
resumed_hanoi = ResumableHanoi(saved_state=saved_progress)

# Continue getting moves where we left off
print(resumed_hanoi.get_next_move())  # Output: ('A', 'C')
print(resumed_hanoi.get_next_move())  # Output: ('B', 'A')
print(resumed_hanoi.get_next_move())  # Output: ('B', 'C')
print(resumed_hanoi.get_next_move())  # Output: ('A', 'C')
print(resumed_hanoi.get_next_move())  # Output: None (puzzle complete)

Key Details to Note #

• State Serialization: The save_state() method returns a list of tuples, which you can easily serialize to JSON, save to a file, or store in a database for persistent interruptions.
• Flexibility: You can adapt this to any peg naming scheme, add visualizations (e.g., update a GUI after each move), or extend it to track move counts for your project.
• Non-Recursive: Unlike the standard recursive approach, this uses an explicit stack, so you have full control over when each step executes—perfect for pausing/resuming.

内容的提问来源于stack exchange，提问作者Sarah Collins