DEV Community: Huimin He

Understanding Backtracking in Algorithms with Python Examples

Huimin He — Wed, 20 Dec 2023 18:12:05 +0000

Understanding Backtracking in Algorithms with Python Examples

Backtracking is a fundamental algorithmic technique, often used in solving complex computational problems. It's a method of exhaustive search, notable for its ability to eliminate large chunks of the search space efficiently. In this article, we'll delve into what backtracking is, its use cases, and provide Python examples to illustrate its implementation.

Summary

Backtracking algorithms are ideal for problems that involve decision making, constraint satisfaction, and finding all possible solutions. They're used when:

Multiple decisions lead to a final solution.
Constraints need to be satisfied at each step.
All possible solutions are required, not just any solution.

If your problem fits into these categories, backtracking is likely a suitable approach.

Use Cases for Backtracking

Combination and Permutation Problems: Backtracking is highly effective for generating all possible combinations or permutations of a given set of elements. For example, generating all possible subsets or arrangements of numbers in an array.
Puzzle Solving: Problems like Sudoku, N-Queens, and crossword puzzles can be solved using backtracking. In these problems, you incrementally build a solution and backtrack when a constraint is violated.
Graph Problems: In scenarios like finding all possible paths between two nodes in a graph, backtracking can be used to explore paths and backtrack when a dead end is reached.
String Manipulation: Problems involving generating all possible arrangements of letters or characters in a string, such as generating all anagrams, often use backtracking.
Decision Making: For problems where you need to make a sequence of decisions that lead to a solution (e.g., solving a maze, or deciding to include/exclude elements to meet a certain criterion), backtracking can be used to explore all potential decision paths.
Game Solving: Many game strategy problems, such as finding the best move in a chess game, can be approached with backtracking, especially when combined with other algorithms like Minimax.
Constraint Satisfaction Problems: These are problems where you need to meet a series of constraints and find a solution that satisfies them all, such as assigning variables without conflict in certain conditions.

Python Examples

Example 1: Generating Permutations

def permute(nums):
    def backtrack(start, end):
        if start == end:
            result.append(nums[:])
        for i in range(start, end):
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1, end)
            nums[start], nums[i] = nums[i], nums[start]

    result = []
    backtrack(0, len(nums))
    return result

print(permute([1, 2, 3]))

Example 2: Solving N-Queens Problem

Implicit Reset by Overwriting: Every time the backtrack function is called for a row, it tries all columns (due to the for col in range(n) loop). When it assigns board[row] = col, it's effectively overwriting the previous value. This is where the board is implicitly "reset." If the placement is not valid, or if all possibilities for the next row are exhausted, the function returns to the previous call, where the loop continues to try the next column.

def solveNQueens(n):
    def is_valid(board, row, col):
        for i in range(row):
            if board[i] == col or \
               i - board[i] == row - col or \
               i + board[i] == row + col:
                return False
        return True

    def backtrack(row):
        if row == n:
            solution = []
            for i in board:
                line = '.' * i + 'Q' + '.' * (n - i - 1)
                solution.append(line)
            results.append(solution)
            return
        for col in range(n):
            if is_valid(board, row, col):
                board[row] = col
                backtrack(row + 1)

    results = []
    board = [-1] * n
    backtrack(0)
    return results

print(solveNQueens(4))

Conclusion

Backtracking is a powerful technique for solving problems that require exploring multiple paths and satisfying constraints. It's especially useful in combination and permutation problems, puzzle solving, and decision-making scenarios. The Python examples provided demonstrate the implementation of backtracking in real-world problems. Remember, backtracking may not be the most efficient for all problems, but it's an essential tool in a developer's toolkit for certain types of challenges.

Shunting Yard algorithm for Leetcode Basic calculator

Huimin He — Sat, 16 Dec 2023 00:03:41 +0000

Here is the best way to solve the Leetcode Basic calculator I, II, III using Shunting Yard algorithm.

The Shunting Yard algorithm, devised by Edsger Dijkstra, is primarily used for parsing mathematical expressions, specifically for converting infix expressions (like the ones we normally use in mathematics, e.g., "3 + 4") into postfix (Reverse Polish Notation - RPN) or prefix notation.

Code:

ops = {"*": 2, "/": 2, "+": 1, "-": 1}


def get_precedence(op):
    return ops[op] if op in ops else 0

def shunting_yard(input):
    ops = []
    res = []

    tokens = input.split(" ")
    for token in tokens:
        if token.isnumeric():
            res.append(token)
        elif token in "+-*/":
            while ops and get_precedence(ops[-1]) > get_precedence(token):
                res.append(ops.pop())
            ops.append(token)
        elif token == "(":
            ops.append(token)
        elif token == ")":
            while ops and ops[-1] != "(":
                res.append(ops.pop())
            ops.pop()
    res += ops[::-1]
    return res

The Shunting Yard algorithm is a method for parsing mathematical expressions specified in infix notation (e.g., 3 + 4) and converting them into postfix notation (e.g., 3 4 +) or Reverse Polish Notation (RPN). This algorithm is particularly useful because operations in postfix notation can be easily computed using a stack, allowing for efficient calculation of expressions.

Here's an explanation of each block in the shunting_yard function:

   if token.isnumeric():
       res.append(token)

Purpose: This checks if the current token is a number. If it is, it's directly added to the result list. In postfix notation, numbers are placed in the same order as they appear in the infix expression.

   elif token in "+-*/":
       while ops and get_precedence(ops[-1]) > get_precedence(token):
           res.append(ops.pop())
       ops.append(token)

Purpose: This part handles operators. It uses the get_precedence function to determine the precedence of the operators. If the operator at the top of the operator stack (ops) has higher precedence than the current token, that operator is popped from the stack and added to the result list. This ensures that operators with higher precedence are evaluated first in the output expression. The current token is then pushed onto the operator stack.

   elif token == "(":
       ops.append(token)

Purpose: When an opening parenthesis is encountered, it's pushed onto the operator stack. Parentheses are used to override the usual precedence of operators to ensure the expression within them is evaluated first.

   elif token == ")":
       while ops and ops[-1] != "(":
           res.append(ops.pop())
       ops.pop()

Purpose: When a closing parenthesis is encountered, the function pops operators from the operator stack and adds them to the result list until an opening parenthesis is found. This ensures that the expression within the parentheses is correctly handled. The opening parenthesis is then popped from the stack but not added to the result list, as parentheses are not used in postfix notation.

   res += ops[::-1]

Purpose: After processing all tokens, any remaining operators on the operator stack are popped and added to the result list. This is necessary to ensure that all parts of the expression are included in the final postfix expression.

The Shunting Yard algorithm is a neat solution for converting infix expressions, which are more human-readable, into postfix expressions, which are easier for machines to evaluate.