Backtracking Tutorial using C Program Code Example for Programmers

If you try to solve some combination problem in programming using simple combination approach where you check all possible variations with repetition or permutations of some kind, you would realize that you would have way too many tries that are not necessary.

You should reduce the poll of possible candidates as much as you can, and find a better solution that will use less processor time.

One of possible technique to solve a combination problem is to use backtracking.

We could apply backtracking to both programmatic and real life practical problems.

Let us take a simple example. If you look for all possible ways to place eight queens on a chess board, you would soon realize that if some configurations are not promising, then you should not check all of its derived solutions. Because there is no way that you could find a good solution after you have figure out that this partial solution is not promising.

So, if you have placed four queens on the chess board, and you have figure out that there is no way to place the fifth one, then you don’t need to place the sixth, or seventh, or eight queen.

How does Backtracking Work?

You start with possible solution of the problem, and you build on this basis toward the one of solutions that will satisfy all conditions that you are required to meet.

This way you could find one or all possible solutions for problem you are solving.

At each step you look for a next candidate, and if you notice that this path is not giving you solution, you backtrack one level back, and start with new candidate.

If that level does not contain the adequate solution you backtrack one more level.

If you end up at the root, you could say that the solution is not available, and that it is not possible to solve problem with the given conditions.

In other case, if you find promising candidate it will become part of partial solution that would be used as a part of final solution.

In a way, it works similar to permutations of a set but as soon as you see that there is no solution in that partial permutation you backtrack and do more tests with new candidates, in most cases there are nodes of a graph, and you dismiss all sub candidates that could be derived from an unpromising path.

If you need to find one solution you could stop, and if you wish to find all possible solutions you could store them and present it after you have checked all possible.

From this, you would recognize that it is very recursive and it is one of techniques that would be adequate for recursive implementations.

To create more methodical discussion, we will say that the final vector v0, v1,…,vn is a solution, if it meets all conditions that are set in the beginning of the problem we are solving.

This vector is sometimes of certain dimension, for example if you are solving problems of queen placement, but it could be of dimensions that are smaller or different.

For example, if you try to get convex hull or something similar, where dimension is smaller than whole set of points that we are trying to contain in one convex hull, but you would not be able to figure out how many dots would be in that convex hull, or dimensions could be different if you trying to find paths from one node of the graph to another.

When you have partial solution, it will be represented with v0, v1,…,vi, from this partial sub solution you could go back if you find out that it will not lead you toward the vector that will full fill all conditions, that candidate solution would be replaced with v0,v1,…vi-1, but you should know that vi-1 would also be next choice of that same level, or if you see the possibility to reach a final solution you would create vector that has one more element added, in other words it would be v0,v1,…vi,vi+1.

Now, if you wish to note this as some form of pseudo algorithm you could write it like this:

BacktrackingProcedure( someVector, dimension)
{
  if(someVector==isSolution)
    PrintSolution OR StoreSolution
  else
    CheckAllPromisingCandidates(i)
    {
      someVector addPromissingCandidate(i);
      checkIfCandidatePromising(i);
      BacktrackingProcedure(temporatyVector, increaseDimenzsionOfVector);
    }
}

When Can We Apply This?

For the above general algorithm, we would need one condition.

The problem you are solving, need to have certain property sometimes called as partial candidate solution and you should be able to test this candidate as possible part of the solution.

This could also be imagined as a tree, not always a binary tree in all possible situations, but as a tree with more choices and not all time you should have equal number of choices, but if you pick v0, v1,…vn way to write that, you will have all time k possible picks at the same level. Those situations with less than k choices at one level of the tree would be situations that would be created with improvements or additional conditions.

There are some more techniques that could be combined with backtracking, so that you could improve your solution even more.

For example, if you rotate chess board you could find it same chess board as if it was turned for 180 degrees. This means that one solution could be generated from other, and it is great idea to have half tests if you could. This is one of the tricks that could be applied, but symmetry of some kind is trick that usually creates code that is harder to understand.

Sometimes you could figure out some more tricks, beside symmetry, that could speed up backtracking when it is applied solo.

You should be aware of fact that this method has its limits and that it is not a magic stick, but it will be great benefit in your bag of tricks that you keep aside, for situations that will allow its applications. In some situation it will not generate solution and sometimes the solution would be obtained very slowly.

What are few problems that could be solved using this approach?

This algorithm is applicable in many theoretical problems, but it could be applied in some practical situations as well.

The most famous application is an algorithm for placing eight queens on chess board. It is possible to solve it without backtracking for some cases and for that approach you have function that will generate solution based on formula.

Next interesting problem is Sudoku solver, which could be solved using backtracking. There is knapsack problem solutions with backtracking approach, also you could solve travelling salesperson problem on the graph, find the path in the labyrinth or solve some puzzles, or perhaps find the convex hull.

Our Example Backtracking Problem to Solve

We are going to solve the one of the most traditional problem that allow this algorithm to be applied.

It is a robot that is looking for a path from top left corner toward bottom right corner.

The robot will have tree possible ways to move, down, right or diagonally down+right.

It is interesting to solve this problem with backtracking, but don’t forget that this is not the only way to solve this problem. Also, it is a very good idea to have few additional conditions, or even obstacles.

Here is the backtracking example code:

