MCD4710

Introduction to algorithms
and programming

Lecture 21
Backtracking
COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969
WARNING
This material has been reproduced and communicated to you by or on behalf of Monash
University pursuant to Part VB of the Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright under the Act. Any
further reproduction or communication of this material by you may be the subject of
copyright protection under the Act.
Do not remove this notice.

2
Objectives
• Getting to know the backtracking design paradigm
• Seeing backtracking implementations for specific problems as
well as a generic implementation
• Recap of graph nomenclature and introduction to the
Hamiltonian cycle problem
N-Queens Problem
8-Queens Puzzle

Place 8 queens on a chess board so that none of them are

attacking each other!
8-Queens Puzzle

Q
Q

Place 8 queens on a chess board so that none of them are

attacking each other!
8-Queens Puzzle

Q
Q
Q

Place 8 queens on a chess board so that none of them are

attacking each other!
N-Queens Problem

…
…
Input: Positive integer 𝑛
Output: All configurations of 𝑛 queens on an 𝑛 × 𝑛 chessboard such that
none of them are attacking each other
Representation of configuration
columns
0 1 2 3

Q Q 0
1
rows
Q 2
Q 3
[2, 3, 0, 0]

row for queen row for queen

in column 0 in column 2
The following configuration of the 4-
queens problem…
Q A. is a solution, represented by [2,0,3,1]
Q B. is a solution, represented by [3,1,4,2]
C. is represented by [2,0,3,1], and is not a
Q solution
Q D. None of the above

1. Visit https://flux.qa

2. Log in using your Authcate details (not required if

you’re already logged in to Monash)

3. Touch the + symbol and enter the code: UF7BD9

4. Answer questions when they pop up.

Implementing the rules
Q How to detect a diagonal attack between
(r1,c1) and (r2,c2)?
Q Q
A. c1-c2==r1-r2
B. abs(c1-r1)==abs(c2-r2)
Q C. abs(c1-c2)==abs(r1-r2)
D. c1-r1==c1-r2
def attacks(r1, c1, r2, c2):
return r1 == r2 or c1 == c2 or \
abs(c1 - c2) == abs(r1 - r2)

def valid(conf):
for i in range(len(conf)):
for j in range(i+1, len(conf)):
if attacks(conf[i], i, conf[j], j):
return False
return True
Brute force solution
def queens(n):
confs = bounded_lists([n]*n)
return list(filter(valid, confs))
n=6
#bounded lists 𝑛𝑛
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 2]
[0, 0, 0, 0, 0, 3]
[0, 0, 0, 0, 0, 4]
[0, 0, 0, 0, 0, 5]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 1, 1]
[0, 0, 0, 0, 1, 2]
…

…
[5, 5, 5, 5, 5, 5]
Improved brute force solution
def queens(n):
confs = permutations(0, n)
return list(filter(valid, confs))
n=6

[0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 5, 4],
[0, 1, 2, 4, 3, 5],
[0, 1, 2, 4, 5, 3],
[0, 1, 2, 5, 3, 4],
[0, 1, 2, 5, 4, 3],
[0, 1, 3, 2, 4, 5],
[0, 1, 3, 2, 5, 4],
[0, 1, 3, 4, 2, 5],
…

…
[5, 4, 3, 2, 1, 0]
Improved brute force solution
def queens(n):
confs = permutations(0, n)
return list(filter(valid, confs))
[0, 1, 2, 3] [2, 0, 1, 3]
[0,1,2,3] [0, 1, 3, 2] [2, 0, 3, 1]
[0, 2, 1, 3] [2, 1, 0, 3]
[0, 2, 3, 1] [2, 1, 3, 0]
[0, 3, 1, 2] [2, 3, 0, 1]
[0, 3, 2, 1] [2, 3, 1, 0]
[1, 0, 2, 3] [3, 0, 1, 2]
[1, 0, 3, 2] [3, 0, 2, 1]
[1, 2, 0, 3] [3, 1, 0, 2]
[1, 2, 3, 0] [3, 1, 2, 0]
[1, 3, 0, 2] [3, 2, 0, 1]
4x3x2x1 = 24 [1, 3, 2, 0] [3, 2, 1, 0]

15
What is Backtracking?
Exit

and so on
…

Start
Possible Positions: [0,1,2,3,4,5,6,7]

0 Q
1
2
3
4
5
6
7

17
Possible Positions: [0,1,2,3,4,5,6,7]

0 Q
1
2
3
4
5
6
7

Partial Solution: [0]

18
Possible Positions: [2,3,4,5,6,7]

