Backtracking

Minh Ngo

1 Definitions
Definition 1. Backtracking is an algorithm based on recursion. A backtracking algorithm tries to construct all
possible solutions to a problem. It will a solution to a computational problem incrementally, one small piece at a
time.
Backtracking can also use to find the best solution. Whenever the algorithm needs to decide between multiple
alternatives to the next component of the solution, it recursively evaluates every alternative and then chooses the
best one.
Here, we have pseudocode for a typical backtracking algorithm that will list all solutions.

Algorithm 1 Backtracking to list all solutions

1: procedure Try(i)
2: for every possible values v for xi do
3: xi ← v
4: if xi is the last element in the solution then
5: print the solution
6: else
7: Record that xi ← v (if need)
8: Try(i + 1) ▷ Recurse
9: Cancel the record of xi ← v (if need)
10: end if
11: end for
12: end procedure

1
Algorithm 2 Backtracking to find best solution
1: procedure Init
2: Initialize best solution BEST
3: end procedure
4:
5: procedure Try(i)
6: for every possible values v for xi do
7: xi ← v
8: if We might be able to find a better solution then
9: if xi is the last element in the solution then
10: Update BEST
11: else
12: Record that xi ← v (if need)
13: Try(i + 1) ▷ Recurse
14: Cancel the record of xi ← v (if need)
15: end if
16: end if
17: end for
18: end procedure
19:
20: Init
21: Try(1)
22: Return BEST

Backtracking works in an incremental way to attack problems. Typically, we start from an empty solution array
and one by one add items. When we add an item, we check if adding the current item violates the problem constraint,
if it does then we remove the item and try other alternatives. If none of the alternatives work out then we go to
previous stage and remove the item added in the previous stage. If we reach the initial stage back then we say that
no solution exists. If adding an item doesn’t violate constraints then we recursively add items one by one. If the
solution array becomes complete then we print the solution.

2 Examples
2.1 Listing all binary numbers
We need to print all binary numbers of length n. We will list all these numbers by assigning for each xi a value in
{0, 1}. For each value we assign for xi , we try possible values for xi+1 . Here is the pseudocode

Algorithm 3 List all binary numbers

1: procedure Try(i)
2: for v = 0, 1 do
3: xi ← v
4: if i = n − 1 then
5: print x0 x1 . . . xn−1
6: else
7: Try(i + 1) ▷ Recurse
8: end if
9: end for
10: end procedure

An implementation in C.
# include < stdio .h >

int n ;
int x [100];

2
void Try ( int i ) {
for ( int v = 0; v <= 1; v ++) {
x[i] = v;
if ( i == n - 1) {
for ( int j = 0; j < n ; j ++) printf ( " % d " , x [ j ]) ;
printf ( " \ n " ) ;
}
else Try ( i + 1) ;
}
}

int main () {
scanf ( " % d " , & n ) ;
Try (0) ;
}

An implementation in Python.
n = int ( input () )
x = [0] * n

def Try ( i ) :
for v in range (2) :
x[i] = v
if i == n - 1:
print (* x )
else :
Try ( i + 1)

Try (0)

Note that a modification of this algorithm allows us to list all the subset of a set S of size n. Imagine that for
each subset X ⊂ S, if ai ∈ X, the digit xi will be 1 and 0 otherwise. So the problem of listing all the subsets boil
down to listing all binary numbers. Here is an implementation in C that list all the subsets of a set of size n.
# include < stdio .h >

int a [100];
int x [100];
int n ;

void print_sol () {
for ( int i = 0; i < n ; i ++) {
if ( x [ i ]) printf ( " % d " , a [ i ]) ;
}
printf ( " \ n " ) ;
}

void Try ( int i ) {

for ( int v = 0; v < 2; v ++) {
x[i] = v;
if ( i == n - 1) {
print_sol () ;
}
else Try ( i + 1) ;
x [ i ] = 0;
}
}

int main () {
scanf ( " % d " , & n ) ;
for ( int i = 0; i < n ; i ++) scanf ( " % d " , & a [ i ]) ;
Try (0) ;
}

With the above implementation, if add a checking condition in the print solution function to calculate the sum
of the subset and only output the subset with sum of given target, we solved the subset sum problem.

