Letters

Dr. Dobb's Journal September, 2004

Backtracking Algorithms

Dear DDJ,

In regard to Timothy Rolfe's article "Backtracking Algorithms" (DDJ, May 2004), I found another discard rule to insert in the algorithm, doing the first algorithm (Cloque.java) as good (or better) than the second one (FacePerm.java).

This new rule sums the complement of the numbers used, then divides by 3 (to get the triplets) the numbers left, then this result divides the sum, thus if the last result is bigger than the allowed value, it discards the rest. For instance, assume we are calculating 12 numbers and 21 as boundary if we are beginning our search having 1, 2, and 3 at the first positions face[0,1,2], we can sum and the complement will be 72 then divide the numbers left 9 by 3 (always three because it is a triplet —>9/3=3) then this new result divides 72 —>72/3=24. If this number is bigger than the allowed (21 in this example) we can discard the rest of permutations because we'll always get an over number.

The following code was inserted in the check method making the program more effective:

// true/false only to enter or not to this // new check (optimization)
if ( true )
{ total = 0;
for(idx=0; idx<=posn; idx++)
total += face[idx];
total = size*(size+1)/2 - total;
if ( total/((size-posn)/3D) > maxTot )
return false;
}

The new performance is:

Numbers Limit Calls-Original Calls-New
12 21 2,168,123 637,269
13 22 8,092,606 549,160
13 23 18,990,336 5,486,228
14 24 77,374,157 8,199,708
15 25 308,576,798 4,829,667

The new Cloque is similar to FacePerm in performance with the examples shown, but if you try 16 and 27 as numbers and limit, respectively, on my computer (PIII 500-MHz, 256 MB), the results are: Cloque, 52,265 secs; FacePerm, 72,204 secs.

German Gonzalez-Morris

German.Gonzalezbritishcouncil.cl

Dear DDJ,

Regarding my article "Backtracking Algorithms" (DDJ, May 2004), Paul Purdom of Indiana University, Bloomington made the following observation clock face permutation backtracking:

There is one simple test you can add to your code that should make it much faster yet.
Suppose you have assigned numbers to the clock face for positions 1 to k, but have not yet assigned numbers for positions k+1 to N. You have the following situation:
X[k-1] X[k] X[k+1] ... X[N] X[1] X[2]
known known unknown ... unknown known known
You also know that the sum of each three numbers should be no more than MaxSum, and you have Nk+2 groups of unknown sums-of-three.
Let R be the sum of the numbers not yet assigned. Then X[k-1] appears in one group-of-three, X[k] appears in two groups, each X contributing to R appears in three groups, X[1] appears in two groups, and X[2] appears in one group. Thus, we need:
(N-k+2)MaxSum>=X[k-1]+2X[k]+3R+2X[1]+X[2].

This, indeed, massively reduces the number of function calls and the time required to solve the problem. For instance, using the straight backtracking implementation in Java took 19.44 hours to discover that a clock face of 20 entries has 506 cyclic permutations with a maximum sum of 33. Doing the same thing after adding the bound that Professor Purdom provided, the program required was only 13.85 seconds. 5.3E+11 function calls got trimmed down to 7.0E+04.

Timothy Rolfe

TRolfeewu.edu

C, as in Duct Tape

Dear DDJ,

I've been writing code (mostly in C) for the past 20 years and I'd like to comment on some of the points in Jerry Pournelle's February 2004 column.

• Strong type/range checking can prevent buffer overflows. This is true, and wonderful when a program runs in a veritable vacuum, like a spreadsheet that takes user input directly and read/writes its own files. It is also nearly true when a program communicates with a known partner for known purposes. Unfortunately, in the world of the Internet, one can rarely be assured that the program on the other end will always be the correct one or even the correct version of the correct program. That means programs must be able to handle unexpected buffer lengths and sometimes must be able to determine the data type of incoming data after it is read—very, very difficult in strongly typed languages. Yes, better hardware can speed up the necessary hoop jumping, but a loosely typed language can easily adjust on the fly to new data types, at least when coded correctly.
• Shooting feet. I once heard (from a fellow at DEC) this comment about programming in C: "We provide the gun and bullets, you provide the foot." However, as most sane people know, just because you can do a thing, doesn't mean you should do that thing!
• C's "near unreadability." When I was learning C, the guys in my shop called it a "write-only language" because it was so hard to guess what another person meant by reading their code. However, that was just an excuse for writing poorly commented code that made use of every possible syntactical shortcut combined with lousy formatting. When I was given the opportunity (at my next job) to set the coding-style guidelines, things were much better... For the past 10 years, I've been coercing the other programmers to follow my style guidelines and none of us ever have trouble following each other's code. Even customers who have purchased source licenses use our source as self training because it is easier to understand than many samples on the MSDN CD!
• Other languages. You missed good old Ada in your list! I had to learn that while I was in the U.S. Air Force (in 1986, when the first validated compilers were becoming available) and I think it would've been a very good choice, too. Based on tests at the time, it was almost always true that a program developed in Ada was done once it would compile. Very few bugs were ever found after a compile completed successfully. On the other hand, there's an old joke that may bear repeating here: "REAL PROGRAMMER's can write Fortran in any language!" And my personal corollary: "Most programmers (or at least, people who call themselves programmers) write bad code in every language (even English or their native tongue)."

I think of C as kind of like Duct tape—very flexible, easy to get something small done very quickly, great for a very wide number of jobs. But would anyone want to fly in an airplane made entirely out of Duct tape?

Steve Valliere

svallie-visions.com

DDJ