Every so often during our software development endeavors we might face situations where the solution(s) can be found easily or the job can be done quickly using typical well-known algorithms that can be implemented routinely. This is the first part of a multi-segment series on programming techniques where we briefly present algorithm methods one by one. This time we are going to cover backtracking.
The Backtracking Algorithm Technique - The Theory (Page 2 of 4 )
The definition of backtracking in computer science is closely related to the brute-force search technique. Brute-force search is a general problem-solving technique that finds the solution trivially by systematically enumerating all of the possible candidates and then checking whether each of them meet the required criteria. Backtracking is a polished and smoother version of this. Usually, it's not that na´ve.
Rather than just enlisting all of the possible candidates, backtracking enumerates just the really possible ones that already satisfy some of the properties of the problem; this can be built on to find the final answer moving forward. Therefore, it begins searching for the solution, and if it can't find anything going "one way" then it will "backtrack" and try another combination(s).
In the end it finds the final valid solution(s) because, practically, it is going to try each possibility. In a nutshell, that's why it is called backtracking. I'm sure you are familiar with the concept of trees from computer science. You see, the backtracking algorithms picks the first path and tries to go into its depth, searching for the solution; if it fails, then it steps backwards and picks the next path (another alternative), and so on.
As a result, we can conclude that in the end the outcome is a resulting vector that contains the solutions. Backtracking solves problems that can be narrowed down to finding some sort of Descartes multiplication of N elements in series, which can be combined to satisfy some strict inner constraints between each other. It's our job as coders to analyze how we can "re-phrase" the problem to some sort of series.
It means that we must "code" the solution into a vector. It is also our job to identify the source elements of series from which we're going to build the possible paths of that so-called tree, or just a simple vector where we are moving forward trying to combine the elements from the source array, and on each failure taking one step backwards and trying the next alternative. We do this until a valid solution is found.
Let's reiterate that analogy with the tree. The tree is going to have each path built up from the A1 x A2 x ... x An Descartes-multiplication of the source series. A1, A2, ..., An are all arrays from which we can generate all of the possible candidates. From the A1 array we can pick N1 elements, from the A2 we can choose N2 and so on. This means that the x-nth level of the tree will have Nx nodes since that's the maximum count of combinations that we can try from the Ax array to find a solution.
What about the solution? Continuing our tree-like analogy, the solution in the end can be found from a valid path/route (from the root node until a leaf). All that is left to do after this stage is to decode those elements the way we simplified our problem to formulate a valid answer. This is optional because, with classic permutation, combination, variation, and etc. problems we work directly with numbers.
Let's clarify some standards regarding backtracking. I'm going to use the vector X as the solution-vector. All of the possible candidates will be picked from the arrays A1, A2, ..., and An. We will use a recursive strategy to accomplish the scenario of stepping backwards. We're going to use the variable k to refer to the k-nth level of the tree containing elements combined until the Ak arrays. Check out the following sketch.
The above diagram will make sense when you arrive on the next page. It is the internal exemplification of the solution vector, which we call X, during a backtracking algorithm on a particular problem ("Puzzle of N Queens" run on a 4 x 4 chess board). What's really important is the fact that all of the possible candidates are picked out of those Ak arrays, though, in this problem all of them can be the numbers 1-4. As soon as no possible candidates are left, the algorithm steps back (arrow down).
As you can see, the X solution vector is supposed to behave like a stack. We're going to push and pop elements into/from it. We begin from the root node and then examine each node of its children. From these nodes we analyze whether or not they are leading to a potential further candidate; if yes, then we'll push it into the stack, move further with one level, and so on. If none of the nodes looks "good" on that specific level, then we pop it from the stack, and try the next possible alternative.
That covers the theory. Let's see the classic problem called the "Puzzle of N Queens" and a real-world applicable backtracking algorithm in both pseudo-code and ANSI C that solves the problem. It's a prime example of backtracking that exemplifies this algorithm in action. It can also be modified into lots of other problems.