2.2 Listing all permutations of length n

We need to print all permutations of {1, 2, 3, . . . , n}. We will assign for each xi a value v in {1, 2, . . . , n} if it was
not already assigned for any position before i (i.e. not marked). Then, we for each value assigned for xi , we try all
possible values for xi+1 . Here is the pseudocode.

3
Algorithm 4 List all permutations of length n
1: procedure Try(i)
2: for v = 1, 2, . . . , 9 do
3: if v was not assigned then
4: xi ← v
5: Mark v as assigned
6: if i = n − 1 then
7: print x0 x1 . . . xn−1
8: else
9: Try(i + 1) ▷ Recurse
10: Mark v as not assigned
11: end if
12: end if
13: end for
14: end procedure

An implementation in C.
# include < stdio .h >

int n ;
int x [100];
int assigned [100];

void Try ( int i ) {

for ( int v = 1; v <= n ; v ++) {
if (! assigned [ v ]) {
x[i] = v;
assigned [ v ] = 1;
if ( i == n - 1) {
for ( int j = 0; j < n ; j ++) printf ( " % d " , x [ j ]) ;
printf ( " \ n " ) ;
}
else Try ( i + 1) ;
assigned [ v ] = 0;
}
}
}

int main () {
scanf ( " % d " , & n ) ;
Try (0) ;
}

An implementation in Python.
n = int ( input () )
x = [0] * n
assigned = [ False ] * ( n + 1)

def Try ( i ) :
for v in range (1 , n + 1) :
if not assigned [ v ]:
x[i] = v
assigned [ v ] = True
if i == n - 1: print (* x )
else : Try ( i + 1)
assigned [ v ] = False

Try (0)

2.3 Listing all arrangements of length k

Now we list all arrangements of length k of the set {1, 2, . . . , n} (k ≤ n). The algorithm is actually same with the
case of permutation, the only difference is that now when i = k − 1, we will print the configuration.

4
Algorithm 5 List all permutations of length n
1: procedure Try(i)
2: for v = 1, 2, . . . , 9 do
3: if v was not assigned then
4: xi ← v
5: Mark v as assigned
6: if i = k − 1 then
7: print x0 x1 . . . xk−1
8: else
9: Try(i + 1) ▷ Recurse
10: Mark v as not assigned
11: end if
12: end if
13: end for
14: end procedure

An implementation in C.
# include < stdio .h >

int n , k ;
int x [100];
int assigned [100];

void Try ( int i ) {

for ( int v = 1; v <= n ; v ++) {
if (! assigned [ v ]) {
x[i] = v;
assigned [ v ] = 1;
if ( i == k - 1) {
for ( int j = 0; j < k ; j ++) printf ( " % d " , x [ j ]) ;
printf ( " \ n " ) ;
}
else Try ( i + 1) ;
assigned [ v ] = 0;
}
}
}

int main () {
scanf ( " % d % d " , &n , & k ) ;
Try (0) ;
}

An implementation in Python.
n , k = map ( int , input () . split () )
x = [0] * k
assigned = [ False ] * ( n + 1)

def Try ( i ) :
for v in range (1 , n + 1) :
if not assigned [ v ]:
x[i] = v
assigned [ v ] = True
if i == k - 1: print (* x )
else : Try ( i + 1)
assigned [ v ] = False

Try (0)

5
2.4 Lists all subsets of size k
To list all subsets of size k of S = {1, 2, . . . , n}, we can transform our task to listing all the configuration x1 x2 . . . xk
where xi ∈ S and x1 < x2 < . . . < xk . We have this observation:

xk ≤ n
xk−1 ≤ xk − 1 ≤ n − 1
..
.
xi ≤ n − k + i
..
.
x1 ≤ n − k + 1.

Thus, xi−1 + 1 ≤ xi ≤ n − k + i (1 ≤ i ≤ k). We assume x0 = 0. Thus, for each xi , we assign to it values from
xi−1 + 1 to n − k + i until we reach xk and we have our configuration.

Algorithm 6 List all permutations of size k

