BackTracking

backtracking is used as a searching technique
so what are we searching basically ?
we are searching the tree for a particular goal leaf node/nodes.

How to apply backtracking
1) Make a choice
2) Compute the consequences
3) If the search is unsuccessful or needs to continue for some other reason,
4) Undo the consequences,
5) Undo the choice
6) Make a different choice
7) repeat from 2

Every language that supports loops, supports backtracking .

basic problem 1 : just by following the definition given above we can have a very trivial case where backtracking can be applied using just for loops and continue statement
problem : find the number of different Pythagoras triplets where hypotenuse is less than 100 .
solution :
1) make choice of sides in the three for loops
2) compute the condition for triplet, if condition fails, means we need to backtrack and stop processing further solution (printing in this case) so just continue; and start with new values of one of the sides and again repeat the above steps.

#include<stdio.h>
int main()
{
	int n = 100;
	int i,j,k,count=1;
	for(i=5;i<=n;i++)
	{
		for(j=1;j<i;j++)
		{
			for(k=1;k<=j;k++)
			{
				if((j*j + k*k )!= i*i)
				 continue;
				printf("%2d | %d %d %dn",count++,i,j,k);
			}
		}
	}
	return 0;
}

code on ideone :http://ideone.com/vDlB0
second problem : generate all the permutations of a string.

solution at : http://quickalgo.blogspot.com/2011/08/permutations-of-string.html
note: notice the tree in the above post, the solutions are the leaf nodes  and we are doing depth first traversal in that tree printing only the leaf nodes.
code :

#include <stdio.h>
#include <string.h>

void swap(char*a,char*b);
void permute(char* s, int i, int n);

int main()
{
	char s[] = "abc";    
	int n = strlen(s);
	permute(s,0,n);      
	return 0;
}
void swap(char*a,char*b)
{
	char t;
	t = *a;
	*a=*b;
	*b=t;
}

void permute(char* s, int i, int n)
{
	int j;
	if(i==n)   // reached the leaf node.
	{
		printf("%sn",s); // process solution  
	}
	else
	{
		for(j=i;j<n;j++)
		{
			swap((s+i),(s+j));  // choose an option and move forward
			permute(s,i+1,n);   // compute new solution
			swap((s+i),(s+j));  // backtrack after printing
		}
	}
}

third problem : 8 queens puzzle
solution is here : http://quickalgo.blogspot.com/2011/08/8-queens-problem.html
code for reference

#include<stdio.h>
#include<stdlib.h>
int t[8] = {-1};
int sol = 1;

void printsol()
{
	int i,j;
	char crossboard[8][8];
	for(i=0;i<8;i++)
	{
		for(j=0;j<8;j++)
		{
			crossboard[i][j]='_';
		}
	}
	for(i=0;i<8;i++)
	{
			crossboard[i][t[i]]='q';
	}

	for(i=0;i<8;i++)
	{
		for(j=0;j<8;j++)
		{
			printf("%c ",crossboard[i][j]);
		}
		printf("n");
	}  
}
int empty(int i)
{
	int j=0;
	while((t[i]!=t[j])&&(abs(t[i]-t[j])!=(i-j))&&j<8)j++;
	return i==j?1:0;
}

void queens(int i)
{
	for(t[i] = 0;t[i]<8;t[i]++)
	{
		if(empty(i))
		{
			if(i==7){
				printsol();
				printf("n solution %dn",sol++);
			}
			else
			queens(i+1);
		}
	}
}



int main()
{
	queens(0);
	return 0;
}

problem 4: knight's tour problem
The knight is placed on the empty board and, moving according to the rules of chess, must visit each square exactly once. A knight's tour is called a closed tour if the knight ends on a square attacking the square from which it began (so that it may tour the board again immediately with the same path). Otherwise the tour is open http://en.wikipedia.org/wiki/Knight's_tour

explanation of problem :

what is a knight's tour ==>

sequence of moves (i.e., a tour) by a knight chess piece (which may only make moves which simultaneously shift one square along one axis and two along the other) such that each square of the board is visited exactly once.
solution : problem 5: Rat in a maze

problem 6: coloring a map

problem 7: sudoku puzzle