0 Q
1
2
3
4
5
6
7

Partial Solution: [0]

19
0 Q
1
2 Q
3
4
5
6
7

Partial Solution: [0, 2]

20
Possible Positions: [4,5,6,7]

0 Q
1
2 Q
3
4
5
6
7

Partial Solution: [0, 2]

21
0 Q
1
2 Q
3
4 Q
5
6
7

Partial Solution: [0, 2, 4]

22
Possible Positions: [1,6,7]

0 Q
1
2 Q
3
4 Q
5
6
7

Partial Solution: [0, 2, 4]

23
0 Q
1 Q
2 Q
3
4 Q
5
6
7

Partial Solution: [0, 2, 4, 1]

24
Possible Positions: [3, 7]

0 Q
1 Q
2 Q
3
4 Q
5
6
7

Partial Solution: [0, 2, 4, 1]

25
0 Q
1 Q
2 Q
3 Q
4 Q
5
6
7

Partial Solution: [0, 2, 4, 1, 3]

26
0 Q
1 Q
2 Q
3 Q
4 Q
5 Backtrack!
6
7

Partial Solution: [0, 2, 4, 1, 3]

27
Possible Positions: [3, 7]

0 Q
1 Q
2 Q
3 [0, 2, 4, 1, 3]
4 Q
5
6
7

Partial Solution: [0, 2, 4, 1]

28
0 Q
1 Q
2 Q
3 [0, 2, 4, 1, 3]
4 Q
5
6
7 Q

Partial Solution: [0, 2, 4, 1, 7]

29
0 Q
1 Q
2 Q
3
4 Q
5 [0, 2, 4, 1, 3]
6
[0, 2, 4, 1, 7]
7 Q

Partial Solution: [0, 2, 4, 1, 7]

30
Possible Positions: [3, 7]

0 Q
1 Q
2 Q
3
4 Q
5
6
7

Partial Solution: [0, 2, 4, 1]

31
Possible Positions: [1,6,7]

0 Q
1
2 Q
3
4 Q
5
6
7

Partial Solution: [0,2,4]

32
0 Q
1
2 Q
3
4 Q
5
6 Q
7

Partial Solution: [0,2,4,6] etc … 33

Backtracking ...
Let’s do it once more

34
[]

[0]
Partial [0,1,2,3,4,5,6,7]

Solutions [2,3,4,5,6,7]
[0,2]

[4,5,6,7]

[0,2,4] Possible
[1,6,7]
Positions

[0,2,4,1] [0,2,4,6]
[3,7]

…
[0,2,4,1,3] [0,2,4,1,7] 35
Requirements
• Keep track of partial solution.
• Build a set of positions selected.
• Keep track of possible next positions.
• Be able to undo steps.
• Be able to check whether the
partial solution is a (complete) solution.

36
For the 8 Queen problem, a partial
solution is a solution if its length is 8.

a. True
b. False

1. Visit https://flux.qa

2. Log in using your Authcate details (not required if

you’re already logged in to Monash)

3. Touch the + symbol and enter the code: UF7BD9

4. Answer questions when they pop up.

37
Possible Positions: [0, 1, 2, 3]
[]

Partial Solution: []
38
[]

Q
[0]

Partial Solution: [0]

39
Possible Positions: [2, 3]
[]

Q 2, 3
[0]

Partial Solution: [0]

40
[]

Q 2, 3
[0]

[0, 2]

Partial Solution: [0, 2]

41
Possible Positions: []
[]

Q 2, 3
[0]
-
[0, 2]

Partial Solution: [0, 2]

42
[]

Q 2, 3
[0]
-
[0, 2]

Backtrack
43
[]

Q 2, 3
[0]
-
[0, 2] [0, 3]

Partial Solution: [0, 3]

44
Possible Positions: [1]
[]

Q 2, 3
[0]
- 1
[0, 2] [0, 3]

Partial Solution: [0, 3]

45
[]

Q 2, 3
[0]
Q - 1
[0, 2] [0, 3]

[0, 3, 1]
Q

Partial Solution: [0, 3, 1]

46
Possible Positions: []
[]

Q 2, 3
[0]
Q - 1
[0, 2] [0, 3]

-
[0, 3, 1]
Q

Partial Solution: [0, 3, 1]

47
[]

Q 2, 3
[0]
- 1
[0, 2] [0, 3]

-
[0, 3, 1]
Q

Backtrack
48
[]

Q 2, 3
[0]
- 1
[0, 2] [0, 3]

-
[0, 3, 1]