1: procedure Try(i)
2: for v = xi−1 + 1, . . . , n − k + i do
3: xi ← v
4: if i = k then
5: print x1 x2 . . . xk
6: else
7: Try(i + 1) ▷ Recurse
8: end if
9: end for
10: end procedure

An implementation in C.
# include < stdio .h >

int n , k ;
int x [100];

void Try ( int i ) {

for ( int v = x [ i - 1] + 1; v <= n - k + i ; v ++) {
x[i] = v;
if ( i == k ) {
for ( int j = 1; j <= k ; j ++) printf ( " % d " , x [ j ]) ;
printf ( " \ n " ) ;
}
else Try ( i + 1) ;
}
}

int main () {
scanf ( " % d % d " , &n , & k ) ;
Try (1) ;
}

An implementation in Python.
n , k = map ( int , input () . split () )
x = [0] * ( k + 1)

def Try ( i ) :
for v in range ( x [ i - 1] + 1 , n - k + i + 1) :
x[i] = v
if i == k : print (* x [1:])
else : Try ( i + 1)

Try (1)

6
2.5 List all subset with given sum
Given a set X of positive integers and a target T . Find if there is a subset S ⊂ X such that the sum of elements of
S is equal to T .
When T = 0, then we can immediately return True since the empty set will always satisfy this condition. Else
if T < 0 or T ̸= 0 and S is empty, we can return False.
Now, consider an element x ∈ X. There is a subset that sum to T iff one of the following statement is True:

• There is a subset of X that includes x and whose sum is T .

• There is a subset of X that excludes x and whose sum is T .

so we can call the function recursively on these sets and values.

Algorithm 7 Find if there is subset sum T

1: procedure Try(X, T )
2: if T = 0 then
3: return True
4: else if T < 0 or X = ∅ then
5: return False
6: else
7: for x in X do
8: with ← Try(X \ {x}, T − x) ▷ Recurse
9: wout ← Try(X \ {x}, T ) ▷ Recurse
10: return with ∨ wout
11: end for
12: end if
13: end procedure

Proving this algorithm correct is a straightforward exercise in induction. If T = 0, then the elements of the
empty subset sum to T, so True is the correct output. Otherwise, if T is negative or the set X is empty, then no
subset of X sums to T , so False is the correct output. Otherwise, if there is a subset that sums to T , then either it
contains x or it doesn’t, and the recursion checked this. Done.
An implementation in Python.
val = int ( input () )
s = list ( map ( int , input () . split () ) )
n = len ( s )

def Try (s , n , sm ) :
if sm == 0:
return True
elif n == 0 or sm < 0:
return False
if s [ n - 1] > sm :
return Try (s , n - 1 , sm )
return Try (s , n - 1 , sm ) or (s , n - 1 , sm - s [ n - 1])

print ( ’ Yes ’ if Try (s , n , val ) else ’ No ’)

2.6 List all the ways to write n as sum of positive integers

Given a positive integers n. List all the ways to write n as sum of positive integers. Two ways are considered identical
if they are permutation of each other.
Let x1 , x2 , . . . , xk be a solution to our problem. To avoid the replication, we will add a constraint that xi−1 ≤ xi .
Note that if x1 , x2 , . . . , xk is a solution, then xk = n − (x1 + x2 + . . . + xk−1 ). If we still want to add more number
so our solutions after xk , then we must have xk ≤ xk+1 and x1 + x2 + . . . + xk + xk+1 ≤ n, or (x1 + x2 + . . . +
xk−1 ) + xk + xk+1 ≤ n ⇐⇒ xk + xk+1 ≤ n − (x1 + x2 + . . . + xk−1 ) ⇐⇒ xk ≤ n−(x1j+x22+...+x k
k−1 )
. Now, if we
n−ti−1
denote ti = x1 + x2 + . . . + xi , then the conditions will be much friendlier: xi−1 ≤ xi ≤ 2 . Let x0 = 1 and
t0 = 0.
So, our algorithm do the following steps:

7
 j k
n−ti−1
• Assign values from xi−1 to 2 to xi , then recursively find the next number.

• Let xi = n − ti−1 and print this solution.

Pseudocode for the algorithm.

Algorithm 8 List all the ways to write n as sum of positive integers

