Imagine you're trying to find your way through a physical hedge maze. You come to a fork in the path: left or right. You don't have a map, so you pick left. You walk for a few minutes, turn another corner, and suddenly—dead end. A brick wall.

What do you do? You don't just stay there staring at the wall. You turn around, walk back to that last fork where you had a choice, and try the right path instead. You essentially "undo" your last few decisions to get back to a state where a different choice was possible. That, in a nutshell, is backtracking.

Mapping the Maze to Python

When we translate this to code, the "paths" are recursive function calls, and the "dead end" is a condition that returns False. Here is how the analogy maps directly to the logic we'll use:

• The Fork in the Road: A loop that iterates through all possible candidates for the current position.
• Taking a Path: Making a recursive call to move to the next level of the problem.
• The Dead End: A base case or a constraint check (like if not is_valid()) that tells us this path is a failure.
• Turning Around: The act of returning from a recursive call and immediately reverting the change you made to your state.

The N-Queens Logic: A Study in State Management

One of the cleanest ways to see this in action is the N-Queens problem—trying to place N queens on an N×N chessboard so that no two queens threaten each other. I've seen a lot of students struggle here because they forget the most important part: cleaning up after themselves.

def solve_n_queens(n):
    board = [["." for _ in range(n)] for _ in range(n)]
    results = []

    def is_safe(row, col):
        # Check column
        for i in range(row):
            if board[i][col] == "Q":
                return False
        
        # Check upper-left diagonal
        for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
            if board[i][j] == "Q":
                return False
        
        # Check upper-right diagonal
        for i, j in zip(range(row-1, -1, -1), range(col+1, n)):
            if board[i][j] == "Q":
                return False
        
        return True

    def backtrack(row):
        if row == n:
            # We reached the end! Copy the board state into results
            results.append(["".join(r) for r in board])
            return

        for col in range(n):
            if is_safe(row, col):
                # 1. Make a choice
                board[row][col] = "Q"
                
                # 2. Explore the consequences
                backtrack(row + 1)
                
                # 3. Undo the choice (The Backtrack)
                board[row][col] = "."

    backtrack(0)
    return results

The Art of the Undo

Look closely at board[row][col] = ".". If you delete that line, the code fails miserably. Why? Because the algorithm will leave "ghost" queens on the board from paths that it already decided were dead ends.

I always tell people to think of backtracking as a "leave no trace" policy. If you change a global list, a set, or a board state before diving deeper into recursion, you are responsible for resetting that state exactly as you found it. If you don't, the next branch of your search tree will be operating on corrupted data.

The pattern is almost always the same: Choose $\rightarrow$ Explore $\rightarrow$ Un-choose. Master that rhythm, and you can solve almost any constraint-satisfaction problem, from Sudoku solvers to complex scheduling algorithms.

📋 Practical Task

The Word Search Puzzle Finder

You've been tasked with building a search engine for a word search puzzle. Given a 2D grid of characters and a target word, you need to determine if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are those horizontally or vertically neighboring. You cannot use the same cell more than once for a single word.

Your Goal: Implement the exists function using a backtracking approach. Remember to mark cells as visited so you don't loop back on yourself, and—crucially—unmark them as you backtrack so other potential paths can use them.

def exists(board, word):
    rows = len(board)
    cols = len(board[0])
    
    def backtrack(r, c, index):
        # TODO: Implement the backtracking logic here
        # 1. Base case: if index == len(word), we found it!
        # 2. Check boundaries and if board[r][c] matches word[index]
        # 3. Mark the cell as visited (e.g., replace with a temporary character)
        # 4. Explore all 4 neighbors recursively
        # 5. Unmark the cell (backtrack)
        pass

    for r in range(rows):
        for c in range(cols):
            if backtrack(r, c, 0):
                return True
    return False

# Test Case
grid = [
    ['A','B','C','E'],
    ['S','F','C','S'],
    ['A','D','E','E']
]
print(exists(grid, "ABCCED")) # Should return True
print(exists(grid, "SEE"))    # Should return True
print(exists(grid, "ABCB"))   # Should return False