Backtrack
49
[]

Q 2, 3
[0]
- 1
[0, 2] [0, 3]

-
[0, 3, 1]

Backtrack
50
[]

2, 3
[0] [1]
Q - 1
[0, 2] [0, 3]

-
[0, 3, 1]

Partial Solution: [1]

51
Possible Positions: [3]
[]

2, 3 3
[0] [1]
Q - 1
[0, 2] [0, 3]

-
[0, 3, 1]

Partial Solution: [1]

52
[]

2, 3 3
[0] [1]
Q - 1
[0, 2] [0, 3] [1, 3]

-
[0, 3, 1]
Q

Partial Solution: [1, 3]

53
Possible Positions: [0]
[]

2, 3 3
[0] [1]
Q - 1 0
[0, 2] [0, 3] [1, 3]

-
[0, 3, 1]
Q

Partial Solution: [1, 3]

54
[]

Q 2, 3 3
[0] [1]
Q - 1 0
[0, 2] [0, 3] [1, 3]

-
[0, 3, 1] [1, 3, 0]
Q

Partial Solution: [1, 3]

55
Possible Positions: [2]
[]

Q 2, 3 3
[0] [1]
Q - 1 0
[0, 2] [0, 3] [1, 3]

- 2
[0, 3, 1] [1, 3, 0]
Q

Partial Solution: [1, 3, 0]

56
[]

Q 2, 3 3
[0] [1]
Q - 1 0
[0, 2] [0, 3] [1, 3]

Q - 2
[0, 3, 1] [1, 3, 0]
Q
[1, 3, 0, 2]

Partial Solution: [1, 3, 0, 2] = Solution

57
Backtracking Algorithm – Queen’s
def getPossible(partial, board_size):
# Finds the next possible options given the partial solution
not_possible = []
possible = [] If partial is empty
all rows are
if partial == []:
possible
possible = [k for k in range(board_size)]
else:
Check partial for rows that are not possible and
append to not_possible

Check partial for diagonals that are not possible and

append to not_possible

for k in range(board_size):
if k not in not_possible: Whatever is not
possible.append(k) in not_possible
return possible is possible

58
Backtracking Algorithm – Queen’s
def getPossible(partial, board_size):
# Finds the next possible options given the partial solution
not_possible = []
possible = []

if partial == []:
possible = [k for k in range(board_size)]
else:
for k in partial:
not_possible.append(k)

Check partial for diagonals that are not possible and

append to not_possible

for k in range(board_size):
if k not in not_possible:
possible.append(k)
return possible

59
Backtracking Algorithm – Queen’s
def getPossible(partial, board_size):
# Finds the next possible options given the partial solution
not_possible = []
possible = []

if partial == []:
possible = [k for k in range(board_size)]
else:
for k in partial:
not_possible.append(k)

for k in range(len(partial)):
j = (k * -1) - 1
if (partial[j] + j) not in not_possible:
not_possible.append(partial[j] + j)
if (partial[j] - j) not in not_possible:
not_possible.append(partial[j] - j)

for k in range(board_size):
if k not in not_possible:
possible.append(k)
return possible 60
Backtracking Algorithm – Queen’s
Find a set of next
positions
def queens(partial, board_size):
possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
Check if
if possibleItems == []: partialSolution is
updateSolution(partial, board_size) a solution
else:
for item in possibleItems: Represent and
partial.append(item) keep track of
queens(partial, board_size) solutions
partial.pop()
Keep track of
return True possible next
positions
Backtrack

61
Backtracking Algorithm – Queen’s
def queens(partial, board_size):
possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
return True

62
queens([],4)

[]

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
63
return True
queens([],4)

[]

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
64
return True
queens([],4)
possibleItems = [0,1,2,3]
[]

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
65
return True
queens([],4)
possibleItems = [0,1,2,3]
[]

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
66
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]

item = 1 :

item = 2 :

item = 3 :

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
67
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]

item = 1 :
[0]

item = 2 :

item = 3 :

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
68
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4)

item = 1 :
[0]

item = 2 :

item = 3 :

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
69
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4)

queens([0],4) item = 1 :
[0]

item = 2 :

item = 3 :

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
70
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3]

item = 2 :

item = 3 :

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
71
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3]

item = 2 :

item = 3 :

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
72
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3]
item = 2 :
item = 2 :

item = 3 :
item = 3 :

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
73
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3]
item = 2 : [0, 2]
partial = [0,2]
item = 2 :

