Backtracking

By
Riaz Ahmad
COMSATS WAH CANTT

A short list of categories

Algorithm types we will consider include:

Simple recursive algorithms

Backtracking algorithms
Divide and conquer algorithms
Dynamic programming algorithms
Greedy algorithms
Branch and bound algorithms
Brute force algorithms
Randomized algorithms

Backtracking (animation)
dead end
?
dead end

start

dead end

dead end
dead end

?
success!

Backtracking

Suppose you have to make a series of decisions,

among various choices, where

You dont 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 find one
that works
4

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 dont 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

Backtracking Algorithm

Based on depth-first recursive search

Approach
1.
2.
3.

Tests whether solution has been found

If found solution, return it
Else for each choice that can be made
a)
b)
c)

4.

Make that choice

Recur
If recursion returns a solution, return it

If no choices remain, return failure

Some times called search tree

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

Backtracking Algorithm Example

Find path through maze

Start at beginning of maze

If at exit, return true
Else for each step from current location

Recursively find path

Return with first successful step
Return false if all steps fail

Consider a maze

Solving a maze
where a player has to decide how to get from room A to room B.
The player can move from room to room through the corridors provided,
but has no way of telling how many corridors a room is connected to until he
reaches that room.
the approach the player uses to solve the maze could be like this:
The player moves from room A to room 2.
From here he can move either to rooms 1 or 3. He chooses 1.
Dead End. He returns to room 2, then goes on to room 3.
He has no choice but to move to room 4.
Given a choice between rooms 5 and 6, he chooses 6.
Another choice between 7 and 8, he chooses 7.
Dead End. He returns to 6 and chooses 8.
Dead End again. He returns to 6 and sees that he has exhausted his choices.
He goes back to room 4, and chooses room 5.
He sees room B, moves to it, and solves the maze.

10

Pseudo code which implements the algorithm

We will now examine some described above.
function CheckRoom(RoomNumber)
begin
if RoomNumber has been visited, return.
for each room connected to this room
if ConnectedRoomNumber == B, the maze has been solved
else CheckRoom(ConnectedRoomNumber)
end for
end function
That's all! The algorithm takes care of rooms with Dead Ends,
rooms with multiple corridors, and anything you care to throw at
it. It has the elegant simplicity characteristic of all recursive
procedures, but it differs slightly from the functions we have
studied previously. It is a backtracking algorithm.
11

How Backtracking works

The sample maze, like all mazes, is essentially a tree, with room A at the root of the
tree.
the backtracking algorithm discussed above is a tree-spanning algorithm. When it
reaches a node like room 2, where it has more than one path to choose from, it picks
one path (to room 1) which is a leaf node, or Dead End. Finding that it can proceed no
more, it unwinds to it's previous execution, (back to room 2) and takes the other path,
to room 3. Such an algorithm is known as a depth-first spanning algorithm, because it
tends to follow a path right down to the bottom of the tree, before it gives up and
unwinds to a previous execution in order to choose a different path. Manually apply the
CheckRoom function above to the tree to get a feel of how the algorithm works.
Backtracking procedures are characterized by multiple recursive calls, typically within
a loop (see the CheckRoom function above).
a backtracking procedure goes through multiple winding and unwinding stages as it
loops through the choices it has to make at every node. One of the most common
applications of backtracking is in the evaluation of moves for strategy games like chess.
We will look at a much simpler game, tic-tac-toe, and see how a backtracking strategy
can be used to ensure that we can never lose the game.

12

How Backtracking works

The maze as a tree

13

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 dont 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

14

Backtracking Algorithm Example

Color a map with no more than four colors

If all countries have been colored return success

Else for each color c of four colors and country n

If country n is not adjacent to a country that has been colored c

Color country n with color c
Recursively color country n+1
If successful, return success

Return failure

15

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

16

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 adjacent to

country 5 is country 8
17

Creating the map

0

int map[][];
void createMap() {
map = new int[7][];
map[0] = new int[] {
map[1] = new int[] {
map[2] = new int[] {
map[3] = new int[] {
map[4] = new int[] {
map[5] = new int[] {
map[6] = new int[] {
}

1
4

2 3
5

1,
0,
0,
2,
0,
2,
2,

4,
4,
4,
4,
1,
6,
3,

2, 5 };
6, 5 };
3, 6, 5 };
6 };
6, 3, 2 };
1, 0 };
4, 1, 5 };
18

Setting the initial colors

static
static
static
static
static

final
final
final
final
final

int
int
int
int
int

NONE = 0;
RED = 1;
YELLOW = 2;
GREEN = 3;
BLUE = 4;

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

NONE, NONE, NONE };

19

The main program

