Let me just make some comments on the basic backtracking
approach. You will find the very same ideas in 8-Queens
and in the Knapsack problem. I have added comments to
the skeleton: you can see the real method below. Note
that you don't see all details in all problems. We needed
to 'remove queen' in the 8-queens, while that wasn't
needed in Knapsack or in this problem. In the Knapsack
method we gave you, we never recorded the solution.
That is addressed in the dynamic programming version
in the lecture notes, and could be added to the basic
Knapsack function as well.
I've included another backtracking example to look at.
The problem is to write an integer as the sum of 4 squares.
This is always possible, and makes a simple example.
Below you will find three versions
General Backtracking framework
Walk through the squares problem.
Real solution to the squares problem.
The third solution is much like the second, but
the comments are more terse. There are also some
ideas on how to speed up the solution.
static boolean
backtracking(some parameters)
{
// Are we done? then return true
// Have we no hope? then return false
// Try each 'position' in turn
for (first position to last postion)
{
If (this looks like a legal postion)
// Can I use this step and solve the rest of
the problem?
if (backtracking(parameters modified to
reflect my position))
{
remember my position
return true;
}
else
remove any traces of my position and try again
in the next iteration of the loop
}
// If I reach here, I was not successful
return false;
}
Pseudo code for the problem of 4 squares
// Returns
// Boolean - were we able to find a solution?
// Input
// value - integer we wish to express as the sum of squares
// num - number of integers we have to work with.
static boolean
tryslow(int value, int num)
{
// Logic to deal with base cases:
// Are we done?
if (value == 0) return true;
// Have we no hope?
if (num == 0) return false;
// Now start at the begining (1*1) work up
// trying each square in turn.
// Starting at 1*1, try 1, 4, 9, 16, etc
for (int i = 1; i*i <= value; i++)
{
int sq = i*i;
// How does this help us solve the problem?
// Rather than trying to represent 'value', we
// only need to represent 'value - i*i'
// Note that we have one less square to work with
if (tryslow (value-sq, num-1))
{
// If we suceeded, record the result and return true
System.out.print(" " + sq);
return true;
}
}
// None of the squares worked. Try again.
return false;
}
Real code for 4 squares, and some ideas on how to speed up the
solution to this problem. The speedups are not shown below.
// warring.java
//
// Every positive integer can be expressed as the sum of four squares.
// Thus 7 = 4 + 1 + 1 + 1
//
// This program uses backtracking to discover such a sum for the first
// 200 numbers
// The initial attempt solves the problem starting with 1*1, then 2*2, etc
// We use two techniques to speed up the backtracking
// 1st Rather than start with 1*1, we start with the largest square
// less than or equal to the number. This is almost 40
times faster
// 2nd We make the second recursive call stop searching when the square
// is less than a third of the remainder, and make the second call
// stop when the square is less than half the remainder. This
// is about twice as fast.
//
....
// tryslow
//
// The slowest of the three methods. Start at 1 and work up.
// Returns
// Boolean - were we able to find a solution
// Input
// value - integer we wish to express as the sum of squares
// num - number of integers we have to work with.
static boolean
tryslow(int value, int num)
{
if (value == 0)
return true; // Are we done?
// Base case: we have no more numbers to work with
if (num == 0)
return false;
// Start at 1 and work up
for (int i = 1; i*i <= value; i++)
{
int sq = i*i; // Place guess
if (tryslow (value-sq, num-1))
{
System.out.print(" " + sq);
return true;
}
}
return false; // Nothing worked. Backtrack
}
- jeff parker