item = 3 :
item = 3 :

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
74
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3]
item = 2 : [0, 2]
partial = [0,2]
item = 2 :
queens([0,2],4)

item = 3 :
item = 3 :

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
75
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3]
item = 2 : [0, 2]
partial = [0,2]
item = 2 :
queens([0,2],4)

item = 3 :
item = 3 :

queens([0,2],4)

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
76
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3] -
item = 2 : [0, 2]
partial = [0,2]
item = 2 :
queens([0,2],4)

item = 3 :
item = 3 :

queens([0,2],4)
possibleItems = []

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
77
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
partial = [0] []
queens([0],4)
2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3] -
item = 2 :
[0, 2]
partial = [0,2]
item = 2 :
queens([0,2],4)

item = 3 :
item = 3 :

queens([0,2],4)
possibleItems = []

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
78
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3] -
item = 2 : [0, 2]
partial = [0,2]
item = 2 :
queens([0,2],4)

item = 3 :
item = 3 :

queens([0,2],4)
possibleItems = []
updateSolution([0,2],4)

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
79
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3] -
item = 2 : [0, 2]
partial = [0,2]
item = 2 :
queens([0,2],4)

item = 3 :
item = 3 :

queens([0,2],4)
possibleItems = []
updateSolution([0,2],4)
return True

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
80
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3] -
item = 2 : [0, 2]
partial = [0,2]
item = 2 :
queens([0,2],4)

item = 3 :
item = 3 :

TRUE

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
81
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3]
item = 2 :
partial = [0,2]
item = 2 :
queens([0,2],4)
partial = [0]
item = 3 :
item = 3 :

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
82
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3]
item = 2 :
partial = [0,2]
item = 2 :
queens([0,2],4)
partial = [0]
item = 3 :
item = 3 :

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
83
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3]
item = 2 : [0, 3]
partial = [0,2]
item = 2 :
queens([0,2],4)
partial = [0]
item = 3 :
partial = [0,3]
item = 3 :

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
84
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3]
item = 2 : [0, 3]
partial = [0,2]
item = 2 :
queens([0,2],4)
partial = [0]
item = 3 :
partial = [0,3]
item = 3 :
queens([0,3],4)

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
85
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3]
item = 2 : [0, 3]
partial = [0,2]
item = 2 :
queens([0,2],4)
partial = [0]
item = 3 :
partial = [0,3]
item = 3 :
queens([0,3],4)

queens([0,3],4)

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
86
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3] 1
item = 2 : [0, 3]
partial = [0,2]
item = 2 :
queens([0,2],4)
partial = [0]
item = 3 :
partial = [0,3]
item = 3 :
queens([0,3],4)

queens([0,3],4)
possibleItems = [1]

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
87
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3] 1
item = 2 : [0, 3]
partial = [0,2]
item = 2 :
queens([0,2],4)
partial = [0]
item = 3 :
partial = [0,3]
item = 3 :
queens([0,3],4)

queens([0,3],4)
possibleItems = [1]

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
88
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3] 1
item = 2 : [0, 3]
partial = [0,2]
item = 2 :
queens([0,2],4)
partial = [0]
item = 3 :
partial = [0,3]
item = 3 :
queens([0,3],4)

queens([0,3],4)
possibleItems = [1]
item = 1 :

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
89
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3] 1
item = 2 : [0, 3]
partial = [0,2]
item = 2 :
queens([0,2],4)
partial = [0] [0, 3, 1]
item = 3 :
partial = [0,3]
item = 3 :
queens([0,3],4)

queens([0,3],4)
possibleItems = [1]
item = 1 :
partial = [0,3,1]

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
90
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3] 1
item = 2 : [0, 3]
partial = [0,2]
item = 2 :
queens([0,2],4)
partial = [0] [0, 3, 1]
item = 3 :
partial = [0,3]
item = 3 :
queens([0,3],4)

queens([0,3],4)
possibleItems = [1]
item = 1 :
partial = [0,3,1]
queens([0,3,1],4)

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
91
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3] 1
item = 2 : [0, 3]
partial = [0,2]
item = 2 :
queens([0,2],4)
partial = [0] [0, 3, 1]
item = 3 :
partial = [0,3]
item = 3 :
queens([0,3],4)

queens([0,3],4)
possibleItems = [1]
item = 1 :
partial = [0,3,1]
queens([0,3,1],4)

queens([0,3,1],4)

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
92
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3] 1
item = 2 : [0, 3]
partial = [0,2]
item = 2 :
queens([0,2],4) -
partial = [0] [0, 3, 1]
item = 3 :
partial = [0,3]
item = 3 :
queens([0,3],4)

