Every professional software developer is sure to have one of the great
books on algorithms close at hand, such as Knuth's mother-of-all-programming-references
Art of Computer Programming or Sedgewick's kinder, gentler (if considerably
less encyclopedic) Algorithms, Second Edition. This is as it should
be--books are tools too, and knowing where to look up a technique when it
is needed is a perfectly honorable alternative to brute-force memorization
and application of rules and recipes. Besides, our field, though young,
is already vast, and has progressed far beyond the point where it's feasible
for the average practitioner to master every one of its many subdivisions.
Unfortunately, the algorithm cook-book approach short-circuits one of programming's
most intense emotional rewards and certainly its most profound learning
experience: the analysis of an unfamiliar problem, the search for a solution,
the realization of the solution in code, and finally the satisfaction of
seeing the solution in use by others. Polya, a Stanford professor of mathematics
who died in 1985, recognized the enormous significance of finding one's
own answers. He set out to teach a problem-solving method, rather than a
set of solutions--a sort of systematic approach to invention--that would
heighten the interest of his students and serve their needs well in any
situation.
How to Solve It has a high name-recognition factor. I daresay almost
every serious programmer has at least heard of the book, and most have a
general idea of its theme. And I venture to say hardly any--other than those
who made their way into the computer field via a major in mathematics--have
ever actually held a copy in their hands, let alone read it. I believe this
to be true because none of the scores of references to the book I've heard
or seen over 20 years gave me any feeling for the book that matched the
book's true personality. And what is that personality?
First and foremost, you must remember that Polya was a mathematician, and
was not concerned with computers at all. As a matter of fact, when the book
was originally written in 1944, general-purpose computers as we know them
today didn't even exist. So How to Solve It is written from the point
of view of a mathematician teaching other mathematicians how to teach mathematics
to students, and the style of writing is an odd admixture--sometimes direct,
fluent, and a tad ironic; sometimes stuffy in a typically mathematical sort
of way, with carefully numbered lists; sometimes Socratic, with imaginary
dialogs between teacher and student; sometimes pedantic; and sometimes exasperatingly
quaint. Nevertheless, when all is said and done, the book lives up to its
reputation.
Polya's "method" has four main stages or elements, which may be
summarized as follows:
1. Understand the problem. What is the unknown? What is the data? What is the condition? Draw a figure. Introduce suitable notation.Having set forth this list in the very first few pages of his book, Polya proceeds to beat on the list repeatedly from every possible angle, using various examples, analogies, anecdotes, and even startlingly modern-sounding quotations from ancient philosophers. In short, he states and restates his thesis until he gets his points across, just as he encourages the reader to state and restate a problem until it has been massaged into a form more easily understood. His thought experiments are all mathematical, of course, but the mathematics are not complex and can be followed easily by anyone with a dim recollection of algebra and solid geometry; the most sophisticated mathematics in the book involve a simple differential.
2. Devise a plan. Find the connection between the data and the unknown. Have you seen the problem before? Do you know a related problem which has already been solved? Can you solve part of the problem? Can you restate the problem?
3. Carry out your plan. Check each step. Can you see clearly the step is correct? Can you prove it is correct?
4. Examine the solution obtained. Can you check the result? Can you check the argument? Can you derive the result differently? Can you see it at a glance? Can you use the result, or the method, for some other problem?
Only such problems come back improved whose solution we passionately desire, or for which we have worked with great tension; conscious effort and tension seem to be necessary to set the subconscious work going. At any rate, it would be too easy if it were not so; we could solve difficult problems just by sleeping and waiting for a bright idea. Past ages regarded a sudden good idea as an inspiration, a gift of the gods. You must deserve such a gift by work, or at least by a fervent wish.