Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

python
communitycreator

What is backtracking in Python?

shreshta

What is backtracking?

Backtracking includes deciding on the simplest choice out of many possibilities. We first select a choice and back down from it if we attain a kingdom in which that particular choice no longer provides the desired solution.

We repeat that procedure and go through all of the available options until we find the preferred solution.

Algorithms that use backtracking

Some algorithms that use backtracking include:

  1. N-queens problem
  2. Graph coloring
  3. Crosswords
  4. Rat in the maze

Recursion vs. backtracking

Recursion involves a function calling itself until it reaches the base case.

Backtracking uses recursion to discover all of the possibilities until we get the best end result for the problem.

Code

The code below is an example of finding all of the possible arrangements of a given set of letters.

def permutation(list, res):
   if list == 1:
      return res
   else:
      return [ 
         y + x
         for y in permutation(1, res)
         for x in permutation(list - 1, res)
      ]
print(permutation(1, ["a","b","c"]))
print(permutation(2, ["a","b","c"]))

Explanation

When we select a pair, we use backtracking to see if that particular pair was previously created. The pair is added to the answer list if it hasn’t already been formed; otherwise, it is ignored.

RELATED TAGS

python
communitycreator
RELATED COURSES

View all Courses

Keep Exploring