queens([0,3],4)
possibleItems = [1]
item = 1 :
partial = [0,3,1]
queens([0,3,1],4)

queens([0,3,1],4)
possibleItems = []
def queens(partial, board_size):
possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
93
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3] 1
item = 2 : [0, 3]
partial = [0,2]
item = 2 :
queens([0,2],4) -
partial = [0] [0, 3, 1]
item = 3 :
partial = [0,3]
item = 3 :
queens([0,3],4)

queens([0,3],4)
possibleItems = [1]
item = 1 :
partial = [0,3,1]
queens([0,3,1],4)

queens([0,3,1],4)
possibleItems = []
def queens(partial, board_size):
possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
94
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3] 1
item = 2 : [0, 3]
partial = [0,2]
item = 2 :
queens([0,2],4) -
partial = [0] [0, 3, 1]
item = 3 :
partial = [0,3]
item = 3 :
queens([0,3],4)

queens([0,3],4)
possibleItems = [1]
item = 1 :
partial = [0,3,1]
queens([0,3,1],4)

queens([0,3,1],4)
possibleItems = []
updateSolution([0,3,1],4) def queens(partial, board_size):
possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
95
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3] 1
item = 2 : [0, 3]
partial = [0,2]
item = 2 :
queens([0,2],4) -
partial = [0] [0, 3, 1]
item = 3 :
partial = [0,3]
item = 3 :
queens([0,3],4)

queens([0,3],4)
possibleItems = [1]
item = 1 :
partial = [0,3,1]
queens([0,3,1],4)

queens([0,3,1],4)
possibleItems = []
updateSolution([0,3,1],4) def queens(partial, board_size):
return True possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
96
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3] 1
item = 2 : [0, 3]
partial = [0,2]
item = 2 :
queens([0,2],4) -
partial = [0] [0, 3, 1]
item = 3 :
partial = [0,3]
item = 3 :
queens([0,3],4)

queens([0,3],4)
possibleItems = [1]
item = 1 :
partial = [0,3,1]
queens([0,3,1],4)

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
97
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3] 1
item = 2 : [0, 3]
partial = [0,2]
item = 2 :
queens([0,2],4)
partial = [0]
item = 3 :
partial = [0,3]
item = 3 :
queens([0,3],4)

queens([0,3],4)
possibleItems = [1]
item = 1 :
partial = [0,3,1]
queens([0,3,1],4)
partial = [0,3]

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
98
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3] 1
item = 2 : [0, 3]
partial = [0,2]
item = 2 :
queens([0,2],4)
partial = [0]
item = 3 :
partial = [0,3]
item = 3 :
queens([0,3],4)

queens([0,3],4)
possibleItems = [1]
item = 1 :
partial = [0,3,1]
queens([0,3,1],4)
partial = [0,3]
return True

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
99
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3] 1
item = 2 : [0, 3]
partial = [0,2]
item = 2 :
queens([0,2],4)
partial = [0]
item = 3 :
partial = [0,3]
item = 3 :
queens([0,3],4)

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
100
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3]
item = 2 :
partial = [0,2]
item = 2 :
queens([0,2],4)
partial = [0]
item = 3 :
partial = [0,3]
item = 3 :
queens([0,3],4)
partial = [0]

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
101
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3
queens([0],4) item = 1 :
[0]
possibleItems = [2,3]
item = 2 :
partial = [0,2]
item = 2 :
queens([0,2],4)
partial = [0]
item = 3 :
partial = [0,3]
item = 3 :
queens([0,3],4)
partial = [0]
return True

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
102
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4) 2, 3

item = 1 :
[0]

item = 2 :

item = 3 :

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
103
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4)
partial = []
item = 1 :

item = 2 :

item = 3 :

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
104
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4)
partial = []
item = 1 :

item = 2 :

item = 3 :

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
105
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4)
partial = []
item = 1 :
[1]
partial = [1]

item = 2 :

item = 3 :

def queens(partial, board_size):

possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
106
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4)
partial = []
3
item = 1 :
[1]
partial = [1]
queens([1],4) 0
queens([1],4) [1, 3]
item = 2 :
possibleItems = [3] 2
item = 3 : [1, 3, 0]
partial = [1,3]
queens([1,3],4)
item = 3 :
partial = [1] [1, 3, 0, 2]
queens([1,3],4)
possibleItems = [0]
item = 0 :
partial = [1,3,0]
queens([1,3,0],4)
partial = [1,3]

