backtracking - OpenGenus IQ: Computing Expertise & Legacy

Iterative Backtracking

In this article, we will be exploring the idea of backtracking with the help of iteration (Iterative Backtracking) along with example as well. The Time and Space Complexity will be discussed at the end of the article.

game theory

Game Tree

In this article, we have covered the concept of how Backtracking help us to solve Game Tree. We will solve the Game Tree Problem by making use of the Minimax Algorithm. We have presented the Time and Space Complexity for various cases.

backtracking

Backjumping

In this article, we have covered the concept of Backjumping which is an improvement to the Backtracking Algorithm. We will solve the N Queens Problem by making use of the Backjumping Algorithm. We have presented the Time and Space Complexity for various cases.

backtracking

Solve Crossword using Backtracking

In this article, we have covered the Backtracking Algorithm for Crossword and compared with the Brute Force approach. We have presented the Time and Space Complexity for various cases.

backtracking

Backtracking Algorithm for Sudoku

In this article, we have covered the Backtracking Algorithm for Sudoku and compared with the Brute Force approach. We have presented the Time and Space Complexity for various cases.

Algorithms

Recursive Backtracking

Backtracking is one of the many algorithmic techniques that can be used to solve various problems. In this article, we will exploring the idea of backtracking with the help of recursion (Recursive Backtracking) along with examples as well.

Algorithms

Knight’s Tour Problem

The Knight's Tour Problem is one of the famous problem in which we have the knight on a chessboard. The knight is supposed to visit every square exactly once. We have explored Backtracking and Warnsdorff's algorithm.

Algorithms

8 Queens Problem using Backtracking

In this article, we will solve the 8 queens problem using backtracking which will take O(N!) time complexity. We demonstrate it with code.

Algorithms

Subset Sum Problem solved using Backtracking approach 【O(2^N) time complexity】

In this article, we will solve Subset Sum problem using a backtracking approach which will take O(2^N) time complexity

Algorithms

All Valid Word Breaks of a Sentence 【O(2^N) time complexity】

We are given with a valid sentence without any spaces and we are given with a dictionary of words. We need to print all the possible ways to break the sentence so that all the breaked words belongs to the dictionary.

Algorithms

Using Bron Kerbosch algorithm to find maximal cliques in O(3^(N/3))

Bron–Kerbosch algorithm is an enumeration algorithm for finding maximal cliques in an undirected graph. Any n-vertex graph has at most 3^n⁄3 maximal cliques, and the worst-case running time of the Bron–Kerbosch algorithm (with a pivot strategy) is O(3^n⁄3).