Topic 10

Recursive Backtracking
"In ancient times, before computers were invented,
alchemists studied the mystical properties of
numbers. Lacking computers, they had to rely on
dragons to do their work for them. The dragons
were clever beasts, but also lazy and bad-tempered.
The worst ones would sometimes burn their keeper
to a crisp with a single fiery belch. But most dragons
were merely uncooperative, as violence required too
much energy. This is the story of how Martin, an
alchemist’s apprentice, discovered recursion by
outsmarting a lazy dragon."
- David S. Touretzky, Common Lisp: A Gentle Introduction to
Symbolic Computation
CS 307 Fundamentals of 1
Computer Science Recursive Backtracking
 Backtracking

Suppose you have to make a series of

decisions, among various choices, where
– You don’t have enough information to know
what to choose
– Each decision leads to a new set of choices
– Some sequence of choices (possibly more than
one) may be a solution to your problem
Backtracking is a methodical way of trying
out various sequences of decisions, until you
2 find one that “works”
 Solving a maze
Given a maze, find a path from start to finish
At each intersection, you have to decide
between three or fewer choices:
– Go straight
– Go left
– Go right
 You don’t have enough information to choose correctly
 Each choice leads to another set of choices
 One or more sequences of choices may (or may not) lead to
a solution
 Many types of maze problem can be solved with
backtracking

3
 Coloring a map
 You wish to color a map with
not more than four colors
– red, yellow, green, blue
 Adjacent countries must be in
different colors
 You don’t have enough information to choose colors
 Each choice leads to another set of choices
 One or more sequences of choices may (or may not) lead to
a solution
 Many coloring problems can be solved with backtracking

4
 Solving a puzzle
 In this puzzle, all holes but one
are filled with white pegs
 You can jump over one peg
with another
 Jumped pegs are removed
 The object is to remove all
but the last peg
 You don’t have enough information to jump correctly
 Each choice leads to another set of choices
 One or more sequences of choices may (or may not)
lead to a solution
 Many kinds of puzzle can be solved with backtracking

5
 Backtracking (animation)

dead end
?
dead end
dead end

?
start ? ? dead end
dead end
?
success!

6
 Terminology I

A tree is composed of nodes

There are three kinds of

nodes:
The (one) root node
Backtracking can be thought of
Internal nodes
as searching a tree for a
Leaf nodes particular “goal” leaf node
7
 Terminology II

Each non-leaf node in a tree is a parent of

one or more other nodes (its children)
Each node in the tree, other than the root,
has exactly one parent
parent
Usually, however,
we draw our trees
downward, with
parent the root at the top
children children

8
 Real and virtual trees
There is a type of data structure called a tree
– But we are not using it here
If we diagram the sequence of choices we
make, the diagram looks like a tree
– In fact, we did just this a couple of slides ago
– Our backtracking algorithm “sweeps out a tree”
in “problem space”

9
 The backtracking algorithm
Backtracking is really quite simple--we
“explore” each node, as follows:
To “explore” node N:
1. If N is a goal node, return “success”
2. If N is a leaf node, return “failure”
3. For each child C of N,
3.1. Explore C
3.1.1. If C was successful, return “success”
4. Return “failure”

10
 Full example: Map coloring
The Four Color Theorem states that any
map on a plane can be colored with no more
than four colors, so that no two countries
with a common border are the same color
For most maps, finding a legal coloring is
easy
For some maps, it can be fairly difficult to
find a legal coloring
We will develop a complete Java program to
solve this problem
11
 Data structures
We need a data structure that is easy to
work with, and supports:
– Setting a color for each country
– For each country, finding all adjacent countries
We can do this with two arrays
– An array of “colors”, where countryColor[i] is
the color of the ith country
– A ragged array of adjacent countries, where
map[i][j] is the jth country adjacent to country
i
• Example: map[5][3]==8 means the 3th country
12 adjacent to country 5 is country 8
 Creating the map
0 1
4
int map[][]; 2 3
6
5
void createMap() {
map = new int[7][];
map[0] = new int[] { 1, 4, 2, 5 };
map[1] = new int[] { 0, 4, 6, 5 };
map[2] = new int[] { 0, 4, 3, 6, 5 };
map[3] = new int[] { 2, 4, 6 };
map[4] = new int[] { 0, 1, 6, 3, 2 };
map[5] = new int[] { 2, 6, 1, 0 };
map[6] = new int[] { 2, 3, 4, 1, 5 };
}
13
 Setting the initial colors

static final int NONE = 0;

static final int RED = 1;
static final int YELLOW = 2;
static final int GREEN = 3;
static final int BLUE = 4;

