From the point of view of logic programming, successively reducing the map by postponing countries with three or fewer neighbors is an example of a more general notion -- that of a postponable variable. A variable in the body of a clause is postponable if, no matter how the other variables are assigned, there is a value for this variable that causes all the goals involving that variable to be satisfied. Clearly any postponable variable can be postponed to the end. Moreover, just as in the map coloring problem, postponing some variables may remove enough goals involving other variables so that they in turn become postponable.
If there were only one stage of postponement, we could regard postponement as a case of selecting the first goal to be attempted, the postponable variables being rejected for selection. However, this wouldn't prevent the selection of a variable postponable in the second stage. Therefore, the postponement process should be completed before any goals are selected for attempt.
The postponability of a variable is expressed by a postponement lemma. For example, the postponability of R4 is expressed by the formula
Notice that our quick recognition of the postponability of R4 is based on the symmetry. We say that whatever colors are assigned to R2 and R3, a compatible color can be found for R4. We don't have to enumerate the possible assignements to R2 and R3. A program would have to do more work unless it also discovered or was told that coloring problems are invariant when the names of the colors are permuted.
We can imagine several combinations of programmer and computer effort in postponing variables. We already discussed the case in which the programmer himself re-ordered the goals in the clause. The other extreme is that the PROLOG compiler attempt to prove postponability lemmas. Since some cases of postponability may depend on some variables already having values, additional postponements can be accomplished by a suitable interpreter. Since most variables in most programs are not postponable, it seems wasteful to have the interpreter always try for postponement. Therefore, it is also possible for the user to specify that the compiler and/or run-time system look for postponable variables, perhaps by enclosing the clause or part of it within which postponable variables may be expected within a macro. Thus the above program might be written
The most powerful way of achieving postponement is for the programmer to use the full power of PROLOG to transform the body. Alain Colmerauer (1981) wrote such a program for rewriting the Pereira-Porto coloring program. If the programmer can arbitrarily rewrite the program, he may change the logic as well as the control. However, we can imagine that a restricted set of re-arrangement operators are used that is guaranteed to only affect the control.
I was informed by Hervé Gallaire that the system for specifying control described in (Gallaire 1981) could not express the postponement heuristic for the coloring problem, but that a small modification to the system would make it possible.