Backtracking Method

Introduction

The backtracking method can be applied to solving problems that meet the following conditions:
- The solution can be represented by an array x[]=(x[1], x[2], ..., x[n]), where each element x[i] belongs to a known set Ai;
- each set Ai is finite, and its elements are in a specified order relationship – often the n sets are identical;
- Either all solutions to the problem are required, or a specific solution is needed that cannot be determined by any other (typically faster) method.

The backtracking algorithm constructs the array x[] (called the solution vector) as follows:
- At each step k, starting (typically) from step 1, the current element x[k] of the solution vector is processed:
- x[k] sequentially receives values from the corresponding set Ak;

At each step, it is checked whether the current configuration of the solution vector can lead to a final solution – if the value of x[k] is correct in relation to x[1], x[2], … x[k-1]: if the value is incorrect, the current element X[k] receives the next value from Ak or we backtrack to the previous element x[k-1], if X[k] has received all values from Ak – step back; if the value of x[k] is correct (we have a partial solution), the existence of a final solution to the problem is checked: if the current configuration of the solution vector x epresents a final solution (typically) we display it; if no final solution is identified, we move to the next element, x[k+1], and resume the process for this element – step forward. As it is constructed, the solution vector x[] represents a partial solution to the problem. When the solution vector is completely constructed, we have a final solution to the problem.

Solved problems

Problem 1
A word consisting of a maximum of 10 distinct lowercase letters is read. Display in lexicographical order all the anagrams of the read word that have the property that they do not contain two adjacent vowels or two adjacent consonants (practically, vowels and consonants must alternate). If this is not possible, the message IMPOSSIBLE will be displayed. Exemple: if s="cosmina" the anagrams are: caminos camison camonis ... sonimac if s="cosmin" it shows IMPOSSIBLE

Solution

     
#include  < iostream>
    #include < cstring>
    #include < cstdlib>
    using namespace std;
    int n,X[12],P[12];
    char s[12];
    
    void afisare()
    {
        for(int i=1;i<=n;i++)
            cout<<s[X[i]-1];
        cout<< endl;
    }
    
    int valid(int k)
    {
        if(k>1) 
        {
            if(strchr("aeiou",s[X[k]-1])==0 &&
               strchr("aeiou",s[X[k-1]-1])==0)
                return 0; 
            if(strchr("aeiou",s[X[k]-1])!=0 &&
               strchr("aeiou",s[X[k-1]-1])!=0)
                return 0; //
        }
        return 1;
    }
    
    void back(int k)
    {
        for(int i=1;i<=n;i++)
            if(!P[i])
            {
                P[i]=1;
                X[k]=i;
                if(valid(k))
                    if(k==n) afisare();
                    else back(k+1);
                P[i]=0;
            }
    }
    
    void ordonare(char s[])
    {
        int l=strlen(s);
        for(int i=0;i<l;i++)
            for(int j=i+1;j<l;j++)
                if(s[i]>s[j])
                {
                    char aux=s[i];
                    s[i]=s[j];
                    s[j]=aux;
                }
    }
    
    int main()
    {
        cin>>s;
        n=strlen(s);
        int cv=0,cc=0;
        for(int i=0;i<n;i++)
            if(strchr("aeiou",s[i])==0) cc++;
            else cv++;//numaram vocalele
        if(abs(cc-cv)>1) cout<<"IMPOSIBIL";
        else
        {
            ordonare(s);
            back(1);
        }
        return 0;
    }  
    

Problem 2

The natural numbers n,a,b,p,q are read (n<=20, a<=b<=n, p<=q) and then n different scores of some questions. To display all the ways in which a number of questions between a and b can be chosen for a test and have a total score between p and q.

Exemple:
7 4 5 20 25
6
5
7
8
2
3
10
will be displayed
6 5 7 2
6 5 7 2 3
6 5 7 3
6 5 8 2
6 5 8 2 3
....
8 2 3 10
               

Solution
    #include < fstream>
        using namespace std;
        ifstream fin("i.in");
        ofstream fout("i.out");
        
        int X[21],Q[21],n,a,b,p,q;
        
        void display(int k)
        {
            for(int i=1;i<=k;i++)
                fout<<Q[X[i]]<<" ";
            fout<<endl;
        }
        
        void back(int k, int pp)
        {
            for(int i=X[k-1]+1;i<=n;i++)
                {
                    X[k]=i;
                    pp=pp+Q[X[k]];
                    if(pp<=q)
                    {
                        if(k>=a && k<=b && pp>=p) display(k);
                        back(k+1,pp);
                    }
                    pp=pp-Q[X[k]];
                }
        }
        
        int main()
        {
            fin>>n>>a>>b>>p>>q;
            for(int i=1;i<=n;i++)
                fin>>Q[i];
            back(1,0);
            return 0;
        }

Practice exercises

1) Display in alphabetical order the anagrams of a word made up of distinct letters.

Exemple:
    date.in
    rac
    date.out
    acr
    arc
    car
    cra
    rac
    rca

2) A natural number n is read. Generate and display all combinations of bits in binary digits that do not have two 1's next to them.

Exemple:
    n=3
    the combinations are:
    0 0 0
    0 0 1
    0 1 0
    1 0 0
    1 0 1

3) One reads a natural number n and then a set with n natural number elements. Using permutations of elements generate and display the permutations of the read set.

4) Two natural numbers n and k are read, k being smaller than the number of digits of the number n. Display the largest number that can be formed by removing k digits from the number n.

Exemple:
    n=3452234
    k=4
    the number is 534

5) Two natural numbers n and k are read. Generate and display all natural numbers consisting of n digits that contain exactly k digits of 1.