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 t
he 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
-
The
column we’re about to try to put a queen in.
-
The
board itself, which is updated as queens are placed on it or
removed.
-
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(n2).
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,
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.]