queens([1,3,0],4)
possibleItems = [2]
queens([1,3,0,2],4) item = 2 :
possibleItems = [] partial = [1,3,0,2]
updateSolution([1,3,0,2],4) queens([1,3,0,2],4)
partial = [1,3,0]
def queens(partial, board_size):
possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
107
return True
queens([],4)
possibleItems = [0,1,2,3]
item = 0 :
[]
partial = [0]
queens([0],4)
partial = []
2, 3 3
queens([0],4) item = 1 :
[0] [1]
partial = [1]
possibleItems = [2,3] - 1 0
queens([1],4)
item = 2 : [0, 2] [0, 3] [1, 3]
partial = [] queens([1],4)
partial = [0,2]
item = 2 :
queens([0,2],4) possibleItems = [3] - 2
partial = [2]
partial = [0] item = 3 : [0, 3, 1] [1, 3, 0]
queens([2],4)
item = 3 : partial = [1,3]
partial = []
partial = [0,3] queens([1,3],4)
item = 3 :
queens([0,3],4) partial = [1] [1, 3, 0, 2]
partial = [3]
partial = [0]
queens([3],4) queens([1,3],4)
partial = []
possibleItems = [0]
item = 0 :
queens([0,2],4) queens([0,3],4) partial = [1,3,0]
possibleItems = [] possibleItems = [1] queens([1,3,0],4)
updateSolution([0,2],4) item = 1 : partial = [1,3]
partial = [0,3,1]
queens([0,3,1],4) queens([1,3,0],4)
partial = [0,3]
possibleItems = [2]
queens([1,3,0,2],4) item = 2 :
possibleItems = [] partial = [1,3,0,2]
queens([0,3,1],4) updateSolution([1,3,0,2],4) queens([1,3,0,2],4)
possibleItems = [] partial = [1,3,0]
updateSolution([0,3,1],4) def queens(partial, board_size):
possibleItems = getPossible(partial, board_size)
print(partial, " || ", possibleItems)
if possibleItems == []:
updateSolution(partial, board_size)
else:
for item in possibleItems:
partial.append(item)
queens(partial, board_size)
partial.pop()
108
return True
Backtracking reduces considered
configurations substantially…
…yet is still an exponential time
algorithm
…yet is still an exponential time
algorithm
General Backtracking
Implementation
Backtracking
General approach
• Find a representation of partial solutions such that all valid options for
augmenting a partial solution can be identified as well as when a
partial solution is complete
• Extend problem to find finding all solutions sols(part) that can be
reached by a sequence of valid decisions from a specific partial
solution part
• Construct all solutions via partial solutions using recurrence relation:
sols(part)=sols(part+[a1])+…+sols(part+[ak])
where [a1,…,ak] are all valid options to augment part

Advantage over brute force:

When reaching partial solution without valid option for augmentation,
the algorithm backtracks
(without exploring a large number of invalid configurations)
General implementation
def queens(n, part=[]):
if len(partial) == n:
return [partial]
else:
res = []
for opt in options(partial, n):
res += queens(n, partial + [opt])
return res

def solutions(completed, options, part=[]):

if completed(part):
return [part]
else:
res = []
for opt in options(part):
augmented = part+[opt]
res += solutions(completed, options,
augmented)
return res
General implementation
def queens(n):

def options(part):
…

def complete(part): return len(part) == n

return solutions(complete, options)

def solutions(completed, options, part=[]):

if completed(part):
return [part]
else:
res = []
for opt in options(part):
augmented = part+[opt]
res += solutions(completed, options,
augmented)
return res
Hamiltonian Cycle Problem
Recall some graph concepts
3

𝑉 = {0, … , 5}
1 𝐸 = { 0,1 , 0,2 , (0,3)
0 5 1,2 , 1,3 , 1,5 ,
2,4 , 3,5 , 4,5 }
4
2

Definitions:
• A path is a non-self-intersecting sequence of successively
connected vertices.
Recall some graph concepts
3

𝑉 = {0, … , 5}
1 𝐸 = { 0,1 , 0,2 , (0,3)
0 5 1,2 , 1,3 , 1,5 ,
2,4 , 3,5 , 4,5 }
4
2

Definitions:
• A path is a non-self-intersecting sequence of successively
connected vertices. E.g., [3, 1, 2, 4]
Recall some graph concepts
3

𝑉 = {0, … , 5}
1 𝐸 = { 0,1 , 0,2 , (0,3)
0 5 1,2 , 1,3 , 1,5 ,
2,4 , 3,5 , 4,5 }
4
2

