A rather long blast from the past about recursion elimination and a bit of complexity theory

While going through old papers, I found something I wrote as a follow-up to an article by Aaron Banerjee in the February 1999 issue of the world of 68’ micros (you can find a somewhat mangled version online here). Both concern recursion elimination, with the well-known “eight queens” problem (place eight queens on a chess board so that none attacks any other) as an example.

I don’t remember whether I submitted it, or whether it was printed. I’m also embarrassed by the barely legible layout—large Helvetica with nearly no leading. To let me toss the printout and keep the text, and to make it easier to read (if only by me), here it is again, with formatting help from LibreOffice and editing for clarity and concision, not to mention fixing bugs I caused by not directly copying and pasting source code. I will come back and fix indentation on the BASIC09 code, after a little experimentation.

Recursion Elimination and the Eight Queens Problem

In the February 1999 the world of 68’ micros, Aaron Banerjee discussed recursive algorithms and how to implement them in languages that don’t support recursion. The Fibonacci sequence has a closed form, and can be turned into an iterative form, but in general, recursion elimination requires an explicit stack that takes the place of the stack typically used to implement function calls. The stack holds state information about parts of the problem to be done later, and actually corresponds to the local variables in a recursive call. Like Mr. Banerjee, we will use the eight queens problem as an example, and in addition to recursion elimination, we’ll try to speed up the check for valid arrangements.

BASIC09, unlike Color BASIC, directly supports recursion and procedures with local variables—you have to go outside the language itself, e.g. with a data module, to get the effect of global variables. Instead of doing that, we’ll have a top-level function declare variables for things like the chess board to pass to the procedure that does the real work.

procedure main

dim row, col, nsols: integer; board(8, 8): boolean

for row := 1 to 8

for col := 1 to 8

board(row, col) := false

next col

next row

nsols := 0

run queen8(1, board, nsols)

print nsols; “ solutions”

end

The board array is boolean because we’re just putting queens on the board; each square either has one (true) or it doesn’t (false). The parameters of queen8 are

1. The column we’re about to try to put a queen in.
2. The board itself, which is updated as queens are placed on it or removed.
3. A count of the number of solutions we’ve seen so far; we added it to give a simple test. (A change from one run to another means we either broke something or fixed something.)

Our queen8 is turned around a bit from Mr. Banerjee’s. Rather than testing whether we have a full solution at entry (i.e. looking for col = 9), we check after placing a queen—it reduces the number of calls at the deepest level (and it means the test is for col = 8 rather than 9).

procedure queen8

param col: integer; board(8, 8): boolean; nsols: integer

dim row: integer; ok: boolean

for row := 1 to 8

run check(board, row, col, ok)

if ok then

board(row, col) := true

if col = 8 then

nsols := nsols + 1

run show(board)

else

run queen8(col + 1, board, nsols)

endif

board(row, col) := false

endif

next row

end

[Note from 2016: even if BASIC09 were in the optimization business, the call by reference would keep it from hoisting the evaluation of col = 8 out of the loop. We happen to know check won’t fiddle with col, so we could do it ourselves—but in a large program subject to change, that’s dangerous, and it can be easy to forget to write “run check(board, row + 0, col + 0, ok)” to force the issue. Given its constraints, call by reference was the way to go for BASIC09, but it’s not perfect.]

Now for the check procedure. Rather than iterating over each position to the “left” of the current column, we just look at the positions that can attack the tentatively-placed queen, which has the following advantages:

• It looks at at most three positions per column rather than eight.
• It can be done with one loop instead of two.
• If we only look at attacking positions, we need only check the board for true, rather than checking whether the position is attacking.

Alas, BASIC09 evaluates both operands of boolean operations, so it’s a bit clumsy.

[Note from 2016: unlike the first version of this article, I will stick with the BASIC09-imposed layout. My experience with the Go programming language and the layout that gofmt imposes, thereby avoiding the endless bikeshedding and arguing over layout that afflicts some other languages, makes me appreciate BASIC09’s having established a standard in that regard almost three decades earlier.]

procedure check

param board(8, 8): boolean; row, col: integer; result: boolean

dim delta: integer

result := true

for delta := 1 to col – 1

exitif board(row, col – delta) then

result := false

endexit

if delta < row then

exitif board(row – delta, col – delta) then

result := false

endexit

endif

if row + delta <= 8 then

exitif board(row + delta, col – delta) then

result := false

endexit

endif

next delta

end

The show procedure is straightforward. To assist the eye in judging the queens’ positions, we print guide lines.

procedure show

param board(8, 8): boolean

dim row, col: integer

for row := 1 to 8

