Backtracking is a systematic way of trying out different sequences of decisions until you find one that "works". It is used to solve problems that require exploring all possible configurations.
Build the solution incrementally and abandon a path ("backtrack") as soon as it is determined that it cannot lead to a valid solution.
Place N queens on an N×N chessboard so that no two queens attack each other.
Fill a 9×9 Sudoku grid so that each row, column, and subgrid contains digits 1–9 exactly once.
Find a path from the start to the destination in a maze.
Find all subsets of a given set that sum up to a specific value.
Used in graph traversal and optimization problems.
def solveNQueens(board, row):
if row == N:
print(board)
return
for col in range(N):
if isSafe(board, row, col):
board[row][col] = 1
solveNQueens(board, row + 1)
board[row][col] = 0 # backtrack
Backtracking is a powerful strategy for constraint satisfaction problems. With proper pruning (like using heuristics), it can efficiently find optimal or valid solutions.
Take quizzes related to this topic and see where you stand!
Start Quiz Now