Table of contents
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:
- 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.
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()
- 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.
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')
- 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.
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.
- 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.
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.
- 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.
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
💌 Stay in the loop with our latest content! Subscribe to our newsletter: Subscribe Now
Thank you for joining us on this exciting coding voyage! 🙌💻
HappyCoding!