The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

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