1. Backtracking is one of the most general techniques. In this technique, we search for the set of solutions or optimal solution which satisfies some constraints.

2. One way of solving a problem is by exhaustive search, we enumerate all possible solutions and see which one produces the optimum result

3. For example, for the Knapsack problems, we could look at every possible subset objects, and find out one which has the greatest profit value and at the same time not greater than the weight bound.

4. Backtracking is a variation of exhaustive search, where the search is refined by eliminating certain possibilities. Backtracking is usually faster method than an exhaustive search.

Graph Coloring Problem

In this problem, for any given graph G we will have to color each of the vertices in G in such a way that no two adjacent vertices get the same color and the least number of colors are used.

Solution:

i. First take input number of vertices and edges in graph G.

ii. Then input all the indexes of adjacency matrix of G whose value is 1. Now we will try to color each of the vertex.

iii. A next_color(k) function takes in index of the kth vertex which is to be colored. First we assign color1 to the kth vertex.

iv. Then we check whether it is connected to any of previous (k-1) vertices using backtracking.

v. If connected then assign a color x[i]+1 where x[i] is the color of ith vertex that is connected with kth vertex.