Definitions:
• A path is a non-self-intersecting sequence of successively
connected vertices. E.g., [3, 1, 2, 4]
• A cycle is path with same start and end vertex.
Recall some graph concepts
3

𝑉 = {0, … , 5}
1 𝐸 = { 0,1 , 0,2 , (0,3)
0 5 1,2 , 1,3 , 1,5 ,
2,4 , 3,5 , 4,5 }
4
2

Definitions:
• A path is a non-self-intersecting sequence of successively
connected vertices. E.g., [3, 1, 2, 4]
• A cycle is path with same start and end vertex. E.g., [0, 3, 1, 2, 0]
Recall some graph concepts
3

𝑉 = {0, … , 5}
1 𝐸 = { 0,1 , 0,2 , (0,3)
0 5 1,2 , 1,3 , 1,5 ,
2,4 , 3,5 , 4,5 }
4
2

Definitions:
• A path is a non-self-intersecting sequence of successively
connected vertices. E.g., [3, 1, 2, 4]
• A cycle is path with same start and end vertex. E.g., [0, 3, 1, 2, 0]
• A Hamiltonian cycle is a cycle that contains all vertices
Recall some graph concepts
3

𝑉 = {0, … , 5}
1 𝐸 = { 0,1 , 0,2 , (0,3)
0 5 1,2 , 1,3 , 1,5 ,
2,4 , 3,5 , 4,5 }
4
2

Definitions:
• A path is a non-self-intersecting sequence of successively
connected vertices. E.g., [3, 1, 2, 4]
• A cycle is path with same start and end vertex. E.g., [0, 3, 1, 2, 0]
• A Hamiltonian cycle is a cycle that contains all vertices
Not every graph has Hamiltonian cycle
3 3
?
1 1
0 5 0 5

4 4
2 2

Definitions:
• A path is a non-self-intersecting sequence of successively
connected vertices. E.g., [3, 1, 2, 4]
• A cycle is path with same start and end vertex. E.g., [0, 3, 1, 2, 0]
• A Hamiltonian cycle is a cycle that contains all vertices
Puzzle Variant of Traveling
Salesperson Problem 3
3
?
1 1
0 5 0 5

4 4
2 2

Hamiltonian Cycle Listing Problem:

Input: A graph 𝐺 = 𝑉, 𝐸
Output: The Hamiltonian cycles of 𝐺
Partial Hamiltonian cycles
3
[1,2,3]
1
0 5

2 4

3 3
3
[2,3,5] [1,4] [1,5]

1 1
1 0 5 0 5
0 5

2 4 2 4
2 4

3 3
3
[4] [5] [3,4]

1 1
1 0 5 0 5
0 5

2 4 2 4
2 4
When is a partial solution
complete?
3
[5]

1
0 5

2 4

3
[3]

1
0 5

2 4

3
[]

1
0 5

2 4
When is a partial solution
complete?
3 3
[5] [3,4]

1 1
0 5 0 5

2 4 2 4

3 3
[3] []
1 1
0 5 0 5

2 4 2 4

3
[]

1
0 5

2 4
When is a partial solution
complete?
3 3 3
[5] [3,4] [4]

1 1 1
0 5 0 5 0 5

4 2 4 2 4
2
3 3 3
[3] [] []

1 1 1
0 5 0 5 0 5

2 4 2 4 2 4

3
[]
def complete(part):
1
0 5 return len(part) == len(graph) \
and graph[part[-1]][0]:
2 4
Putting everything together
def hamiltonian_cycles(graph):

def completed(part):
return len(part) == len(graph) \
and graph[part[-1]][0]

def options(part):
res = []
path = [0] + part
for v in neighbours(path[-1], graph):
if v not in path:
res += [v]
return res

return solutions(completed, options)

3 3 3 3

1 1 1 1
0 5 0 5 0 5 0 5 …

2 4 2 4 2 4 2 4
Brute force solution
def cycle(vertices, graph):
for i in range(len(vertices)):
if not graph[vertices[i-1]][vertices[i]]:
return False
return True

def brute_force_hamiltonian_cycles(graph):
perms = permutations(1, len(graph))
res = []
for perm in perms:
walk = [0] + perm
if cycle(walk, graph):
res += [walk]
return res
3

1 Backtracking: 43 partial solutions

0 5
Brute force: 120 permutations

2 4
Brute force solution
def cycle(vertices, graph):
for i in range(len(vertices)):
if not graph[vertices[i-1]][vertices[i]]:
return False
return True

