Programming = Language + X

Suppose you are a beginner on the piano. You hear a piece of music that catches your fancy and borrow the score from the library. If the music is beyond your capabilities, you'll know soon enough: if not right away on turning the cover page, then before you get to the end of the first few bars.

In programming, it's different. There you can be busy for days or weeks, even months, learning the ins and outs of, say, Java and its libraries. Flushed with the illusion of power that all this knowledge brings, you come across something that catches your fancy, say, write a program that solves Sudoku puzzles. Wouldn't that be neat! Now that you know so much about this powerful and sophisticated programming language, what's going to stop you? Even after weeks of thrashing around, you may still not know what hit you.

Knowing the language is not enough

This was the state of a friend I wanted to help. How could I get the fact across that there is something to learn in programming beyond the language? Even independently of the language? In fact, I was trying to solve
"Programming = Language + X".
I scanned the books on my shelves, mainly the detritus of many visits by publishers' reps. I ended up not giving him any of these, because, every time I reached out, I realized that this was another book where the learning of some language was misleadingly intertwined with the X.

What are the other things you need to know? As a rule, programmers don't know, just as a pianist has no idea of all the things she's doing right. For something to change in this matter, something unusual needs to happen. In this case, the unusual thing was a great programmer accepting a job as a professor, being confronted with large classes of novices, and trying to teach them to program. One of the times this happened was in the 1960s and the professor was E.W. Dijkstra.

Dijkstra was not only an unusually effective programmer, but was unusual in trying to make explicit the problem-solving steps that he tended to race through unconsciously. He took some problems that were simple to explain, yet hard enough for his students to founder upon. For each of these he wrote down a complete route from problem statement to solution, trying not to skip a single step. A result of this exercise is "Notes on Structured Programming".

An example picked by Dijkstra

As soon as I remembered that it was from this paper that I learned a nifty algorithm for generating prime numbers, I knew what my friend needed. So, out from under the gifts from the publishers' reps, I pulled the book "Structured Programming" by O.-J. Dahl, E.W. Dijkstra, and C.A.R. Hoare; Academic Press 1972. This contains Dijkstra's paper. It first came out as a report, which I obtained by submitting to Google the query dijkstra "eight queens".

I found to my surprise that Dijkstra's paper also contains a treatment of the Eight-Queens problem. This is a simple search problem, simpler than the Sudoku-solving that my friend was struggling with. OK, I know: the Eighty-Queens problem is not a simple search problem, but here we're only trying to run Eight-Queens problem on a modern computer.

So I e-mailed him the following problem statement taken verbatim from Dijkstra's paper

"It is requested to make a program generating all configurations of eight queens on a chessboard of 8 by 8 squares such that no queen can take any of the others. This means that in the configurations sought, no two queens may be on the same row, on the same column, or on the same diagonal."
I suggested that he try this instead of Sudoku. My plan was to give him a copy of Dijkstra's story. Whatever degree of success my friend would have had, his attempt should have softened him up for Dijkstra's description of a problem-solving process.

As it happened, I did not hear from my friend again. Still my interest was piqued: Dijkstra was great on generating prime numbers, so what would he be like with Eight Queens? I only knew it as a program beloved by Prolog enthusiasts because it is supposed to demonstrate the power of built-in backtracking.

On the bus back from work I started reading Dijkstra's explanation. My mind kept wandering off. After a few stops I closed the book, and started to think. The bus is a good place to think; walking home afterwards is even better.

I have yet to get back to Dijkstra's explanation. In the meantime I think I have found a better one. Dijkstra was working with Algol 60, so did not have the help of built-in backtracking. My choice of programming language was C, so I was in the same situation. For me the process was a revelation, because the problem seemed to solve itself; at no point was I conscious of "coding backtracking". Anyway, backtracking is only a vague concept for me. I would have to work hard to even give a reasonably precise description of the process. But the step-by-step problem solving process that I followed leads to a simple program that does the job. Maybe it does backtracking; I don't know.

But of course it didn't matter that I could solve the problem. The issue here is to explain the mental operations involved to someone in whom these operations are not triggered automatically when confronted with the problem. Dijkstra followed a do-it-yourself approach to describing the operations, and so did I. Only when I was finished did something from the distant past come back.

Pólya on problem-solving

It turned out I had not only read, but still owned, a copy of the book "How To Solve It" by George Pólya, published in 1948.

Pólya was a mathematician and most of his examples in the book concern mathematical problems. But he also includes recreational puzzles and, indeed, the subtitle of the book is: "A System Of Thinking Which Can Help You Solve Any Problem". This makes one wonder whether the system can also help solve the problem of writing a program for the Eight-Queens problem.

