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