int mapColors[] = { NONE, NONE, NONE, NONE,

NONE, NONE, NONE };

14
 The main program

(The name of the enclosing class is ColoredMap)

public static void main(String args[]) {

ColoredMap m = new ColoredMap();
[Link]();
boolean result = [Link](0, RED);
[Link](result);
[Link]();
}

15
 The backtracking method

boolean explore(int country, int color) {

if (country >= [Link]) return true;
if (okToColor(country, color)) {
mapColors[country] = color;
for (int i = RED; i <= BLUE; i++) {
if (explore(country + 1, i)) return true;
}
}
return false;
16
}
 Checking if a color can be
used

boolean okToColor(int country, int color) {

for (int i = 0; i < map[country].length;
i++) {
int ithAdjCountry = map[country][i];
if (mapColors[ithAdjCountry] == color) {
return false;
}
}
return true;
}
17
 Printing the results

void printMap() {
for (int i = 0; i < [Link]; i++) {
[Link]("map[" + i + "] is ");
switch (mapColors[i]) {
case NONE: [Link]("none"); break;
case RED: [Link]("red"); break;
case YELLOW: [Link]("yellow"); break;
case GREEN: [Link]("green"); break;
case BLUE: [Link]("blue"); break;
}
}
}

18
 Backtracking
Start
Success!

Success!

Failure
Problem space consists of states (nodes) and actions
(paths that lead to new states). When in a node can
can only see paths to connected nodes

If a node only leads to failure go back to its "parent"

node. Try other alternatives. If these all lead to failure
then more backtracking may be necessary.
CS 307 Fundamentals of 19
Computer Science Recursive Backtracking
 A More Concrete Example
Sudoku
9 by 9 matrix with some
numbers filled in
all numbers must be between
1 and 9
Goal: Each row, each column,
and each mini matrix must
contain the numbers between
1 and 9 once each
– no duplicates in rows, columns,
or mini matrices

CS 307 Fundamentals of 20
Computer Science Recursive Backtracking
 Solving Sudoku – Brute Force
A brute force algorithm is a
simple but general
approach
Try all combinations until
you find one that works
This approach isn’t clever,
but computers are fast
Then try and improve on
the brute force resuts

CS 307 Fundamentals of 21
Computer Science Recursive Backtracking
 Solving Sudoku
Brute force Sudoku Soluton
– if not open cells, solved 1
– scan cells from left to right,
top to bottom for first open
cell
– When an open cell is found
start cycling through digits 1
to 9.
– When a digit is placed check
that the set up is legal
– now solve the board
CS 307 Fundamentals of 22
Computer Science Recursive Backtracking
 Attendance Question 1
After placing a number in a cell is the
remaining problem very similar to the original
problem?
A. Yes
B. No

CS 307 Fundamentals of 23
Computer Science Recursive Backtracking
 Solving Sudoku – Later Steps
1 1 2 1 2 4

1 2 4 8 1 2 4 8 9

uh oh!

CS 307 Fundamentals of 24
Computer Science Recursive Backtracking
 Sudoku – A Dead End
We have reached a dead end in our search
1 2 4 8 9

With the current set up none of the nine

digits work in the top right corner
CS 307 Fundamentals of 25
Computer Science Recursive Backtracking
 Backing Up
When the search reaches a dead 1 2 4 8 9
end in backs up to the previous
cell it was trying to fill and goes
onto to the next digit
We would back up to the cell with
a 9 and that turns out to be a dead
end as well so we back up again
1 2 4 9
– so the algorithm needs to remember
what digit to try next
Now in the cell with the 8. We try
and 9 and move forward again.

CS 307 Fundamentals of 26
Computer Science Recursive Backtracking
 Characteristics of Brute Force
and Backtracking
Brute force algorithms are slow
The don't employ a lot of logic
– For example we know a 6 can't go in the last 3
columns of the first row, but the brute force
algorithm will plow ahead any way
But, brute force algorithms are fairly easy to
implement as a first pass solution
– backtracking is a form of a brute force algorithm

CS 307 Fundamentals of 27
Computer Science Recursive Backtracking
 Key Insights
After trying placing a digit in a cell we want to solve
the new sudoku board
– Isn't that a smaller (or simpler version) of the same
problem we started with?!?!?!?
After placing a number in a cell the we need to
remember the next number to try in case things
don't work out.
We need to know if things worked out (found a
solution) or they didn't, and if they didn't try the next
number
If we try all numbers and none of them work in our
cell we need to report back that things didn't work
CS 307 Fundamentals of 28
Computer Science Recursive Backtracking
 Recursive Backtracking