for col := 1 to 8

if board(row, col) then

print “Q”;

else

print “ ”;

endif

if col < 8 then

print “|”;

endif

next col

print

if row < 8 then

print “-+-+-+-+-+-+-+-”

next row

print

end

Now that we’ve shown the canonical recursive version, let’s eliminate the recursion from queen8, replacing it with a stack. (Happily, we know how big to make the stack; the recursion happens once per column, and there are eight of them on a chess board.) At any stage, there is only one thing to remember, namely the row we’re on. If you think about it, you’ll realize that the stack pointer is always the same as the column we’re on, so there’s no need to save it on the stack as Mr. Banerjee’s code does. (We lucked out on this one; in general, you will have to save the information associated with a pending piece of the problem.) We keep the same interface for now—admittedly from the start we’ve been exposing details we shouldn’t, and we should have put a layer around the board initialization and outer call to queen8. For now, though, we’re concentrating on recursion elimination.

procedure queen8

param col: integer; board(8, 8): boolean; nsols: integer

dim row, rowstack(8): integer; ok: boolean

row := 0

loop

while row < 8 do

row := row + 1

run check(board, row, col, ok)

if ok then

board(row, col) := true

if col = 8 then

nsols := nsols + 1

run show(board)

board(row, col) := false

else

rowstack(col) := row

row := 0

col := col + 1

endif

endif

endwhile

exitif col = 1 then endexit

col := col – 1

row := rowstack(col)

board(row, col) := false

endloop

end

This is less clear than the recursive version, so explanation is in order. The while loop looks for the first row we haven’t tried yet for which we can safely place a queen in that row on the current column. If there is one, we put a queen there, remember the row, and either we’re completely done (on column eight) or we move on to the next column. If there isn’t one, we leave the loop because we’re done with the current column. If that’s the first column, we’re completely done (see the exitif); otherwise, we back up a column, remember the row we were on there, and remove the queen we had on that row and column, so we can try the next possibility for that column.

I’ve yet to run the program on a CoCo. On the MM/1a, the recursive and non-recursive versions both take about two minutes to run. Curiously, over half the time is taken by show! If the body of show is edited out, the result runs in fifty seconds. On the MM/1b (aka AT306), the program runs in 1:15—five eighths of the time—so the screen I/O on the MM/1 and MM/1a has significant overhead.

One can do other things to speed the program up, but the point here is to show recursion and recursion elimination in a language with decent control structures that clarify what’s happening… oh, what the heck. I did it anyway, so why not write it up?

The revised check still takes time proportional to the column number, and the column number ranges over 1 to n, where n = 8, in the fashion of bubble sort, so overall we’re talking O(n²). We haven’t changed its complexity, we just cut it down by a constant factor. To really speed it up we have to make check run in constant time, doing the same amount of stuff no matter what row or column we’re looking at. How much stuff? Well, there are three paths down which an attack can come, so there ought to be a way to just do three tests: one for the row, and one for each diagonal. (We never put more than one queen in a column, so nothing can get us from that direction.) The board is small enough that we could keep a row as an integer with one bit per column, making the board one-dimensional and a check for a row attack is just checking for a non-zero value for that row. OK, what about the diagonals?

They need an array each, one for those going up and one for those going down (from the POV of increasing column number). Each array has fifteen elements, because there are fifteen diagonals of each kind, one per endpoint with the minimum column number (don’t count the middle corner twice, like I almost did). We could keep a count of how many there are… but we don’t have to! This is the eight queens problem. We cut off the search at the first conflict, so the elements can be boolean. For that matter, we needn’t play bit games with the board. There can be at most one piece in each row. We could get away with boolean there, too, if we didn’t want to display the solutions, but we do, so we’ll keep the column number of the queen in that row, or zero if we haven’t put a queen in that row… but that makes “board” a less-than-suggestive name. Let’s call it “column” instead.

With those changes, here are the new main, queen8, and show. We’ll add a little timing info to main. check is simple, and doesn’t need guards—we’ll never fall off the end of an array—so we’ll “inline” it by hand, and not write it separately from queen8. [Note from 2016: the code here isn’t best practice. We’re concentrating on the algorithm and data. Best practice would be to define an abstraction of the chess board that lets you get a new empty board, lets you attempt to place a queen on a square and reports success (if the square isn’t under attack) or failure (if it is), and lets you remove a queen from a square. That would let us make this kind of change without disturbing main or queen8. Sadly, BASIC09’s type statement reveals the innards of the type it defines, making “information hiding” a bit of a sham.]

procedure main

dim diag, row, nsols, column(8): integer

