Introduction To
Backtracking Algorithm is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.
Backtracking can be applied only for problems which admit the concept of a "partial candidate solution" and a relatively quick test of whether it can possibly be completed to a valid solution.
It is an important tool for solving constraint satisfaction problems, such as crosswords, verbal arithmetic, Sudoku, and many other puzzles. It is often the most convenient (if not the most efficient) technique for parsing, for the knapsack problem and other combinatorial optimization problems. It is also the basis of the so-called logic programming languages such as Icon, Planner and Prolog.
The term "backtrack" was coined by American mathematician D. H. Lehmer in the 1950s. The pioneer string-processing language SNOBOL (1962) may have been the first to provide a built-in general backtracking facility.
Course Structure
Standard Problems
- Subset Sum | Backtracking-4
- Sudoku | Backtracking-7
- Solving Cryptarithmetic Puzzles | Backtracking-8
- Magnet Puzzle | Backtracking-9
- N Queen in O(n) space
- Remove Invalid Parentheses
- Prime numbers after prime P with sum S
- Rat in a Maze with multiple steps or jump allowed
- A backtracking approach to generate n bit Gray Codes
- C++ program for Solving Cryptarithmetic Puzzles
- Print all possible paths from top left to bottom right of a mXn matrix
Misc
- 8 queen problem
- Combinational Sum
- Backtracking to find all subsets
- Power Set in Lexicographic order
- Check if a given string is sum-string
- Fill 8 numbers in grid with given conditions
- Word Break Problem using Backtracking
- Minimize number of unique characters in string
- Partition of a set into K subsets with equal sum
- Warnsdorff’s algorithm for Knight’s tour problem
- Longest Possible Route in a Matrix with Hurdles
- Match a pattern and String without using regular expressions
- Fill two instances of all numbers from 1 to n in a specific way
- Find all distinct subsets of a given set
- Find shortest safe route in a path with landmines
- Find paths from corner cell to middle cell in maze
- Find Maximum number possible by doing at-most K swaps
- Print all palindromic partitions of a string
- Printing all solutions in N-Queen Problem
- Print all possible strings that can be made by placing spaces
- Print all possible strings that can be made by placing spaces
- Smallest expression to represent a number using single digit
- Given an array A[] and a number x, check for pair in A[] with sum as x
- Combinations where every element appears twice and distance between appearances is equal to the value