Backtracking

Backtracking is an approach to problem solving which is usually applied to constraint satisfaction problems like puzzles. In a backtracking solution, a search path is followed and the algorithm backtracks at a particular point ( also known as decision point ) in the path as soon as it realizes that this path won’t lead to a valid solution and then it follows another path starting from a previous decision point. In this way, different paths are repeatedly explored to arrive at the final solution.
Consider the problem of solving a sudoku. A naive algorithm will try to find every possible arrangement of numbers and checks if the problem can be solved with a particular arrangement but the backtracking algorithm provides a much better and efficient solution.
Backtracking is basically a refinement of the brute-force approach in which the solution to a problem is found using systematic search rather than trying out possible solutions blindly.
Let’s solve some problems using backtracking approach.

Back | Next

All problems on Backtracking technique
* Given a maze in the form of a matrix of size n x n. A robot is placed at cell ( 0, 0 ). Print all possible paths that robot can take to reach the last cell ( n-1, n-1 ) of the maze
* Given a maze in the form of a matrix of size n x n with all elements as 0 or 1. 0 denotes safe cell & 1 denotes dangerous cell. A rat is placed at cell ( 0, 0 ). Print a safe path ( if exists ) which rat can take to reach last cell ( n-1, n-1 ).
* Solve the Knight’s Tour problem
* Solve the N-Queens problem
* Given a set of candidate values in an array & a target x, find all possible ways in which candidate values can be added to get x. We can use each candidate value any number of times
About    Contact    Sitemap    Terms    Privacy