#include <stdio.h>
#include <stdlib.h>

/* macro to define limits*/
#define MAX_X 4
#define MAX_Y 9

#define END_X 3
#define END_Y 8

/* define structure for one point
   with coordinate x and y */
typedef struct P{int x,y;};

/* functions to present path through matrix,
   check if next move is valid
   with backtrack technique */
void presentPath(P[],int);
int tryC(int m[][MAX_Y],int,int);
void checkPaths(int m[][MAX_Y],int,int,P[],int);

int
main()
{
/* declare start position and
   matrix we are searching paths*/
  int sX=0, sY=0,
  	m[MAX_X][MAX_Y]=
     {
      {0,0,0,1,1,1,0,0,0},
  	{1,1,0,0,0,0,0,0,0},
  	{1,0,1,0,0,1,0,1,0},
  	{0,0,1,1,0,1,1,1,0}
     };
  
  /* array that will serve to memorize the each path */
  P Path[MAX_X+MAX_Y+1];
  
  /* lets go and look for all paths */
  checkPaths(m,sX,sY,Path,0);

  return 0;
}

void 
presentPath(P   Path[MAX_X+MAX_Y+1],
			int k)
{
  for(int i=0; i<k; i++)
    printf("%d, %d",Path[i].x,Path[i].y);
  
  printf("\n\n");
}

int tryC(int m[MAX_X][MAX_Y],int x, int y)
{return ((x>=0)&&(x<MAX_X)&&(y>=0)&&(y<MAX_Y)&&m[x][y]==0);}

void 
checkPaths(int m[MAX_X][MAX_Y],
		   int c_x, int c_y,
		   P Path[MAX_X+MAX_Y+1],int l)
{
  /* will abandon path beyond wall
   and path where we hit the wall.
   your position is at the current
   x and y location*/
  if(!tryC(m,c_x,c_y)) return ;
  
  /* mark the path and memorize */
  m[c_x][c_y]=2; 
  Path[l].x=c_x;Path[l].y=c_y;
  
  /* are we at the searched position
  or check new potential candidates */
  if((c_x==END_X)&&(c_y==END_Y))
  	presentPath(Path,l+1);
  else
  {
  	/* we will try to move down, right and down-right*/
  	checkPaths(m,c_x+1,c_y+1,Path,l+1);
  	checkPaths(m,c_x+1,c_y,Path,l+1);
  	checkPaths(m,c_x,c_y+1,Path,l+1);
  }
  
  /* clear the position that has been marked */
  m[c_x][c_y]=0;
}

Explanation of the Above Backtracking Code

At the beginning of program we have few macros that will be used for limits and if you try to change some of the dimensions it would be easy to change the values in macros.

In our program we declare one data type, which is declared as typedef and it will be used to store the locations of a dot that has two coordinates: x and y. It is very logical to use x and y because you have analogy to coordinates in two dimensions.

Then we forward the functions we will use in our program.

First functions is presentPath, which is used to present the path on the screen. It has array as input value, that array is of P type, as you remember it is a struct, beside that we will need to know how many steps we have stored in that array, so we will have the one more information handed to the function.

Next thing we will use is function that will check if we have bounced into the wall or have we crossed beyond the limits of our matrix. This is very interesting function because it is very compact, and it will return appropriate value.

One more thing in our program is the checkPaths function which will try to find all paths from one location to another with already explained method of backtracking.

We have used recursion because this is one of the moments when it is so logical to use it, but if you would like to experiment with out it you are very welcome.

The argument for our function are : one matrix that will be used to store the configuration of the landscape, next we have to int variables that are used to store current location, then we have array that is used to store path, and also we would need the length of the path.

When we analyse the function first thing we have is test of current location, if it is not promising it will not be considered any more, if location is crossing left boarders of matrix it will not be tested as promising candidate. If the current location with coordinates c_x and c_y is considered it will be marked with 2, so that we could know where the location was filled, after it will be cleared with adequate operation.

Because we wish to present the dot we are currently at, we store that path in array that is used to store path we are travelling.

It is important to explain this if else command. If we have reached the end point of our travel we will present one of the possible paths.

If we are not at end location we will check down-right firs, because that could potentially generate the shortest path first, next we will try to move across x for one place, after we will try to move across y for one place.

This will check all possible paths: down-right, right and down.

There is one more thing left to be done we need to clear the occupied location in matrix.

In main function we will fill the matrix with some zeros and ones, and we will call our function that will in collaboration with other functions find shortest path, without testing paths that are not promising.

Additional Backtracking Exercises

1. Try to find the path in the matrix, if you are allowed to move:
   • up, down, left and right.
   • diagonally in all possible combinations.
2. You are presented with unknown number of dots in two dimension space. Task that should be accomplished is to find the convex hull that will enclose all dots from given set of dots. The dots that will form convex hull are all or part of the dots that are given in that set.
3. Solve the Sudoku.
4. Place eight queens on chess board. Find one or all solutions. After that try to find good algorithm that will enable you to place n queens on chess board with n*n squares.
5. Find a path for a knight through the chess board with condition that the knight must visit all squares and if it is not possible to complete one path from a certain position, find the longest one.
6. Solve back pack problem with backtracking and compare the solution to simple combination and dynamic programming technique.
7. Solve hopping game.