A way to learn the backtracking method

prof. Doru Popescu Anastasiu

In memory of Tudor Sorin.

Summary
About 16 years ago, Tudor Sorin proposed to the IT world in Romania
a poem of materials that standardized the backtracking method. This led to
creating a template through which a method could be used by both students,
students, teachers. I will continue to present this programming method as a
natural continuation of the chapter "Recursion" from the 10th grade, mathematics profile
computer science, intensive computer science.

Introduction
Many teachers conclude the chapter on recursion with problems of the type:

Given a natural number n<20 and an alphabet with two letters (A={a,b}). Determine all
the words of letters using the given alphabet.
Example
[Link] [Link]
2 aa
ab
ba
bb
The solution to the problem is as follows:

A word can be stored in a vector with char type components (each

component can have one of the values 'a', 'b'). Recursively, words can
determine using the following program:
var x: array[0..21] of char; #include <fstream.h>
n:integer;
char x[21];
f:text;
int n;
ofstream fout("[Link]");
display procedure;
var i:integer; void display() {
begin int i;
for i:=1 to n do for(i=1;i<=n;i++)
write(f,x[i]); cout << x[i];
writeln(f);;
end; }
procedure generate(k: integer); void generate(int k){
begin if(k==n+1)
if k=n+1 then display();
display else
else {
begin a
x[k]:='a'; generate(k+1);
generate(k+1); x[k]='b';
x[k]:='b'; generate(k+1);
generate(k+1); }
end }
end;
int main() {
begin ifstream fin("[Link]");
assign(f,'[Link]'); fin>>n;
reset(f); [Link]();
read(f,n); generate(1);
close(f); [Link]();
assign(f,'[Link]'); return 0;
rewrite(f); }
generate(1);
close(f)
end.

For the given example in the statement, the call sequence is as follows:

generate(1)è generate(2)à generate(3)

a x[2]='a'
the generation is stopped by the condition k=n+1 and
is displayed
ß
b
à generate(3)
the generation is stopped by the condition k=n+1 and
it is displayed
x[1]='b'ß ß
è generate(2)à generate(3)
a
the generation is stopped by the condition k=n+1 and
it is displayed
ß
b
à generate(3)
the generation is stopped by the condition k=n+1 and
it is displayed
stop ß ß
This results in the following tree, with the evolution of the vector x:

x=()

x=('a') x=('b')

x=(‘a’,’a’) x=( ‘a’,’b’) x=( ‘b’,’a’) x=('b','b')

Generalizations

We continue to raise the issue of how we can determine the words that use a
larger alphabet (for example, with the first letters from the English alphabet). Moreover, how
we determine the words that fulfill a certain property (for example: not to have
two identical letters in consecutive positions) etc.

If we focus on the issue of determining words, using the first letters from
the English alphabet with the restriction: there should be no equal letters in consecutive positions, a variant of
a subprogram that generates the vector x could be:

procedure generate(k:integer); void generate(int k){

var i: integer; int i;
begin if(k==n+1)
if k=n+1 then display();
display else
else for(i=1;i<=m;i++)
for i:=1 to m do {
begin x[k]='a'+i-1;
x[k]:=chr(ord('a')+i-1); generate(k+1);
generate(k+1) }
end }
end;

We mention that, in the display function, it will be checked that there are no two
equal letters in consecutive positions, displayed only in this case.

Under these conditions for n=2 and m=2, the same tree as above is generated. Some of
branches being generated for no reason, because once two components with indices are built
consecutive and the same letter, it surely will not reach a word to be displayed. Thus
to optimize the generation algorithm, it is necessary to add a condition to each
not (related to the choice of value for component x[k], that is, x[k]≠x[k-1]).

We obtain the refinement as follows:

procedure generate(k: integer); void generate(int k){
var i:integer; int i;
begin if(k==n+1)
if k=n+1 then display();
display else
else for(i=1;i<=m;i++)
for i:=1 to m do {
begin x[k] = 'a' + i - 1;
x[k] := chr(ord('a') + i - 1); if(condition(k))
if condition(k) then generate(k+1);
generate(k+1) }
end }
end

