Backtracking is used when we want to generate multiple solutions until we have the right one(s).
For example generating sequences of numbers on different positions like:
123 132 321 312 231 213 etc.
More details about the backtracking algorithm:
Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example of the use of backtracking is the eight queens puzzle, that asks for all arrangements of eight queens on a standard chessboard so that no queen attacks any other. In the common backtracking approach, the partial candidates are arrangements of k queens in the first k rows of the board, all in different rows and columns. Any partial solution that contains two mutually attacking queens can be abandoned, since it 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 useless, for example, for locating a given value in an unordered table. When it is applicable, however, backtracking is often much faster than brute force enumeration of all complete candidates, since it can eliminate a large number of candidates with a single test.Backtracking 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[citation needed]) 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. Backtracking is also utilized in the (diff) difference engine for the MediaWiki software.Backtracking depends on user-given "black box procedures" that define the problem to be solved, the nature of the partial candidates, and how they are extended into complete candidates. It is therefore a metaheuristic rather than a specific algorithm — although, unlike many other meta-heuristics, it is guaranteed to find all solutions to a finite problem in a bounded amount of time.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.
How does it basicaly work?
We have an array in which we store the solution (the st array).
We generate a member for the array and check that if we add it to the current solution then the solution is still valid. If it is then we add and go to the next member of the array that needs to be generated. If we have generated enough members for the current solution then we have a valid solution for our problem.
If the generated member is not valid the we try to generate another one if none can be found we go to the previous member and regenerate it (but differently from what it currently is because the next member doesnt have a solution). If none is found we again go to the previous member and so on. If we reach 0 then there is no solution.
I'm sure my explanation is very confusing so check the code bellow.
My implementation of this algorithm:
Code:
#include<ios tream.h>
#include<fstream.h>
intst[100],n,p;
//This function will print the solution to the user if the current solution is valid
void show(int k){
int i;
for (i=1;i<=p;i++)
cout<<st[i]<<" ";
cout<<endl;
}
//Check if the member K of the solution is valid.
int valid(int k){
int i;
for(i=1;i<=k-1;i++)
if (st[i]==st[k])
return 0;
return 1;
}
int main(){
int m,k;
ifstream f("data.in");
f>>n>>p;
//we start with member 1 of the solution equal to 0
st[1]=0;
k=1;
//while we still have a member in the solution
while(k!=0){
//if we have reached the needed members in st then print and regenerate the previous member
if(k==p+1)
show(--k);
//if we can still increase the current member (generate a new value for it)
if (st[k]<n){
//increase current member
st[k]++;
//check if its valid after incrementation
if (valid(k))
//if it is then initiate the next member with 0
st[++k]=0;
}
else
//if we cannot work anymore with the current member we go to the previous one
k--;
}
return 0;
}