Problems such as Suduko can be solved
using recursive backtracking
recursive because later versions of the
problem are just slightly simpler versions of
the original
backtracking because we may have to try
different alternatives

CS 307 Fundamentals of 29
Computer Science Recursive Backtracking
 Recursive Backtracking
Pseudo code for recursive backtracking
algorithms

If at a solution, report success

for( every possible choice from current state /
node)
Make that choice and take one step along path
Use recursion to solve the problem for the new node / state
If the recursive call succeeds, report the success to the next
high level
Back out of the current choice to restore the state at the
beginning of the loop.
Report failure
CS 307 Fundamentals of 30
Computer Science Recursive Backtracking
 Goals of Backtracking
Possible goals
– Find a path to success
– Find all paths to success
– Find the best path to success
Not all problems are exactly alike, and
finding one success node may not be the
end of the search
Start
Success!

Success!

CS 307 Fundamentals of 31
Computer Science Recursive Backtracking
 The 8 Queens Problem

CS 307 Fundamentals of 32
Computer Science Recursive Backtracking
 The 8 Queens Problem
A classic chess puzzle
– Place 8 queen pieces on a chess board so that
none of them can attack one another

CS 307 Fundamentals of 33
Computer Science Recursive Backtracking
 The N Queens Problem
Place N Queens on an N by N chessboard so that
none of them can attack each other
Number of possible placements?
In 8 x 8
64 * 63 * 62 * 61 * 60 * 59 * 58 * 57
= 178,462, 987, 637, 760 / 8!
= 4,426,165,368

n choose k
– How many ways can you choose k things from a
set of n items?
– In this case there are 64 squares and we want to choose
8 of them to put queens on
CS 307 Fundamentals of 34
Computer Science Recursive Backtracking
 Attendance Question 2
For valid solutions how many queens can be
placed in a give column?
A. 0
B. 1
C. 2
D. 3
E. 4
F. Any number

CS 307 Fundamentals of 35
Computer Science Recursive Backtracking
 Reducing the Search Space
The previous calculation includes set ups like this
one Q
Q

Includes lots of set ups with Q

Q
multiple queens in the same Q
column Q
How many queens can there be Q
in one column? Q

Number of set ups

8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 = 16,777,216
We have reduced search space by two orders of
magnitude by applying some logic
CS 307 Fundamentals of 36
Computer Science Recursive Backtracking
 A Solution to 8 Queens
 If number of queens is fixed and I realize there can't be
