Backtracking 101
Tags: datastructures, dsa, backtracking, algorithms
Published: 2023-09-23 15:19:36

Welcome, dear readers, to the final installment of our algorithm design series. I hope you've been enjoying this journey and gaining a solid grasp of the concepts presented in my blogs.

In this article, we'll delve into the fascinating realm of backtracking algorithms.

## Introduction

Imagine a lock that emits a satisfying "click" when you enter the correct digit for each level. To unlock it, you must first find the first digit, then the second, and continue in sequence until the lock opens. This approach is straightforward and efficient, akin to a greedy algorithm, resulting in a swift solution. However, let's consider a different scenario: an old, finicky lock that produces the same sound not only for the correct digit but also for other digits. When attempting to identify the first ring's digit, you may encounter multiple instances of this sound. At this juncture, reaching the solution isn't a direct path; instead, you must explore various states. If those states don't yield the desired solution, you'll need to backtrack one step at a time to uncover the next viable option. This intelligent approach, involving pruning or bounding functions, significantly accelerates your progress. Today, we explore problems that can be elegantly solved using the backtracking algorithm.

### Problems on the Backtracking Algorithm:

1. **N Queens Problem:** Consider the N Queens Problem, where you're tasked with arranging N queens on an NxN chessboard in a way that no two queens threaten each other.
    

```python
def is_feasible(board, row, col):
    for i in range(row):
        if board[i][col] == 1:
            return False
        for j in range(col):
            if board[i][j] == 1 or board[i][col - j] == 1 or (col - j >= 0 and board[i][col - j] == 1):
                return False
    return True

def solve_n_queens(n):
    board = [[0] * n for _ in range(n)]

    def backtrack(row):
        if row == n:
            result.append(["".join(["Q" if cell == 1 else "." for cell in row]) for row in board])
            return
        for col in range(n):
            if is_feasible(board, row, col):
                board[row][col] = 1
                backtrack(row + 1)
                board[row][col] = 0

    result = []
    backtrack(0)
    return result

# Example usage:
n = 4
solutions = solve_n_queens(n)
for solution in solutions:
    for row in solution:
        print(row)
    print()
```

1. **Tower of Hanoi:** The Tower of Hanoi puzzle involves moving disks from one pillar to another while ensuring that a larger disk never rests on top of a smaller one. This classic puzzle has roots in India and is often linked to an intriguing prophecy.
    

```python
def tower_of_hanoi(num, source, auxiliary, target):
    if num == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    tower_of_hanoi(num - 1, source, target, auxiliary)
    print(f"Move disk {num} from {source} to {target}")
    tower_of_hanoi(num - 1, auxiliary, source, target)

# Example usage:
tower_of_hanoi(3, 'A', 'B', 'C')
```

1. **Sudoku Solver:** The Sudoku puzzle is a classic problem where you need to fill a 9x9 grid with digits so that each column, each row, and each of the nine 3x3 subgrids (called "regions") contains all of the digits from 1 to 9 without repetition.
    

```python
def solve_sudoku(board):
    def is_valid(board, row, col, num):
        for i in range(9):
            if board[row][i] == num or board[i][col] == num or board[3*(row//3)+i//3][3*(col//3)+i%3] == num:
                return False
        return True

    def solve():
        for row in range(9):
            for col in range(9):
                if board[row][col] == '.':
                    for num in map(str, range(1, 10)):
                        if is_valid(board, row, col, num):
                            board[row][col] = num
                            if solve():
                                return True
                            board[row][col] = '.'
                    return False
        return True

    solve()

# Time Complexity: O(9^(n*n)) where n is the size of the board.
# Space Complexity: O(n*n) for the board itself.
```

1. **Word Search:** Given a 2D board of letters and a word, determine if the word can be constructed by connecting adjacent letters horizontally or vertically.
    

```python
def exist(board, word):
    def dfs(row, col, word_index):
        if word_index == len(word):
            return True
        if row < 0 or row >= len(board) or col < 0 or col >= len(board[0]) or board[row][col] != word[word_index]:
            return False
        original_char = board[row][col]
        board[row][col] = '#'
        found = (dfs(row + 1, col, word_index + 1) or
                 dfs(row - 1, col, word_index + 1) or
                 dfs(row, col + 1, word_index + 1) or
                 dfs(row, col - 1, word_index + 1))
        board[row][col] = original_char
        return found

    for row in range(len(board)):
        for col in range(len(board[0])):
            if dfs(row, col, 0):
                return True
    return False

# Time Complexity: O(m*n*4^L) where L is the length of the word.
# Space Complexity: O(L) for recursion stack.
```

1. **Subset Sum:** Given a set of positive integers and a target sum, determine if there exists a subset of the set that sums up to the target.
    

```python
def subset_sum(nums, target):
    def backtrack(index, current_sum):
        if current_sum == target:
            return True
        if current_sum > target or index == len(nums):
            return False

        if backtrack(index + 1, current_sum + nums[index]):
            return True
        return backtrack(index + 1, current_sum)

    return backtrack(0, 0)

# Time Complexity: O(2^n) where n is the number of elements in the set.
# Space Complexity: O(n) for recursion stack.
```

Remember that backtracking problems can vary greatly in complexity, and optimizing them further may require more advanced techniques like memoization or dynamic programming.

These are just a few examples of problems that can be elegantly solved using backtracking algorithms. The power of backtracking lies in its ability to navigate through complex decision spaces, allowing you to explore and find solutions efficiently.

✨ Our algorithmic adventure has reached its final chapter, but the journey continues! 🚀 Explore the complete series for more insights: [**Read the Full Algorithm Design Series**](https://coolcoderr.hashnode.dev/series/algo-design)

💌 Stay in the loop with our latest content! Subscribe to our newsletter: [**Subscribe Now**](https://coolcoderr.hashnode.dev/newsletter)

Thank you for joining us on this exciting coding voyage! 🙌💻

HappyCoding!