A Summary of the Barnes-Butterfield War In all innocence, we wrote a short YOU CAN SO RECURSE IN AMIGA BASIC article in Vol. III, No. 2, to de- AND, monstrate recursion for an Amigan INSIGHTS INTO THE FOLLIES who asked what it involved. In that OF BRUTE FORCE RECURSION article, we said you can't "use re- cursion" in Amiga Basic. Not long after, a letter arrived, addressed to "The Hater and Vilifier of Amiga Basic, PO Box 411..." The Postmistress handed it to us and said, "Better tone down what- ever it is you're writing, Dick. We're getting tired of checking the hate-mail for letter bombs." (Most of the hate mail arrives from software houses who fail to appreciate our comments on their programs). But this wasn't hate mail. In his usual calm, precise way, Jim Butterfield told us we could recurse in Amiga Basic with GOSUB, and demonstrated how. He also up- held the honor and utility of that language with many a good example. Last, he warned that brute force recursion on a knight's tour of a full 8 x 8 board might require half of forever. We replied at length, expounding upon the many virtues of True Basic, and objecting that GOSUB did not allow passage of arguments dur- ing recursion. (This began as a "my language is better than your language" sort of thing, from which both of us soon had the good sense to desist.)< One rainy afternoon, in about two hours, we wrote a simple True Basic program to demonstrate recursion in action as the program attempted to solve a 4 x 4 board. We sent it to Jim because it was short and showed graphically each recur- sive move. We also sent a copy to old master Terry Peterson in California, and asked if he could adapt it to A/C Basic (the compiled version), for, if memory served, A/C Basic could accept recursive subroutine calls with arguments.< Terry Peterson responded first, with a much-improved recursive version of our program, in A/C Basic, which ran about twice as fast as ours did. It showed that A/C Basic indeed recursed with efficiency and speed. Okay, Basic wins the first battle of the war. Then Jim wrote a thoughtful letter, noting the overwhelming follies of plain, brute-force recursion. Following are a few of his ideas, which we demonstrate on a 5 x 5 board: 1 0 3 8 0 `MISSED CORNERS:`Only two ways into and out of a corner 0 13 6 0 4 exist. If you you use one to get there, you must use 0 2 9 12 7 the other to leave. At left, the moves around the upper 0 11 0 5 0 right corner ignore the rule. Move 13 could make the 0 0 0 10 0 corner, but leave no way out. When such corners don't fill properly, a recursive program wastes an enormous amount of time to learn that the board can't be solved until it backs off and makes the appropriate moves into and out of each corner. (Yes, a 5 x 5 board can be solved). 1 6 3 12 9 `TRAPS at MISSED SQUARES:`At left sit two blank squares, 4 11 8 0 0 in positions 5 and 6, row 2. Move 14 made it impossible 7 2 5 10 13 for either to be reached; move 15 blocks the knight ut- 0 15 0 0 0 terly. As you watch a knight move recursively, you can 0 0 0 14 0 see these traps develop. There are two obvious mechanical solutions: 1) develop algorithms able to fill corners with logic, and 2) to look ahead and avoid the traps at missed squares. No one, so far as we know, has written such routines. Indeed, there's no assur- rance that they'd be faster than brute force recursion. `Jim Butterfield, with his usual ingenuity,`asked why the viewer can't intervene when these obvious problems develop. He wrote two programs in Amiga Basic which let you intervene at will, back off to a specific move, and try again. We find ourselves fascinated, as we use Jim's programs, with learning how to look at a board and back off to a move that'll unblock a board and let the knight proceed. Both are written for full 8 x 8 boards (Jim told us that REAL MEN do not horse around with 4 x 4 boards, even for demos. We've been eating quiche ever since.)< The war was not without its lighter moments. Jim conceived a grand scheme based on symmetry. "Aha," he said, "a search to depth of 64 is a great time waster. With symmetry, could this not be reduced to 16? If I could find a pattern of 16 moves that took me from upper-left to upper-right, I could iterate these moves (rotatated 90 degrees) to get to lower-right, etc. It wasn't hard to code, but I wondered why no useful solutions appeared. Then it struck me! THERE CAN BE NO POSSIBLE SOLUTION! Proof: On each move, a knight moves to a square of oppos- ite color. Each two-move pair, the knight returns to to the original color. Af- ter 16 moves, the knight must be on the same color it started. But--upper left and upper right corners have opposite colors! There is no way 16 moves can get from one to the other. Reductio ad absurdum. Groan..." Jim adds, "Can we do a 32-move sequence that repeats, upper left to lower right? It takes more time than you might think, and again is helped by manual interven- tion." `Doug Jones of Atlantic Highlands`also sent us a recursive tour in C; it works (swiftly!) on boards from 4 x 4 to 8 x 8. It states "no answer" to a 4 x 4 board in 16 seconds, solves a 5 x 5 board in less than 1 second, solves a 6 x 6 board in 9 minutes 45 seconds, and (suprise!) finds a solution to a 7 x 7 in 6:35. It prints a blue and white checkerboard on screen, and shows recursion by move num- ber on the board (it's pretty swift at that). We set it up this morning on our A-1000 with nothing else running, looking for a solution to an 8 x 8 board...< `The Object of our Exercise in Recursion`is to demonstrate how it works. Those who want to see it in both source code and action will find all the programs on Amigan PD Disk 21. Terry Peterson placed the A/C version in the runtime package so that anyone can run it. The A/C Basic programs--as well as Jim's--graphically represent the board for each move; the effect of recursion is plain as the nose on an elephant. The source code for Doug Jones' C program is an excellent demo in that language, although the recursive work is graphically so swift it's al- most impossible to follow. `Some numbers will make the weaknesses in brute force recursion come alive.`We ran both A/C Basic and True Basic on 8 x 8 boards for over half a billion iter- ations without finding a solution. With manual intervention, one can find a sol- ution to an 8 x 8 board with Jim's program and no practice in less than a hour. The weakness in a brute force approach is amply demonstrated by Doug Jones' pro- gram in C. We kicked it off on an 8 x 8 board at 11:59 on Friday morning, and at 23:59 had to shut it down--still not solved. Jim's comments about the stupidity of brute force recursion were amply demonstrated here. The move sequence at the left appeared shortly after 1 p.m. on the lower-left hand corner of 13 4 the board. The program spent the next ten hours on recursive moves 0 19 higher than and beyond this obvious failure. In time, it would have backtracked down the recursive road and filled the corner. But--in how many more hours (or days)? Brute force recursion on complex problems, as Jim said at the beginning, demands either clever auxiliary algorithms or manual in- tervention--or both. If you want to understand recursion and how it works, its weaknesses and strengths, you can do no better than read and run the programs issued on PD Disk 21.