Explaining Backtracking
Keep trying. Every possibility.
27 Jul 2019
View Comments
#computer
#programming
#backtracking
#DFS
#depth
#first
#search
#algorithms
In computer science, Backtracking tries to solve a problem incrementally by try-and-error method, that is by moving backwards when failed to try again, gradually building to a final solution. This technique solves many problems where it appears visually impossible to solve.
Backtracking works closely with depth-first search, infamously known for one of the 2 conventional methods for traversing a tree. In DFS traverse, you basically start at the root of the tree and then explore as far as the end of the branch, then you backtrack to traverse each subsequent parent node and start traversing through its other children.
You are correct in thinking DFS as one of the ways of Backtracking; Backtracking is just a generalized term for DFS.
Generally, Backtracking is useful for finding a specific path. When I say path, I mean try-and-error methods when finding this particular path. This path can expect just a straight “path” or some variations to the path like getting a specific target sum or finding out specific patterns.
There are some interesting examples I would like to share, which utilizes Backtracking, and some of the algorithms develop itself to employ DFS as well. For all the examples below, there are tests written for them inside the same directory. Make sure to check them out to fully understand the problems.
1. Word Search
Here is one of my favourite algorithm. When you have a 2D array like this:
array =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
You need to find whether there is a path to a given string. For example, when a string “ABCESE” given, the algorithm should return “true” because there is a path on the board for this string, A->B->C->E->S->E. For the “false” case, we can go with “ABFE” because none of the characters in the board satisfies the exact A->B->F->E.
It is one of a typical DFS problem which has a bit of Backtracking involved. You go through every possible character in the matrix to find if we can come up with the provided string. Once we have a match, we found it, return true!
Below is the code written in Python:
2. Sudoku Solver
Solve Sudoku.
You probably already know how the game plays out, if unsure, please refer to here
When I first encountered this problem, it gave me a headache as it seemed too complicated to write an algorithm for it. However, as I gazed at the problem, contemplating various ways to solve the problems, the word Backtracking suddenly hit me!
The algorithm tries again and again, very rigorously until we have a filled board with a set of validations passed.
Honestly, writing an algorithm to solve Sudoku can indeed be confusing. It gave me a lot of headaches because we aren’t sure where we should even begin.
First, we should generalize our thoughts in our head as much as possible. It is then probably a good idea to start by thinking about how we are going to validate the board like a row-wise, col-wise, 3x3 board with unique 1-9. With this validation in mind, we can keep trying to fill a number from 1-9 in the empty spot as we go until we have a full, complete and valid board. When the validation fails, we reset (backtrack) the row/col to what it was before and try a new number again.
Below is the code written in Python:
3. Combination Sum
Here we are given with an array. We are relentlessly trying to find all sum of numbers in an array which sums up to a target number provided.
For example, let’s say that we have [2,3,7] as a provided array and target is 7. We need to find any combinations of numbers (numbers can be repeating itself to create the sum. So for the above example, we have [2,2,3] and [7] as our answers.
You should think about how these numbers get repeated themselves to make up for the sum. Luckily, we have a good base case here. We stop and add the combination when we have the target met. Sorting happens in the beginning so the algorithm can bail out early when the condition isn’t satisfied.
But how do we know when the target is met? We can subtract the encountered numbers from the original target until we have exact “zero.” If we do not have the condition we want, we want to add the number back so the algorithm can continue its search.
Below is the code written in Python:
4. Permutation
As you have seen in previous examples, it is common to use the technique called Backtracking for combination or permutation. Then we can variate the technique (Backtracking/DFS) to meet the condition as needed.
Permutation can be confusing, especially when there are multiple of the same numbers (instances). When you think of a permutation, you need to remember its exact position and think of it as a distinct entity.
Check this code example in Python. There are 2 similar functions in there but serves a different purpose. One shows all possible positions of an array and the other one does not include the duplicated items.
The algorithm is showing how it uses DFS to reach to the base case, which gathers all possible outcome. It tries each of the different places in digits to find all distinct possible output. I also added the unique case, so it does not further recurse when algorithm already witnessed number.
Without the uniqueness, it is unique per position. So for “12321” case, we have 1 at index 0, 2 at index 1, etc. Now if we swap the positions, so they are represented as 12321, there are 4 different ways to to represent this “12321” because we can swap between 1s and 2s to make it as the same number. Please look at the test case for the permutation algorithm. It will make a whole lot more sense.
Code written in Python:
5. Lottery numbers in a sequence of a number
Requirement: You are trying to find a sequence of numbers (ex lottery) meeting the following criteria:
- The digits must form 7 unique numbers between 1 and 59
- Digits must be used in the order meaning that you cannot build a number using digit n and digit n + 10, for example. Ex: In 12345678, you can’t use 1 and 3 to get 13
- Every digit must be used precisely once meaning that you cannot use one digit as a part of two different numbers. Ex: In 1234567, you can’t get 12 23 3 4 5 6 7 as it uses the digit ‘2’ in both ‘12’ and ‘23’
- All of the digits must be used. Ex: If the sequence is 12345679, 1 2 3 4 5 6 7 cannot be valid as the final digit 9 hasn’t been used
Sample input:
- 569815571556
4938532894754
1234567
472844278465445
0123456
Sample output:
4938532894754 -> 49 38 53 28 9 47 54
1234567 -> 1 2 3 4 5 6 7When I encountered this problem, I thought it was pretty easy. After trying different methods for about an hour, I still couldn’t produce any fruitful code for an hour or two. I had lots of different ideas about how to go about solving it, but the right algorithm wasn’t just popping in my head. Then I struggled even more as I was heading in the wrong direction to solve the problem. I eventually gave up.
When I was trying to go to bed one night, the solution just clicked through my mind. It turns out this problem was just another backtracking problem! I got up in the middle of the night, went straight to the computer and started coding the way I pictured. BUT, I failed again. I got stuck because I could not express my thoughts well. Last time I tried, I didn’t even use the IDE, so this time, I decided to solve this problem step by step with the IDE using the debugger. I started noticing how recursion fails when it tries to backtrack.
After rewriting a couple of times, I finally was able to have an algorithm that’s was producing some expected result. The algorithm tries every possible outcome, then aggregates the result when the condition is met.
NOTE: I noticed the solution I wrote is not 100% correct because it doesn’t go through every possibility of spaces in between these numbers. One way to approach this problem is we could try the intrinsic method to solve the problem. We could generate every possibility of adding a space in between the numbers (1 and 2 number pos) and see if they can form a number meeting above conditions. To do this means rewriting the current algorithm, which shows the idea of generating every possibility, which is the key here.
Below is the code written in Python.
Conclusion
We just went through 5 examples above, where they employ Backtracking technique, and some have a bit of taste in DFS. If you look at the problem alone, it can be daunting and puzzling. However, if you think about the idea of Backtracking alone, it is quite simple. It tries to go through all possibilities and see if they would work. If not, step back and try more possibilities. Common classic examples include eight queens puzzle or knapsack problem. I would recommend you read through some of these classic examples to understand the algorithm better. It might not be the best solution, or it might be the only solution. There are seldom no short-cuts available. We have to go through all the possibilities!