(The name of the enclosing class is ColoredMap)
public static void main(String args[]) {
ColoredMap m = new ColoredMap();
m.createMap();
boolean result = m.explore(0, RED);
System.out.println(result);
m.printMap();
}

20

The backtracking method

boolean explore(int country, int color) {
if (country >= map.length) 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;
}
21

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;
}

22

Printing the results

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

23

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 dont 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

24

What is searching?
If you want to go from Point A to Point B, you are employing
some kind of search. For a direction finder, going from Point A to
Point B literally means finding a path between where you are
now and your intended destination.
For a chess game, Point A to Point B might be two points
between its current position and its position 5 moves from now.
Searching falls under Artificial Intelligence (AI). A major goal of
AI is to give computers the ability to think, or in other words,
mimic human behavior. The problem is, unfortunately, computers
don't function in the same way our minds do. They require a
series of well-reasoned out steps before finding a solution. Your
goal, then, is to take a complicated task and convert it into
simpler steps that your computer can handle.

25

Search representation
First, we need a representation of how our search problem will
exist. The following is an example of our search tree

In our above graph, the path connections are not two-way. All
paths go only from top to bottom
26

Depth First Search

Depth first search works by taking a node, checking its

neighbors, expanding the first node it finds among the
neighbors, checking if that expanded node is our
destination, and if not, continue exploring more nodes.

27

Pseudo code / Informal Algorithms (Depth First Search)

Declare two empty lists: Open and Closed.
Add Start node to our Open list.
While our Open list is not empty, loop the following:

Remove the first node from our Open List.

Check to see if the removed node is our destination.

If the removed node is our destination, break out of the loop, add the
node to our Closed list, and return the value of our Closed list.
If the removed node is not our destination, continue the loop (go to Step
c).

Extract the neighbors of our above removed node.

Add the neighbors to the beginning of our Open list, and add the
removed node to our Closed list. Continue looping.

28

Steps in Depth First Search

Step 0
Let's start with our root/goal node:
I will be using two lists to keep track of what we are
doing - an Open list and a Closed List. An Open list
keeps track of what you need to do, and the Closed List
keeps track of what you have already done.
Open List: A
Closed List: <empty>

29

Step 1

Now, let's explore the neighbors of our A node. To put

another way, let's take the first item from our Open list
and explore its neighbors:
Node A's neighbors are the B and C nodes. Because we
are now done with our A node, we can remove it from
our Open list and add it to our Closed List.
You now have two new nodes B and C that need
exploring.
Add those two nodes to our Open list.
Open List: B, C
Closed List: A
30

Steps 2

Our Open list contains two items. For depth first search and
breadth first search, you always explore the first item from our
Open list. The first item in our Open list is the B node. B is not
our destination, so let's explore its neighbors:

Because I have now expanded B, I am going to remove it from

the Open list and add it to the Closed List. Our new nodes are D
and E, and we add these nodes to the beginning of our Open list:
Open List: D, E, C
Closed List: A, B

31

Step3

You should start to see a pattern forming. Because D is

at the beginning of our Open List, we expand it. D isn't
our destination, and it does not contain any neighbors.
All you do in this step is remove D from our Open List
and add it to our Closed List:
Open List: E, C
Closed List: A, B, D

32

Step 4

We now expand the E node from our Open list. E is not our destination, so we
explore its neighbors and find out that it contains the neighbors F and G.
Remember, F is our target, but we don't stop here though. Despite F being on
our path, we only end when we are about to expand our target Node - F in this
case:

Our Open list will have the E node removed and the F and G nodes added. The
removed E node will be added to our Closed List:
Open List: F, G, C
Closed List: A, B, D, E

33

Step 5

We now expand the F node. Since it is our intended destination, we stop:

We remove F from our Open list and add it to our Closed List. Since we are at
our destination, there is no need to expand F in order to find its neighbors. Our
final Open and Closed Lists contain the following data:
Open List: G, C
Closed List: A, B, D, E, F
The final path taken by our depth first search method is what the final value of
our Closed List is: A, B, D, E, F

34

Breadth First Search

Depth and Breadth first search methods are covered in
the same Lecture is because they are both similar. In
depth first search, newly explored nodes were added to
the beginning of your Open list. In breadth first search,
newly explored nodes are added to the end of your
Open list.

35

Pseudo code / Informal Algorithms ( breadth First

Search)
Declare two empty lists: Open and Closed.
Add Start node to our Open list.
While our Open list is not empty, loop the following:

Remove the first node from our Open List.

Check to see if the removed node is our destination.

If the removed node is our destination, break out of the loop, add the node to
our Closed list, and return the value of our Closed list.
If the removed node is not our destination, continue the loop (go to Step c).

Extract the neighbors of our above removed node.

Add the neighbors to the end of our Open list, and add the removed node
to our Closed list.

36