def brute_force_hamiltonian_cycles(graph):
perms = permutations(1, len(graph))
res = []
for perm in perms:
walk = [0] + perm
if cycle(walk, graph):
res += [walk]
return res
3 7

5 6 Backtracking: 383 partial solutions

1
0
8

2 4 9
Brute force solution
def cycle(vertices, graph):
for i in range(len(vertices)):
if not graph[vertices[i-1]][vertices[i]]:
return False
return True

def brute_force_hamiltonian_cycles(graph):
perms = permutations(1, len(graph))
res = []
for perm in perms:
walk = [0] + perm
if cycle(walk, graph):
res += [walk]
return res
3 7

5 6 Backtracking: 383 partial solutions

1
0
8 Brute force: 362880 permutations
2 4 9
Knapsack Problem
Recall the Knapsack Problem

4kg 9kg 10kg

$400 $1800 $3500

20kg 2kg 1kg

$4000 $1000 $200
http://www.unusualbag.com/

Input: 1. set of items with associated weights and values

2. capacity
Output: selection of items such that
a) sum of item weights less than capacity
b) sum of item values maximum (among all selections satisfying (a))
For brute force algorithm, we
represented solutions as bitlists
def bitlists(n): [0, 0, 0, 0, 0, 0] first
first = n*[0] <
last = n*[1] [0, 0, 0, 0, 0, 1]
res = [first] <
while res[-1] != last: [0, 0, 0, 0, 1, 0]
res += [lex_suc(res[-1])] <
return res [0, 0, 0, 0, 1, 1]
<
[0, 0, 0, 1, 0, 0]
def lex_suc(bitlst): <
“”” …
I: bitlist a!=[1,...,1] <
O: direct lex. successor of a [0, 1, 0, 1, 1, 1] a
“”” <
res = bitlst[:] [0, 1, 1, 0, 0, 0] lex_suc(a)
i = len(res) - 1 <
while res[i] == 1: …
res[i] = 0 <
i -= 1 [1, 1, 1, 1, 1, 0]
res[i] = 1 <
return res [1, 1, 1, 1, 1, 1] last
Partial solution

4kg 9kg 10kg 20kg 2kg 1kg

[]
0 1

0 4
0 1
0 1 0 1

0 9 4 13
00 01 10 11
0 1 0 1 0 1 0
0 10 9 19 4 14 13
00 0 00 1 01 0 01 1 10 0 10 1 11 0
0 1 0 0 0 0 0 0
0 20 10 9 19 4 14 13
00 0 0 00 01 00 1 0 01 0 0 01 1 0 10 0 0 10 1 0 11 0 0
0 1 0 0 1 0 1 0 0 1 0 10 1
… … … … … … … …
Complete solutions are of length n

4kg 9kg 10kg 20kg 2kg 1kg

[]
0 1

0 4
0 1
0 1 0 1

0 9 4 13
00 01 10 11
0 1 0 1 0 1 0
0 10 9 19 4 14 13
00 0 00 1 01 0 01 1 10 0 10 1 11 0
0 1 0 0 0 0 0 0

… … … … … … …
0 1 15 16
0 0 0 0 0 0 0 0 0 0 0 1 … 1 1 0 0 1 0 1 1 0 0 1 1
Let’s use our backtracking function
def knapsack(values, weights, capacity):

def weight(part):
…

def value(part):
…

def options(part):
if weight(part)+weights[len(part)] <= capacity:
return [0, 1]
else:
return [0]

def completed(part):
return len(part) == len(values)

sols = completed_solutions(completed, options)

return max(sols, key=value)

Comparison of backtracking and
brute force algorithm

4kg 9kg 10kg 20kg 2kg 1kg

$400 $1800 $3500 $4000 $1000 $200
Number of solutions (bitlists): 64
Number of feasible solutions: 27

4kg 9kg 10kg 20kg 2kg 1kg 6kg 11kg 7kg 15kg
$400 $1800 $3500 $4000 $1000 $200 $700 $3600 $800 $1500
Number of solutions (bitlists): 1024
Number of feasible solutions: 158
Gain depends on number of items, weights, and capacity
Idea for further improvement: branch-and-bound
(upper bound best possible value with partial solution)
Further Reading
Levitin, Ch 21.1: Backtracking

Levitin, Ch 21.2: Branch-and-bound

Chapter 21 of the book is called “Coping with the

Limitations of Algorithm Power” suggesting that there is
a general limit to what (efficient) algorithms can do.

We’ll investigate this next week as the final topic of the

unit.

140
Coming Up
• NP-completeness
• Revision