1: procedure Try(i) j k
2: for v = xi−1 , . . . , n−t2i−1 do
3: xi ← v
4: ti ← ti−1 + xi
5: Try(i + 1) ▷ Recurse
6: end for
7: xi ← n − ti−1
8: Print solution
9: end procedure

An implementation in C.
# include < stdio .h >

int n ;
int x [100] , t [100];

void print ( int i ) {

for ( int j = 1; j <= i ; j ++) printf ( " % d " , x [ j ]) ;
printf ( " \ n " ) ;
}

void Try ( int i ) {

for ( int v = x [ i - 1]; v <= ( n - t [ i - 1]) / 2; v ++) {
x[i] = v;
t [ i ] = t [ i - 1] + x [ i ];
Try ( i + 1) ;
}
x [ i ] = n - t [ i - 1];
print ( i ) ;
}

int main () {
scanf ( " % d " , & n ) ;
x [0] = 1; t [0] = 0;
Try (1) ;
}

An implementation in Python.
n = int ( input () )
x = [0] * ( n + 1)
t = [0] * ( n + 1)

def Try ( i ) :
for v in range ( x [ i - 1] , ( n - t [ i - 1]) // 2 + 1) :
x[i] = v
t [ i ] = t [ i - 1] + x [ i ]
Try ( i + 1)
x [ i ] = n - t [ i - 1]
print (* x [1: i +1])

x [0] = 1
t [0] = 0
Try (1)

2.7 N queens problem

Given a n × n chessboard. We want to place n queens on the chessboard, so that no two queens attack each other.
Note that this is impossible for any number of queens greater than n by pigeonhole principle.
We will try to place a queen on each column of the board recursively. For each cell on that column, we check
if there is another queen in that row, in the upper diagonal and the lower diagonal. If there is no queen, then we
place the queen at that cell, and move to the next column. When we reach the last column, then it is a satisfying

8
solution, so we output that solution. Otherwise, it is not a solution, and we go back, remove the queens and place
it in another satisfy position. We model the chessboard as a two dimensional array (bij )n×n , where bij = 1 if there
is a queen at cell (i, j) and 0 otherwise.

Algorithm 9 List all the ways to place n queens on n × n chessboard

1: procedure Check(i, j)
2: if There is a queen on the cells on the left of column j on row i then
3: return False
4: end if
5: if There is a queen on the upper diagonal corresponds to cell (i, j) then
6: return False
7: end if
8: if There is a queen on the lower diagonal corresponds to cell (i, j) then
9: return False
10: end if
11: return True
12: end procedure
13:
14: procedure Try(j)
15: for i = 0, 1, 2, . . . , n do
16: if Check(i, j) then
17: bij ← 1 ▷ Place the queen
18: if j = n − 1 then
19: Output solution
20: else
21: Try(j + 1) ▷ Recurse
22: end if
23: bij ← 0 ▷ Remove the queen
24: end if
25: end for
26: end procedure

An implementation in C.
# include < stdio .h >

int b [100][100];
int n ;

int chk ( int r , int c ) {

for ( int i = 0; i < c ; i ++) {
if ( b [ r ][ i ]) return 0;
}
for ( int i = r , j = c ; i >= 0 && j >= 0; i - - , j - -) {
if ( b [ i ][ j ]) return 0;
}
for ( int i = r , j = c ; i < n && j >= 0; i ++ , j - -) {
if ( b [ i ][ j ]) return 0;
}
return 1;
}

void print () {
for ( int i = 0; i < n ; i ++) {
for ( int j = 0; j < n ; j ++) printf ( " % d " , b [ i ][ j ]) ;
printf ( " \ n " ) ;
}
printf ( " \ n " ) ;
}

void Try ( int j ) {

for ( int i = 0; i < n ; i ++) {
if ( chk (i , j ) ) {
b [ i ][ j ] = 1;
if ( j == n - 1) {
print () ;
}

9
 else Try ( j + 1) ;
b [ i ][ j ] = 0;
}
}
}

int main () {
scanf ( " % d " , & n ) ;
Try (0) ;
}

An implementation in Python.
n = int ( input () )
b = [[0] * n for _ in range ( n ) ]

def chk (r , c ) :
for i in range ( c ) :
if b [ r ][ i ] == 1: return False
for i , j in zip ( range (r , -1 , -1) , range (c , -1 , -1) ) :
if b [ i ][ j ] == 1: return False
for i , j in zip ( range (r , n , 1) , range (c , -1 , -1) ) :
if b [ i ][ j ] == 1: return False
return True

def print_sol () :
for row in b :
print ( ’ ’. join ([ str ( elem ) for elem in row ]) )
print ( ’\ n ’)

def Try ( j ) :
for i in range ( n ) :
if chk (i , j ) :
b [ i ][ j ] = 1
if j == n - 1:
print_sol ()
else : Try ( j + 1)
b [ i ][ j ] = 0

Try (0)

We can further optimize the algorithm above by changing the way we check if a cell is safe. In the above
implementation, we check it by looping over the cells. If you note that the sum of the indices of the cells on the
lower diagonal is a constant and the difference of the indices of the cells on the upper diagonal is also a constant,
we can implement a faster version of this algorithm.
An implementation in C.
# include < stdio .h >

int b [100][100];
int ud [100] , ld [100] , cr [100];
int n ;

void print () {
for ( int i = 0; i < n ; i ++) {
for ( int j = 0; j < n ; j ++) printf ( " % d " , b [ i ][ j ]) ;
printf ( " \ n " ) ;
}
printf ( " \ n " ) ;
}

void Try ( int j ) {

for ( int i = 0; i < n ; i ++) {
if (( ud [ i - j + n - 1] != 1 && ld [ i + j ] != 1 && cr [ i ] != 1) ) {
b [ i ][ j ] = 1;
ud [ i - j + n - 1] = ld [ i + j ] = cr [ i ] = 1;
if ( j == n - 1) {
print () ;
}
else Try ( j + 1) ;
b [ i ][ j ] = 0;
ud [ i - j + n - 1] = ld [ i + j ] = cr [ i ] = 0;
}
}
}

int main () {
scanf ( " % d " , & n ) ;
Try (0) ;
}

10
 An implementation in Python.
n = int ( input () )
b = [[0] * n for _ in range ( n ) ]
ud , ld , cr = [ False ] * (2 * n ) , [ False ] * (2 * n ) , [ False ] * n

def print_sol () :
for row in b :
print ( ’ ’. join ([ str ( elem ) for elem in row ]) )
print ( ’\ n ’)

def Try ( j ) :
for i in range ( n ) :
if ( not ud [ i - j + n - 1]) and ( not ld [ i + j ]) and ( not cr [ i ]) :
b [ i ][ j ] = 1
ud [ i - j + n - 1] , ld [ i + j ] , cr [ i ] = True , True , True
if j == n - 1:
print_sol ()
else : Try ( j + 1)
b [ i ][ j ] = 0
ud [ i - j + n - 1] , ld [ i + j ] , cr [ i ] = False , False , False

Try (0)

2.8 Knight tour problem

Given a n × n chessboard. We place a knight on the first cell of an empty board. We want to find a path for the
knight to visit every cells of the chessboard, according to the rule of chess.
We will build the solutions incrementally. Assume that we are at cell (i, j). We will try all the possible moves,
and if there is a path that allow us to visit all the cell on the chessboard, we will output that path. Here, a solution
will be complete if the number of moves in that path is n2 .

Algorithm 10 Knight tour problem

1: procedure Check(i, j)
2: if (i, j) is still inside the board and hasn’t been visited then
3: return True
4: end if
5: return False
6: end procedure
7: xd[8] = {2, 1, −1, −2, −2, −1, 1, 2}
8: yd[8] = {1, 2, 2, 1, −1, −2, −2, −1}
9: procedure Try(i, j, nmoves)
10: if nmoves = n2 then
11: print this solution
12: end if
13: for k = {0, 1, 2, . . . , 8} do
14: inext ← i + xd[k] ▷ Get the next move of knight
15: jnext ← j + xd[k]
16: if Check(inext , jnext , nmoves + 1) then
17: bij ← nmoves
18: Try(inext , jnext , nmoves + 1) ▷ Recurse
19: bij ← −1
20: end if
21: end for
22: end procedure

An implementation in C.
# include < stdio .h >
# include < string .h >

int b [100][100];
int n;
int xd [8] = {2 , 1 , -1 , -2 , -2 , -1 , 1 , 2};
int yd [8] = {1 , 2 , 2 , 1 , -1 , -2 , -2 , -1};

11
int chk ( int i , int j ) {
if ( i >= 0 && j >= 0 && i < n && j < n && b [ i ][ j ] == -1) return 1;
return 0;
}

void print_sol () {
for ( int i = 0; i < n ; i ++) {
for ( int j = 0; j < n ; j ++) printf ( " % d " , b [ i ][ j ]) ;
printf ( " \ n " ) ;
}
printf ( " \ n " ) ;
}

void Try ( int i , int j , int n_moves ) {

if ( n_moves == n * n ) {
print_sol () ;
}
for ( int k = 0; k < 8; k ++) {
int i_next = i + xd [ k ];
int j_next = j + yd [ k ];
if ( chk ( i_next , j_next ) ) {
b [ i_next ][ j_next ] = n_moves ;
Try ( i_next , j_next , n_moves + 1) ;
b [ i_next ][ j_next ] = -1;
}
}
}

int main () {
scanf ( " % d " , & n ) ;
memset (b , 255 , sizeof ( b ) ) ;
b [0][0] = 0;
Try (0 , 0 , 1) ;
}

An implementation in Python.
n = int ( input () )
b = [[ -1] * n for _ in range ( n ) ]
xd = [2 , 1 , -1 , -2 , -2 , -1 , 1 , 2]
yd = [1 , 2 , 2 , 1 , -1 , -2 , -2 , -1]

def print_sol () :
for row in b :
print ( ’ ’. join ([ str ( elem ) for elem in row ]) )
print ( ’\ n ’)

def chk (i , j ) :
return i >= 0 and j >= 0 and i < n and j < n and b [ i ][ j ] == -1

def Try (i , j , n_moves ) :

if n_moves == n ** 2:
print_sol ()
for k in range (8) :
i_next = i + xd [ k ]
j_next = j + yd [ k ]
if chk ( i_next , j_next ) :
b [ i_next ][ j_next ] = n_moves
Try ( i_next , j_next , n_moves + 1)
b [ i_next ][ j_next ] = -1

b [0][0] = 0
Try (0 , 0 , 1)

2.9 Sudoku solver

The game Sudoku is very famous. The objective is to fill a 9 × 9 grid with digits so that each column, each row,
and each of the nine 3 × 3 subgrids that compose the grid contain all of the digits from 1 to 9. The puzzle setter
may provide a partially completed grid.
It’s hard to solve this puzzle entirely at once, but we can solve it recursively as following: For each cell, we check
all the numbers from 1 to 9 to see if it already appeared in the same row, column and box. If it is not, then we
assign the number to that cell and recursively move to the next cell.

12
Algorithm 11 Sudoku solver
1: procedure Check(i, j, v)
2: if Column jth already has value v then
3: return False
4: end if
5: if Row ith already has value v then
6: return False
7: end if
8: for i ← 3 · ⌊(x − 1)/3⌋ to 3 · ⌊(x − 1)/3⌋ + 3 do
9: for j ← 3 · ⌊(y − 1)/3⌋ to 3 · ⌊(y − 1)/3⌋ + 3 do
10: if b[i, j] = v then
11: return False
12: end if
13: end for
14: end for
15: return True
16: end procedure
17:
18: procedure Try(i, j)
19: if j = 9 then
20: if i = 8 then ▷ Reach final configuration
21: Print this solution
22: else
23: Try(i + 1, 0) ▷ Recurse to next row
24: end if
25: else if b[i, j] = 0 then
26: for v ← 1 to 9 do
27: if Check(i, j, v) then
28: b[i, j] ← v
29: Try(i, j + 1) ▷ Recurse to next cell
30: b[i, j] ← 0
31: end if
32: end for
33: else
34: Try(i, j + 1) ▷ Recurse to next cell
35: end if
36: end procedure

An implementation in C.
# include < stdio .h >

int b [10][10];

int chk ( int r , int c , int val ) {

for ( int i = 0; i < 9; i ++) {
if ( b [ r ][ i ] == val ) return 0;
}
for ( int i = 0; i < 9; i ++) {
if ( b [ i ][ c ] == val ) return 0;
}
for ( int i = 3 * ( r / 3) ; i < 3 * ( r / 3) + 3; i ++) {
for ( int j = 3 * ( c / 3) ; j < 3 * ( c / 3) + 3; j ++) {
if ( b [ i ][ j ] == val ) return 0;
}
}
return 1;
}

void print_sol () {
printf ( " \ n " ) ;
for ( int i = 0; i < 9; i ++) {
for ( int j = 0; j < 9; j ++) printf ( " % d " , b [ i ][ j ]) ;
printf ( " \ n " ) ;

13
 }
printf ( " \ n " ) ;
}

void Try ( int i , int j ) {

if ( j == 9) {
if ( i == 8) print_sol () ;
else Try ( i + 1 , 0) ;
}
else if ( b [ i ][ j ] == 0) {
for ( int v = 1; v <= 9; v ++) {
if ( chk (i , j , v ) ) {
b [ i ][ j ] = v ;
Try (i , j + 1) ;
b [ i ][ j ] = 0;
}
}
}
else Try (i , j + 1) ;
}

int main () {
for ( int i = 0; i < 9; i ++) {
for ( int j = 0; j < 9; j ++) scanf ( " % d " , & b [ i ][ j ]) ;
}
Try (0 , 0) ;
}

An implementation in Python.
b = [[ int ( x ) for x in input () . split () ] for _ in range (9) ]

def chk (r , c , v ) :
for i in range (9) :
if b [ r ][ i ] == v : return False
for i in range (9) :
if b [ i ][ c ] == v : return False
for i in range (3 * ( r // 3) , 3 * ( r // 3) + 3) :
for j in range (3 * ( c // 3) , 3 * ( c // 3) + 3) :
if b [ i ][ j ] == v : return False
return True

def print_sol () :
for row in b :
print ( ’ ’. join ( str ( elem ) for elem in row ) )
print ( ’\ n ’)

def Try (i , j ) :
if j == 9:
if i == 8: print_sol ()
else : Try ( i + 1 , 0)
elif b [ i ][ j ] == 0:
for v in range (1 , 10) :
if chk (i , j , v ) :
b [ i ][ j ] = v
Try (i , j + 1)
b [ i ][ j ] = 0
else : Try (i , j + 1)

Try (0 , 0)

2.10 Longest increasing subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence in that array.
The simplest approach is to try to find all increasing subsequences and then returning the maximum length
of longest increasing subsequence. We can do this recursively. We will have a procedure that return the length of
longest increasing subsequence from current position onward. We consider two cases:

1. The current element is larger than the previous element included in the LIS. In this case, we can include the
current element in the LIS. Thus, we find out the length of the LIS obtained by including it. Further, we also
find out the length of LIS possible by not including the current element in the LIS. The value returned by the
current function call is, thus, the maximum out of the two lengths.

2. The current element is smaller than the previous element included in the LIS. In this case, we can’t include
the current element in the LIS. Thus, we find out only the length of the LIS possible by not including the
current element in the LIS, which is returned by the current function call.

14
Algorithm 12 Longest increasing subsequence
1: procedure Try(prev, curpos)
2: if curpos = n then
3: return 0
4: end if
5: taken ← 0
6: if a[curpos] > prev then
7: taken ← 1+ Try(a[curpos], curpos + 1) ▷ Recurse
8: end if
9: nottaken ← 1+ Try(prev, curpos + 1) ▷ Recurse
10: end procedure

An implementation in C.
# include < stdio .h >
# include < limits .h >

int a [100];
int n ;

int max ( int a , int b ) {

return ( a > b ? a : b ) ;
}

int Try ( int prev , int curpos ) {

if ( curpos == n ) return 0;
int taken = 0;
if ( a [ curpos ] > prev ) taken = 1 + Try ( a [ curpos ] , curpos + 1) ;
int nottaken = Try ( prev , curpos + 1) ;
return max ( taken , nottaken ) ;
}

int main () {
scanf ( " % d " , & n ) ;
for ( int i = 0; i < n ; i ++) scanf ( " % d " , & a [ i ]) ;
printf ( " % d \ n " , Try ( INT_MIN , 0) ) ;
}

An implementation in Python.
a = list ( map ( int , input () . split () ) )
n = len ( a )

def Try ( prev , curpos ) :

if curpos == n :
return 0
taken = 0
if a [ curpos ] > prev :
taken = 1 + Try ( a [ curpos ] , curpos + 1)
nottaken = Try ( prev , curpos + 1)
return max ( taken , nottaken )

print ( Try ( int ( -1 e9 ) , 0) )

2.11 Travelling salesman

This section consider the following infamous problem:
Given a list of n cities and the distances between pair of cities, what is the shortest possible route that
visits each city and returns to the origin city? The informations are provided in a n × n matrix C, where
C[i, j] = C[j, i] is the cost to travel from city i to city j. Assume that C[i, i] = 0 for all i, C[i, j] = +∞
if i and j are not connected.
Our route will have the form x[1..n + 1] where x[1] = x[n + 1] = 1 and x[1..n] is a permutation of length n.
We will backtrack like this: Assume that we are at city x[i], then x[i + 1] can be picked from the cities that is
connected to x[i].
We need to optimize this by using bounding. We will initialize a best configuration with cost = +∞. When we
choose x[i], we will check if the cost up to that city is less that the cost of best configuration. If it is not, then we
try other city because it is pointless if we keep choosing that city. When we get to x[n], we need to check if it is
connected to x[1]. If it is, then we update the cost of best config.

15
 Here is the pseudocode of the recursive function.

Algorithm 13 TSP
1: procedure Try(i)
2: for j ← 2 to ncity do
3: if j is not visited then
4: x[i] ← j
5: pathcost[i] = pathcost[i − 1] + cost[x[i − 1], j]
6: if pathcost[i] < mincost then
7: if i < ncity then
8: Mark j as visited
9: Try(i + 1)
10: Unmark j
11: else
12: Update solution
13: end if
14: end if
15: end if
16: end for
17: end procedure

An implementation in C.
# include < stdio .h >
# include < string .h >
# include < limits .h >

int cost [20][20];

int tmp [21] , best [21] , path_cost [21];
int vis [20] = {0};
int n_path , n_city , min_cost ;

void init () {
vis [1] = 1; tmp [1] = 1; path_cost [1] = 0; min_cost = ( int ) 1 e9 ;
}

void print_sol () {
if ( min_cost == ( int ) 1 e9 ) printf ( " No solution .\ n " ) ;
else {
for ( int i = 1; i <= n_city ; i ++) printf ( " % d -> " , best [ i ]) ;
printf ( " 1\ n " ) ;
printf ( " Cost : % d \ n " , min_cost ) ;
}
}

void Try ( int i ) {

for ( int j = 2; j <= n_city ; j ++) {
if (! vis [ j ]) {
tmp [ i ] = j ;
path_cost [ i ] = path_cost [ i - 1] + cost [ tmp [ i - 1]][ j ];

if ( path_cost [ i ] < min_cost ) {

if ( i < n_city ) {
vis [ j ] = 1; Try ( i + 1) ; vis [ j ] = 0;
}
else {
if ( path_cost [ n_city ] + cost [ tmp [ n_city ]][1] < min_cost ) {
for ( int i = 1; i <= n_city ; i ++) best [ i ] = tmp [ i ];
min_cost = path_cost [ n_city ] + cost [ tmp [ n_city ]][1];
}
}
}
}
}
}

int main () {
memset ( cost , 255 , sizeof ( cost ) ) ;

scanf ( " % d % d " , & n_city , & n_path ) ;

for ( int k = 1; k <= n_path ; k ++) {

int m , n , c ;

16
 scanf ( " % d % d % d " , &m , &n , & c ) ;
cost [ n ][ m ] = cost [ m ][ n ] = c ;
}
for ( int i = 1; i <= n_city ; i ++) {
for ( int j = 1; j <= n_city ; j ++) {
cost [ i ][ j ] == -1 ? ( int ) 1 e9 : cost [ i ][ j ];
}
}

init () ;
Try (2) ;
print_sol () ;
}

17