The condition function returns true/1 or false/0 depending on the situation (if x[k]≠x[k-1],
respectively x[k]=x[k-1]). In order to avoid a particular case k=1, before the call
generate(1) initializes x[0] with a character that is not in the alphabet (of
example x[0]='*').

Transition to the backtracking method

Using the previous considerations, we can discuss the solution to a problem.

general.

The backtracking method allows solving problems of the type:

Given n sets A1A2, ..., An and a property P, which depends on x1, x2, ..., xn(x1DIN A1,
x2 DIN A2, ..., xnsize AnIt is required to determine all the sequences x1, x2, ..., xtranslatedText, who checks
property P.

Specification
For the problem of generating words where the letters in consecutive positions are
distinct, we have:

A1, A2, ..., An they are all formats from the first m lowercase letters of the English alphabet.
P is the condition xinotequaltoxi-1in the set {2, 3, …, n}.

Description of the solution method (called backtracking due to the generation mechanism)
the solutions)

The construction of the components of vector x will be done in ascending order of the indices, x1,
x2, ..., xk, ..., x. xk being from the set Ak.

From condition P, partial conditions are deduced for the components x.1, x2, ..., xkThese
they will be noted with P(k).

The idea of the method is that if, at a given point, it is necessary to construct xk, themselves
consider the elements of A one by onekand if the conditions P(k) are verified, then we proceed
the following component, otherwise it goes back to the previous component and is searched for
another value. There is constantly a "going and coming" (created by the mechanism of recursiveness)
until a solution is reached.
The general form of a recursive subprogram for generating the vector x is presented in
continue.
procedure back(k:integer); void back(int k){
var i:Tip; Tip i;
begin if(k==n+1)
if k=n+1 then display();
display else
else for(i in Ak)
for I in Akdo {
begin x[k]=i;
x[k]:=i; if(P(k))
if P(k) then back(k+1);
back(k+1) }
end }
end

- The generation subprogram must be called using back(1) to construct the vector x
starting with the first component.

Observations
The backtracking method determines all solutions to the problem.
The more restrictive the partial conditions P(k) are, the longer the execution time is.
mic.
Sometimes it is preferable to use in its components x, the indices of the elements from
set A1A2, ..., Abecause these are consecutive numbers and can be traversed more
easy.
The execution time of algorithms that use the backtracking method is exponential.
(relative to n).
If there are other methods of resolution with polynomial execution time, then this
the method can be used only to confirm the correctness of the other, by comparing
results.
To master this programming method, it is necessary to solve a number
a lot of problems, starting with the classic ones (the n-queens problem, coloring a map,
generation of combinatorial elements, payment of a sum of money, etc.), then continuing with
those that require modifications to the generation subprocess.
The backtracking method can also be used for generating chains in arrays.
two-dimensional (so-called backtracking in plan) but for this variant it should
write another material.

Proposed problems
1. A set A is given with n (n<20) elements of natural numbers <32000. It is required to
determine all the ways to divide A into three sets with the same sum
elements.
Example
[Link] [Link]
9 {7 3 6 4} {2 8 10} {11 9}
2 8 7 11 6 4 9 3 10 ...
2. A sequence with n (n<50) elements of natural numbers <100 is given. It is requested to determine all
numbers from a sequence that can be written as a sum of distinct prime numbers.
Example
[Link] [Link]
3 7 10
6 7 10

3. Given a natural number (n<20). Determine all the numbers in base 2 with n digits, which have
the number of digit 1 is equal to that of digit 0.
Example
[Link] [Link]
4 1100
1010
1001

4. A sequence with n (n<20) elements is given, distinct natural numbers <200. It is required to do ...
determine the smallest natural number that cannot be written as a sum of terms from the sequence
that.
Example
[Link] [Link]
4 8
1 2 4 10

5. Given a sequence with n (n<20) elements, distinct natural numbers <200. It is required to
determine all the longest increasing subsequences of the given sequence.
Example
[Link] [Link]
7 359
8359234 234

6. Given a sequence of n (n<20) elements, integers with absolute value <200. It is required
to determine all the values of the arithmetic expressions that can be obtained by placing between any
two neighboring numbers using the operator + or -.
Example
[Link] [Link] Explanation
3 8 2+8+(-2)
2 8 -2 12 2 + 8 - (-2)
-8 -8
-4 2 - 8 - (-2)