more than one queen per column I can iterate through the
rows for each column
for(int c0 = 0; c0 < 8; c0++){
board[c0][0] = 'q';
for(int c1 = 0; c1 < 8; c1++){
board[c1][1] = 'q';
for(int c2 = 0; c2 < 8; c2++){
board[c2][2] = 'q';
// a little later
for(int c7 = 0; c7 < 8; c7++){
board[c7][7] = 'q';
if( queensAreSafe(board) )
printSolution(board);
board[c7][7] = ' '; //pick up queen
}
board[c6][6] = ' '; // pick up queen
CS 307 Fundamentals of 37
Computer Science Recursive Backtracking
 N Queens
The problem with N queens is you don't
know how many for loops to write.
Do the problem recursively
Write recursive code with class and demo
– show backtracking with breakpoint and
debugging option

CS 307 Fundamentals of 38
Computer Science Recursive Backtracking
 Recursive Backtracking
You must practice!!!
Learn to recognize problems that fit the
pattern
Is a kickoff method needed?
All solutions or a solution?
Reporting results and acting on results

CS 307 Fundamentals of 39
Computer Science Recursive Backtracking
 Another Backtracking Problem
A Simple Maze
Search maze until way
out is found. If no way
out possible report that.

CS 307 Fundamentals of 40
Computer Science Recursive Backtracking
 The Local View
Which way do
I go to get
out?
North
West
East

Behind me, to the South

CS 307 Fundamentals of
is a door leading South
41
Computer Science Recursive Backtracking
 Modified Backtracking
Algorithm for Maze
 If the current square is outside, return TRUE to indicate that a solution has been
found.
If the current square is marked, return FALSE to indicate that this path has been
tried.
Mark the current square.
for (each of the four compass directions)
{ if ( this direction is not blocked by a wall )
{ Move one step in the indicated direction from the current square.
Try to solve the maze from there by making a recursive call.
If this call shows the maze to be solvable, return TRUE to indicate that
fact.
}
}
Unmark the current square.
Return FALSE to indicate that none of the four directions led to a solution.

CS 307 Fundamentals of 42
Computer Science Recursive Backtracking
 Backtracking in Action
The crucial part of the
algorithm is the for loop
that takes us through the
alternatives from the current
square. Here we have moved
to the North.

for (dir = North; dir <= West; dir++)

{ if (!WallExists(pt, dir))
{if (SolveMaze(AdjacentPoint(pt, dir)))
return(TRUE);
}
CS 307 Fundamentals of 43
Computer Science Recursive Backtracking
 Backtracking in Action

Here we have moved

North again, but there is
a wall to the North .
East is also
blocked, so we try South.
That call discovers that
the square is marked, so
it just returns.

CS 307 Fundamentals of 44
Computer Science Recursive Backtracking
 So the next move we
can make is West.

Where is this leading?

CS 307 Fundamentals of 45
Computer Science Recursive Backtracking
 This path reaches
a dead end.

Time to backtrack!

Remember the
program stack!

CS 307 Fundamentals of 46
Computer Science Recursive Backtracking
 The recursive calls
end and return until
we find
ourselves back here.

CS 307 Fundamentals of 47
Computer Science Recursive Backtracking
 And now we try
South

CS 307 Fundamentals of 48
Computer Science Recursive Backtracking
 Path Eventually Found

CS 307 Fundamentals of 49
Computer Science Recursive Backtracking
 More Backtracking Problems

CS 307 Fundamentals of 50
Computer Science Recursive Backtracking
 Other Backtracking Problems
Knight's Tour
Regular Expressions
Knapsack problem / Exhaustive Search
– Filling a knapsack. Given a choice of items with
various weights and a limited carrying capacity
find the optimal load out. 50 lb. knapsack. items
are 1 40 lb, 1 32 lb. 2 22 lbs, 1 15 lb, 1 5 lb. A
greedy algorithm would choose the 40 lb item
first. Then the 5 lb. Load out = 45lb. Exhaustive
search 22 + 22 + 5 = 49.

CS 307 Fundamentals of 51
Computer Science Recursive Backtracking
 The CD problem
We want to put songs on a Compact Disc.
650MB CD and a bunch of songs of various
sizes.
If there are no more songs to consider return result
else{
Consider the next song in the list.
Try not adding it to the CD so far and use recursion to evaluate best
without it.
Try adding it to the CD, and use recursion to evaluate best with it
Whichever is better is returned as absolute best from here
}

CS 307 Fundamentals of 52
Computer Science Recursive Backtracking
 Another Backtracking Problem
Airlines give out frequent flier miles as a way to get
people to always fly on their airline.
Airlines also have partner airlines. Assume if you
have miles on one airline you can redeem those
miles on any of its partners.
Further assume if you can redeem miles on a
partner airline you can redeem miles on any of its
partners and so forth...
– Airlines don't usually allow this sort of thing.
Given a list of airlines and each airlines partners
determine if it is possible to redeem miles on a
given airline A on another airline B.
CS 307 Fundamentals of 53
Computer Science Recursive Backtracking
 Airline List – Part 1
 Delta
– partners: Air Canada, Aero Mexico, OceanAir
 United
– partners: Aria, Lufthansa, OceanAir, Quantas, British Airways
 Northwest
– partners: Air Alaska, BMI, Avolar, EVA Air
 Canjet
– partners: Girjet
 Air Canda
– partners: Areo Mexico, Delta, Air Alaska
 Aero Mexico
– partners: Delta, Air Canda, British Airways

CS 307 Fundamentals of 54
Computer Science Recursive Backtracking
 Airline List - Part 2
 Ocean Air
– partners: Delta, United, Quantas, Avolar
 AlohaAir
– partners: Quantas
 Aria
– partners: United, Lufthansa
 Lufthansa
– partners: United, Aria, EVA Air
 Quantas
– partners: United, OceanAir, AlohaAir
 BMI
– partners: Northwest, Avolar
 Maxair
– partners: Southwest, Girjet

CS 307 Fundamentals of 55
Computer Science Recursive Backtracking
 Airline List - Part 3
Girjet
– partners: Southwest, Canjet, Maxair
British Airways
– partners: United, Aero Mexico
Air Alaska
– partners: Northwest, Air Canada
Avolar
– partners: Northwest, Ocean Air, BMI
EVA Air
– partners: Northwest, Luftansa
Southwest
– partners: Girjet, Maxair
CS 307 Fundamentals of 56
Computer Science Recursive Backtracking
 Problem Example
 If I have miles on Northwest can I redeem them on Aria?
 Partial graph:

Ocean Air

BMI Avolar

Northwest

Air Alaska
EVA Air

CS 307 Fundamentals of 57
Computer Science Recursive Backtracking