dim udiag(15), ddiag(15): boolean

dim t0, t1: string[32]

for row := 1 to 8

column(row) := 0

next row

for diag := 1 to 15

udiag(diag) := false

ddiag(diag) := false

next diag

t0 := date$

nsols := 0

run queen8(1, column, udiag, ddiag, nsols)

t1 := date$

print nsols; “solutions”

print “start at “; t0; “, end at “; t1

end

procedure queen8

param col, column(8): integer; udiag(15), ddiag(15): boolean; nsols: integer

dim row: integer

for row := 1 to 8

if column(row) = 0 and udiag(row + col – 1) and ddiag(8 + row – col) then

column(row) := col

udiag(row + col – 1) := false

ddiag(8 + row – col) := false

if col = 8 then

nsols := nsols + 1

run show(column)

else

run queen8(col + 1, column, udiag, ddiag, nsols)

endif

column(row) := 0

udiag(row + col – 1) := true

ddiag(8 + row – col) := true

endif

next row

end

procedure show

param column(8): integer

dim row, qpos: integer; rowstring: string[16]

rowstring := “ | | | | | | | ”

for row := 1 to 8

qpos := 2 * column(row) – 1

print left$(rowstring, qpos – 1); “Q”; right$(rowstring, 15 – qpos)

if row < 8 then

print “-+-+-+-+-+-+-+-”

endif

next row

print

end

This version runs on the MM/1b in twenty-four seconds, about three times faster. Allen Huffman kindly ran it under a CoCo 3 emulator (using TuneUp, which would give it an advantage over stock OS-9). With sync lock turned on to make it run at CoCo speed, it ran in about two and a half minutes; without sync lock, it ran in twenty-eight seconds. Eliminating recursion only saved about three seconds on the MM/1b. I instrumented queen8, and it proved to only be called 1,965 times, less than I would’ve thought. Moral of this part of the story: choose your data structures carefully; it can make a big difference. (Note that it lets us easily print each row with a single statement rather than a character at a time. I suspect that makes a big difference in BASIC09.)

Having gone this far, we might as well write it in Color BASIC. This is a recursive version—it has recursive GOSUBs, which is as close as you can get in Color BASIC. It lacks the comments that Mr. Banerjee’s code has, and which production code should have (though they eat valuable memory in Color BASIC, so the temptation to eliminate them there is strong). On the other hand, it follows the BASIC09 version closely, so one could argue that the BASIC09 is documentation for the Color BASIC. To conserve writer and reader sanity,

• this is not crammed together the way Color BASIC code tends to be
• the text is in lower case

The first solution, running on an actual CoCo, takes about thirty-five seconds to appear, and a complete run takes, as nearly as I can tell, ten minutes and forty-five seconds. I would recommend running the progam in WIDTH 80 mode.

100 dim cl(8), rs(8), ud(15), dd(15),

110 r$=” ! ! ! ! ! ! ! “

120 for i=1 to 8:cl(i)=0:next

130 for I=1 to 15:ud(i)=1:dd(i)=1:next

140 ns=0

150 co=1

160 gosub 200

170 sound 50,3

180 print ns;”solutions”

190 end

200 for ro=1 to 8

210 if cl(ro)<>0 or ud(ro+co-1)=0 or dd(8+ro-co)=0 then 250

220 cl(ro)=co:ud(ro+co-1)=0:dd(8+ro-co)=0

230 if co=8 then ns=ns+1:gosub 300:else rs(co)=ro:co=co+1:gosub 200:co=co-1:ro=rs(co)

240 cl(ro)=0:ud(ro+co-1)=1:dd(8+ro-co)=1

250 next

260 return

300 cls

310 for rn=1 to 8

320 qp=2*cl(rn)-1

330 print left$(r$,qp-1);”Q”;right$(r$,15-qp)

340 if rn<8 then print “-+-+-+-+-+-+-+-”

350 next

360 return

Recursion is an important concept with many applications, not all of which have closed-form solutions. For example, consider plotting a function f on an interval [a,b] if all you can do on the display is draw line segments. Pick a point c in (a, b) and check whether (c, f(c)) is “close enough” to being on the line segment joining (a, f(a)) and (b, f(b)). If it is, draw that segment. Otherwise, recur on [a, c] and then on [c, b]. (Numerical methods students will recognize this as “adaptive trapezoidal integration”.) By all means, learn to use recursion, and learn how to avoid it or implement it via an explicit stack as Mr. Banerjee describes. [Note from 2016: It can come in handy for any language—for example, it is very common for embedded systems to flatly forbid recursion, whatever the language, for fear of stack overflow.]