How does one formulate a backtracking algorithm

Question

I am new to learning algorithms. I was reading backtracking algorithm for generating all strings for n bits. If I dry run the program I know the program is giving right result. But I didn't understood the logic can anybody please explain? What I mean is what will be be the thought process to arrive at this solution

void binary(int n)
{
    if(n < 1)
        printf("%s\n",A);    // Assume A is a global variable
    else
    {
        A[n-1] = '0';
        binary(n-1);
        A[n-1] = '1';
        binary(n-1);
    }
}

Answer 1

This answer begins with a first section explaining the problem in more general terms. The direct answer to the question for the example given by the OP is then given in a second section that illustrate the discussion in the first.

You may well want to skip the first section and go direcly to the second one, depending on whether you like to start with basic principles or with the analysis of an example.

The principles : non-deterministic programming

My description is not intended for this algorithm only, but is more a general way to design such algorithms.

The key idea is that backtracking is a technique to implement non-determinism with depth-first exploration of the non-deterministic space of possibilities.

Non-determinism allows you to separate the logic of the problem from the non-deterministic exploration of the solution space. It makes programs clearer, simplifies analysis and proofs of properties. This is pretty much the same advantage that you get when using non-determinism in Automata Theory, to simplify the design of automata performing a given calculation. Non-determinism makes your technical life much easier.

This advantage is such that various programming experts and language designers have analyzed or experimented with the introduction of a standard non-deterministic functionality in various programming languages, not to mention the language Prolog where non-determinism is a central control feature.

Another advantage of using non-determinism is that it leave open the implementation technique, that can also use breadth first exploration, or even dynamic programming (to avoid repeating calculations). And the handling of non-determinism, such as adding the backtrack control, is done entirely by the compiler.

An interesting side-point is that BNF, the language of context-free grammars, can be seen as a simple non-deterministic programming language to write parsers. And you can compile it fairly simply into a depth-first parser (some early ones were just that - Ned Irons, 1961), or a breadth-first one, or a dynamic-programming one (CYK, Earley, and some others).

However, backtracking requires mastering the state of the environment. Without going into details, it is much easier to implement it in a purely functional programming language that has no side-effects (for example, no assignment to global variables), at least not in the parts of programs that use non-determinism.

This is not in contradiction with the use of the global variable A below, which is never read, except to collect the answers.

But it explains why I insist on starting with a recursive non-deterministic program, rather than with an equivalent iterative variant.

What is described below could well be done automatically by the compiler of a non-deterministic language.

Description of the design for the given example

Here is how I would explain the design of this algorithm.

You consider an array A of bits where the permutation is stored before printing. It can be a global variable.

First you write a non-deterministic algorithm, that will just produce one permutation, a "random" one, chosen by the god of non-determinism :)

This is a simple recursive procedure that ask the god's oracle choose for each bit in succession. The choose oracle return non-deterministically one of its arguments (here the word oracle is used in its mythological sense, not in the usual sense of computability theory). Using recursion is important, as I shall explain later.

void binary(int n)
{
    if(n < 0)
        printf("%s\n",A);    // Assume A is a global variable
    else
    {
        A[n-1]= choose('0','1')
        binary(n-1);
    }
}

You should agree that this algorithm will return one of the permutation, anyone of them. You could organize the recursion differently, it does not really matter. All that matters is that you may follow any of the possible computations.

What you have done with this program is to prepare for all choices that will make a permutation.

Then, instead of making one choice non deterministically, you simply try them all, one after the other, for each of the calls.

Since you have a list of the possible choices (there can be a variable number of them), you just try them in succession. You can do that by having a segment of code for each possible value. But when the possible values are in a list of variable length, you can just loop over that list.

Here you have just 2 values, so you just write twice the same code, once for each of the values, so that:

        A[n-1]= choose('0','1')
        binary(n-1);

becomes

        A[n-1]= '0'
        binary(n-1);
        A[n-1]= '1'
        binary(n-1);

The first call to binary will produce all permutations with '0' in position n and the second all permutations with '1'.

Instead of choising arbitrarily, you do one, then the other.

There is an invisible trick that helps you. This would be somewhat harder if you had used an iteration rather than a recursion.

The reason is that, for each former call to choose, you have to come back to it after trying all possibilities of later choices, and you have to remember what are the choices you have not tried yet.

This is very easily handled by returns of the recursive call, where you find the environment and the execution point where you left it, so that you simply go on.

If you had used an iteration, you would have a beautiful mess managing the data to recall how far you have dealt with each non-deterministic choice.

You could have started with a very simple loop, that is also a non-deterministic way of computing a single permutation.

void binary(int n)
{
    for (i=n-1; i=0; i--) {
        A[i]= choose('0','1')
    }
    printf("%s\n",A);
}

But transforming this program into a deterministic backtracking program would be a lot harder.

Isolating each non-deterministic choice in a function makes your life easy.

There is an old classical paper that talks of non-deterministic algorithms, though I have not looked at it in a very long time, and I have no memory of how it handles the problem. People were not using recursion as much in those times. You may want to look at it. Bob Floyd was one of the pioneers of computer science.

Non-deterministic algorithms, Robert W. Floyd, 1966.

I do not recall where it was published, but it is easy enough to find.

Note: _{The previous version of the answer was assuming arrays are indexed from 1 to n. I changed that as it may put off users who recognize the code as C code. The site is normally language agnostic. The program given in the question is missing both A[0] and A[n].}

Answer 2

The idea here is to implement the following recursive definition of the set $A_n$ of all binary strings of length $n$: $$ A_0 = \{\epsilon\}, \qquad A_n = \{x0 : x \in A_{n-1}\} \cup \{x1 : x \in A_{n-1}\}. $$ Here $\epsilon$ is the empty string. You can also start at $A_1 = \{0,1\}$, but your program actually has $0$ as a base case. Starting with this recursive definition, it is routine to convert it to your recursive procedure.

To make sure that you understand this, I recommend the following exercise. Try to implement the following slightly different recursive definition: $$ B_0 = \{\epsilon\}, \qquad B_n = \{0x : x \in B_{n-1}\} \cup \{1x : x \in B_{n-1}\}. $$

---

Languages like python which support generators natively make this even easier. Here is code that generates all binary strings of length $n$, based on the recursions above:

def A(n):
    if n == 0: yield ''
    for x in A(n-1): yield x + '0'
    for x in A(n-1): yield x + '1'

def B(n):
    if n == 0: yield ''
    for x in B(n-1): yield '0' + x
    for x in B(n-1): yield '1' + x

Python also makes it easy to implement these recursions slightly differently:

def C(n):
    if n == 0: yield ''
    for x in C(n-1):
        yield x + '0'
        yield x + '1'

def D(n):
    if n == 0: yield ''
    for x in D(n-1):
        yield '0' + x
        yield '1' + x

Can you tell what is the connection between the orders generated by A,B,C,D?