Books / Introduction to Recursion and Backtracking / Chapter 11
Backtracking Example - The Sum of Four Squares
LaGrange’s 4-squares theorem states that any natural number can be written as the sum of four squares (including 0 if need be.) Suppose we wanted an algorithm that, given any natural number, could find four squares whose sum equals the number. Backtracking can do this. The idea is to pick a square less than the number, subtract it, and then find three numbers that add up to the difference. If we succeed, then we found the four numbers. If we do not, then we back up to the first number we picked and try a different first number. We can proceed by picking the smallest first number first, or by picking the largest first number first. Either way we can proceed methodically. The algorithm below picks the smallest number first.
int tryout_solution(int number, int num_squares) {
int i;
if (number == 0) {
// If number == 0 it can be written as the sum of however many 0's we
// need so we have succeeded .
return true;
}
// assert: number > 0
if (num_squares == 0)
// If we reach here, since number > 0 and we have used up our quota of
// four squares, we could not find 4 square s whose sum is number
return false;
// try to find a number i such that i * i is less than number
// if we do , then subtract i * i from the number and recursively
// do the same thing for number−i * i with one less square than before.
// if one particular i fails, we try the next i . This is the backtracking part
for (i = 1; i * i <= number; i++) {
int square = i * i;
if (tryout_solution(number− square, num_squares− 1)) {
printf(" %d", square);
if (num_squares < 4)
printf(" + ");
return true;
}
}
return false;
}
The above function would be called with an initial value of 4 for the second parameter, num_squares
, as in:
if (tryout_solution(value, 4))
printf(" = %d\n", value);
The function attempts to find num_squares
squares that sum to number
. If number is zero, it is trivial to
satisfy so it returns true
. Since each recursive call diminishes num_squares
, it is possible that it is zero.
If number
is not zero but num_squares
is zero, it means that it has run out of chances - it has used four
squares but their sum is not the original number, so it returns false. Otherwise there is still hope - for
each square less than number
, it calls tryout_solution(number-square, num_squares-1)
, hoping that
one of those squares will result in tryout_solution()
returning true
. If it does, it means that it found
the remaining squares and that square
is one of the squares that add up to number
. It prints the value
of square
(with a ‘+’ after if need be), and returns to the calling function. If the main program is named
find_lagrange_squares
, the output could look like:
$ find_lagrange_squares 2000
1764 + 196 + 36 + 4 = 2000