Member-only story
Backtracking for Beginners — Fundamental computer science concept
In this post, we’re going to delve into one of the most powerful, versatile and widely-used techniques known as Backtracking.
What is Backtracking?
At its core, backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally, one piece at a time. If a solution that we’ve begun building can’t be completed into a valid solution (due to constraints or rules of the problem), we ‘backtrack’ to the last valid state and try a different path.
Picture yourself lost in a maze, where you can only move forward. Each time you reach a dead-end, you backtrack to the previous intersection and try a different path. Eventually, using this method, you’ll explore the whole maze. That’s backtracking!
Backtracking is used in many algorithms and computer science problems, including:
- Combinatorial problems (e.g., generating all permutations of a string)
- Constraint Satisfaction Problems (e.g., Sudoku, N-Queens Problem)
- Puzzles and games (e.g., maze-solving, Chess)
Let’s understand it further with different variations of backtracking.
