BackTracking

Backtracking is a refinement of the brute force approach, which systematically searches for a solution to a problem among all available options. It does so by assuming that the solutions are represented by vectors (v₁, ..., v_m) of values and by traversing, in a depth first manner, the domains of the vectors until the solutions are found.

When invoked, the algorithm starts with an empty vector. At each stage it extends the partial vector with a new value. Upon reaching a partial vector (v₁, ..., v_i) which can’t represent a partial solution, the algorithm backtracks by removing the trailing value from the vector, and then proceeds by trying to extend the vector with alternative values.

ALGORITHM try(v1,...,vi) 
   IF (v1,...,vi) is a solution THEN RETURN (v1,...,vi) 
   FOR each v DO 
      IF (v1,...,vi,v) is acceptable vector  THEN 
        sol = try(v1,...,vi,v) 
        IF sol != () THEN RETURN sol 
      END 
   END 
   RETURN () 

If S_i is the domain of v_i, then S₁ × ... × S_m is the solution space of the problem. The validity criteria used in checking for acceptable vectors determines what portion of that space needs to be searched, and so it also determines the resources required by the algorithm.

The traversal of the solution space can be represented by a depth-first traversal of a tree. The tree itself is rarely entirely stored by the algorithm in discourse; instead just a path toward a root is stored, to enable the backtracking.

source:  http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch19.html

Let us look at a few classic examples of Backtracking to understand the concept well.


Permutations of a string
Given a string, print all its permutations.  Permutations of a string are all of the same length. All permutations have the same set of characters, but they in different order.
Read more...

---

Solving Maze - Backtracking
Given an MxN maze, find a path from top left corner to bottom right corner. You can only move to right and down. Let 1 denote the places we can go and 0 denotes places, which can't be visited.
Read more...

---

Q3. N-Queens Problem

Given an NxN chessboard, find a solution such that N Queens are placed in non-attacking configurations.
A configuration is attacking if one or more of following occurs:

• Two or more queens are placed in same row
• Two or more queens are placed in same column
• Two or more queens are placed diagonally to each other

Q
				Q
							Q
					Q
		Q
						Q
	Q
				Q

Solution:

#define N 8

#include <stdio.h>

//utility function to check if placing Queen in A[row][col] is a //non-attacking configuration
bool isSafe(int A[N][N], int row, int col)
{
  //check any element in the same column
    for(int i=0; i<row; i++)
{
if(A[i][col] == 1)
return false;
}
//check any element in the same row
for(int i=0; i<col; i++)
{
if(A[row][i] == 1)
return false;
}
//check along the diagonals
for(int i=0; i<row; i++)
{
int diff = row-i;
if(col >= diff)
if(A[i][col-diff] == 1)
return false;
if((col+diff) < N)
if(A[i][col+diff] == 1)
return false;
}
return true;
}

// Main function to solve the N-Queens problem
bool NQueens(int A[N][N], int row)
{
if(row == N)
return true;
for(int j=0; j<N; j++)
{
if(isSafe(A, row, j))
{
A[row][j] = 1;
if(NQueens(A, row+1))
return true;
A[row][j] = 0;
}
    }
return false;
}

//utility function to print the elements of NxN matrix
void printMatrix(int M[N][N])
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
printf("%d  ", M[i][j]);
printf("\n");
}
}

int main()
{
int A[N][N] = {0};
NQueens(A, 0);
printMatrix(A);
getchar();
}

Output:
1  0  0  0  0  0  0  0
0  0  0  0  1  0  0  0
0  0  0  0  0  0  0  1
0  0  0  0  0  1  0  0
0  0  1  0  0  0  0  0
0  0  0  0  0  0  1  0
0  1  0  0  0  0  0  0
0  0  0  1  0  0  0  0



Q4. Subset Sum

Find subset of elements that are selected from a given set whose sum adds up to a given number K.

Solution:

#include <iostream>
using namespace std;

//Utility function to check if adding a number to the solution //set satisfies the constraints or not.
bool isSafe(int A[], int n, int index, int S1, int S2, const int sum)
{
if(S1 + A[index] <= sum)
return true;
if(S1 + S2 < sum)
return false;
}

// A[]   - input array of elements
// n     - number of elements in A
// sol[] - solution array containing values 0/1
// S1    - sum of selected elements from index 0 to (index-1)
// S2    - sum of remaining elements from index to n-1
// index - index of current element in A
// sum   - target sum 
bool subSetSum(int A[], int n, int sol[], int S1, int index, int S2, const int sum)
{
if(S1 == sum)
return true;
for(int i=index; i<n; i++)
{
if(isSafe(A, n, i, S1, S2, sum))
{
sol[i] = 1;
if(subSetSum(A, n, sol, S1+A[i], i+1, S2-A[i], sum))
return true;
sol[i] = 0;
}
}
return false;
}

//compare function for qsort()
int compareFun(const void *v1, const void *v2)
{
if(*(int*)v1 > *(int*)v2)
return 1;
else if(*(int*)v1 < *(int*)v2)
return -1;
return 0;
}


int main(int argc, char* argv[])
{
    // original list of numbers
int A[8] = {10, 5, 3, 1, 2, 4, 15, 20}; 
int sol[8] = {0};
qsort(A, 8, sizeof(int), compareFun);   
    // A[] now contains elements in sorted order
int sum = 30;
bool b = subSetSum(A, 8, sol, 0, 0, 60, sum);
for(int i=0; i<8; i++)
{
        // sol[] contains 0/1 values for elements corresponding           to sorted A[]
if(sol[i])    
cout << A[i] << "  " ; 
}
getchar();
return 0;
}

Output: 1 2 3 4 5 15


Q5. Graph coloring

Given an undirected graph and a number m, determine if the graph can be colored with at most m colors such that no two adjacent vertices of the graph are colored with same color. Here coloring of a graph means assignment of colors to all vertices.

Solution:

#include <iostream>
using namespace std;

#define N 5

bool isSafe(int A[N][N], int arColor[N], int color, int index)
{
for(int i= 0; i<N; i++)
{
if(A[index][i] == 1)
if(arColor[i] == color)
return false;
}
return true;
}

bool graphColor(int A[N][N], int index, int arColor[N], int maxColor)
{
if(index == N)
return true;
for(int i=index; i<N; i++)
{
for(int col = 1; col<=maxColor; col++)
{
if(isSafe(A, arColor, col, i))
{
arColor[i] = col; 
if(graphColor(A, i+1, arColor, maxColor))
return true;
arColor[i] = 0;
}
}
return false;
}
return false;
}

int graphColoring(int A[N][N], int color[N])
{
for(int i = 1; i<=N; i++)
{
if(graphColor(A, 0, color, i))
return i; //returns the number of colors required
}
return N;
}


int main(int argc, char* argv[])
{
// adjacency matrix representation of graph
int Adj[N][N] = {0, 1, 1, 0, 1,
                 1, 0, 1, 1, 1,
                 1, 1, 0, 1, 0,
                 0, 1, 1, 0, 1, 
                 1, 1, 0, 1, 0};
/* [0]-----[1]
| \   / | \
|  \ /  |  \
|   /---|--[2]
|  /    |  /
| /     | /
  [4]-----[3]
*/
int color[N] = {0}; //0 means no color initially
int num = graphColoring(Adj, color);
for(int i=0; i<N; i++)
cout << color[i] << "  ";
 
     getchar();
return 0;
}

Output:  1  2  3  1  3