I'll repeat here the very short outline of the book, so short that you'll find it on the inside front cover.

  1. Understanding the problem
    1. What is the unknown? What are the data? What is the condition?
    2. Is it possible to satisfy the condition? Is the condition sufficient to determine the unknown? Or is it insufficient? Or redundant? Or contradictory?
    3. Draw a figure. Introduce suitable notation.
    4. Separate the various parts of the condition. Can you write them down?
  2. Devising a plan
    1. Have you seen it before? Or have you seen the same problem in a slightly different form?
    2. Do you know a related problem? Do you know a theorem that could be useful?
    3. Look at the unknown! And try to think of a familiar problem having the same or a similar unknown.
    4. Here is a problem related to yours and solved before. Could you use it? Could you use its result? Could you use its method? Should you introduce some auxiliary element in order to make its use possible?
    5. Could you restate the problem? Could you restate it still differently? Go back to definitions.
    6. If you cannot solve the proposed problem, try to solve first some related problem. Could you imagine a more accessible related problem? A more general problem? A more special problem? An analogous problem? Could you solve a part of the problem? Keep only part of the condition, drop the other; how far is the unknown determined, how can it vary? Could you derive something useful from the data? Could you think of other data appropriate to determine the unknown? Could you change the unknown or the data, or both if necessary, so the new unknown and the new data are nearer to each other?
    7. Did you use all the data? Did you use the whole condition? Have you taken into account all essential notions involved in the problem?
  3. Carrying out the plan Carrying out your plan of the solution check each step. Can you see clearly that the step is correct? Can you prove it is correct?
  4. Looking back
    1. Can you check the result? Can you check the argument?
    2. Can you derive the result differently? Can you see it at a glance?
    3. Can you use the result, or the method, for some other problem?
This is the complete text of Pólya's outline. I was tempted to skip a lot, as it seemed to be slanted towards solving mathematical problems rather than the problem at hand. But it was good that I persevered, because more turned out to be relevant than seemed to be the case at first sight.

Object and Meta problem

An interesting feature of the problem at hand is that it is easy to confuse solving the Eight-Queens problem itself (the object problem) with the meta problem of writing a program that solves the Eight-Queens problem. One might think that we need not be concerned with methods for solving the object problem. But going over Pólya's checklist shows that it gives hints about how to solve the object problem that help with the meta problem.

Using the checklist for the object problem

Item 1.1 The data are the board as specified by the rules of chess, by the rule for attack by a queen, and by the fact that there are eight queens on the board. The unknown is a set of eight squares for putting queens on. The condition is that, with a queen on each of these squares, no queen attacks any other.

Item 1.2 It's funny that ours is apparently not a typical problem: these questions can only be answered by trying to solve the object problem, which we expect to leave to the program to be constructed. We happen to know that

  1. it is possible to satisfy the condition,
  2. the condition is not sufficient (there are 92 solutions)
  3. the conditions are not redundant
  4. the conditions are not contradictory (there is at least one solution).
Item 1.3 Not applicable here: a chessboard with eight tokens is even better than a figure.

Item 1.4 The condition that a queen attacks a piece can be separated as follows: the two have to be (1) in the same row, or (ii) in the same column, or (iii) on the same diagonal. The further condition that there cannot be any intervening piece is not relevant for this problem, as that intervening piece can only be a queen, which is then itself exposed to attack.

Item 2.5 Checklist item 2.5 is helpful. If a human is solving the object problem, then the existing formulation seems satisfactory. However, a program does not solve the object problem by handling chunks of plastic on a piece of cardboard. So restating the problem should be useful.

We can even restate the problem in such a way that the resulting problem is easier to solve by a computer program. It is fortunate that we came across 1.4 first, and separated the condition into three parts. The first part allows us to simplify the representation of a queen: as there can only be one queen in each row, and there are just enough rows for the queens, there has to be exactly one queen in each row. That suggests identifying each queen by the row in which it resides. For each row we only have to specify the column of the queen of that row. In this way the constraint of not being in the same row is automatically satisfied.

How would we now represent a solution? It is a sequence s of eight numbers, where s[i] is the column number of the queen in the i-th row. Two squares s[i] and s[j] with i not equal to j are on the same diagonal if and only if the absolute value of s[i]-s[j] is equal to the absolute value of i-j. So the figure of checklist item 1.3 comes in handy after all.

Even though we do not have to solve the object problem ourselves, it makes sense to know more about it and look for other hints that might be helpful. Item 2.6 suggests we solve part of the problem, perhaps in connection with dropping part of the condition.

The part to be dropped could be that we have to start solving the problem from scratch. We could consider the problem of completing a partial solution. where non-attacking queens have already been placed in the rows 0,...,i-1. That would leave us with the more promising problem of only placing the queen in row i in such a way that it is safe from the queens in rows 0,...,i-1. If this is not possible, then we have to look for another way of placing the first i queens. If it is possible, then we can continue completing the partial solution from a more advantageous starting point.

Using the checklist for the meta problem

Here we run into a difficulty right away with item 1.1: Understanding the Problem. The most interesting part of Pólya's work is his claim that the methods apply to solving problems in all areas, not just in mathematics. But even within mathematics, he has to go out of his way to argue that the methods apply both to proving and to constructing. Our meta problem is clearly one of constructing: namely, we have to construct a computer program.

But, what can the data possibly be? Do data ever make sense with a construction problem? Yes, consider a typical one, where one is to construct the perpendicular through a point P on a line l. Here the P and l are the data, the unknown is a line p, and the condition is that p goes through P and is perpendicular to l.

In the current problem, the unknown is a program. The condition is that it prints the eight column numbers that represent a solution to the Eight-Queens problem. It doesn't seem necessary to identify data. Just read on and see how the program gets written with help of some of the other hints by Pólya. It is OK to pick and choose from his list: it is a checklist, not an algorithm. Item 2.6 is promising, as it supposes we cannot solve the problem, and suggests we solve some other problem, an easier one, of course. That other problem had better be related, otherwise the solving would be an exercise in futility. But related in what way?

We noted that the Eight Queens problem can be solved by completing a partial solution that places mutually non-attacking queens in rows s[0],...,s[i-1]. For such a completion to be possible, two conditions need to be satisfied: