Backtracking with C++

Backtracking is an algorithmic technique that considers searching in every possible combination for solving a computational problem.

  • It is known for solving problems recursively one step at a time and removing those solutions that do not satisfy the problem constraints at any point in time.
  • It is a refined brute force approach that tries out all the possible solutions and chooses the best possible ones out of them.
  • The backtracking approach is generally used in cases where there are possibilities of multiple solutions.

Backtracking — How it works?

In any backtracking problems, the algorithm tries to find a path to the feasible solution which has some intermediary checkpoints. In case they don’t lead to a feasible solution, the problem can backtrack from the checkpoints and take another path in search of the solution. Consider the below example:

  • Here S is the starting point of the problem. We start from S, we go to find solution S1 via the intermediate point I1. But we find that the solution S1 is not a feasible solution to our problem. Hence, we backtrack (go back) from S1, go back to I1, go back to S, and then check for the feasible solution S2. This process happens till we arrive at a feasible solution.
  • Here, S1 and S2 are not feasible solutions. Only S3 is a feasible solution as per our example. When we look at this example, we can see that we traverse through all possible combinations, till we arrive at the feasible solution. This is why we say that backtracking is a brute-force algorithmic technique.
  • The above tree representation of a problem is called as a “space state tree”. It represents all possible states (solution or non-solution) of that given problem.
  • The final algorithm can be summarised as:
    Step 1 − if the current point is a feasible solution, return success
    Step 2 − else if all paths are exhausted (i.e current point is an endpoint), return failure since we have no feasible solution.
    Step 3 − else if the current point is not an endpoint, backtrack and explore other points and repeat the above steps.

Maze Traversal Algorithm Using Backtracking

Backtracking is trying out all possibilities using recursion, exactly like brute force.
Suppose you have to make a series of decisions, among various choices, where :

Backtracking is a methodical way of trying out various sequences of decisions until you find one that “works”.

Let's look at an example to explain this further.

At each intersection, you have to decide between three or fewer choices:

You don’t have enough information to choose correctly. Each choice leads to another set of choices. One or more sequences of choices may (or may not) lead to a solution.

So, you explore each option thoroughly and once you cannot find a solution using the option selected, you come back and try one of the remaining options.

Backtracking Pseudocode

Pseudocode for the above question would be :

In general, the usual pseudocode for any backtracking solution is :

Graph Coloring Algorithm Using Backtracking

What is a graph coloring problem?

Graph coloring problem involves assigning colors to certain elements of a graph subject to certain restrictions and constraints. This has found applications in numerous fields in computer science. For example:

  • Sudoku: This game is a variation of the Graph coloring problem where every cell denotes a node (or vertex) and there exists an edge between two nodes if the nodes are in the same row or same column or same block.
  • Geographical maps: There can be cases when no two adjacent cities/states can be assigned the same color in the maps of countries or states. In this case, only four colors would be sufficient to color any map.

Vertex coloring is the most commonly encountered graph coloring problem. The problem states that given colors, determine a way of coloring the vertices of a graph such that no two adjacent vertices are assigned the same color.

Analysis

Input:

  • A graph represented in a 2D array format of size where V is the number of vertices in the graph and the 2D array is the adjacency matrix representation and value is 1 if there is a direct edge from i to j, otherwise, the value is 0.
  • An integer that denotes the maximum number of colors which can be used in graph coloring.
  • Consider the input as shown in the image below:
  • The above graph can be represented as follows:
  • Consider

Output:

  • Return array color of the size that has numbers from 1 to m. Note that represents the color assigned to the ith vertex.
  • Return if the graph cannot be colored with colors.

Solution:

Naive Approach:

  • The brute force approach would be to generate all possible combinations (or configurations) of colors.
  • After generating a configuration, check if the adjacent vertices have the same color or not. If the conditions are met, add the combination to the result and break the loop.
  • Since each node can be colored by using any of the colors, the total number of possible color configurations are mV. The complexity is exponential which is very huge.

Pseudo Code:

  • Time Complexity: O(mV).
  • Space Complexity: O(V) which is for storing the output array.

Using Backtracking:

  • By using the backtracking method, the main idea is to assign colors one by one to different vertices right from the first vertex (vertex 0).
  • Before color assignment, check if the adjacent vertices have the same or different colors by considering already assigned colors to the adjacent vertices.
  • If the color assignment does not violate any constraints, then we mark that color as part of the result. If the color assignment is not possible then backtrack and return false.
  • Time Complexity: O(mV). Since backtracking is also a kind of brute force approach, there would be total O(mV) possible color combinations. It is to be noted that the upper bound time complexity remains the same but the average time taken will be less due to the refined approach.
  • Space Complexity: O(V) for storing the output array in O(V) space

Question 1: Modular Expression

Implement .

In other words, given , and ,
find (AB)%C.

Solution:

Time Complexity: O(log n)

Question 1: Reverse Link List Recursion

Reverse a linked list using recursion.

Example :
Given ,

return .

Solution:

Technical Details behind all your favorite products.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store