The 8 Queens Problem
The 8 Queens Problem
With Pascal, Fortran and Lisp solutions
The 8 Queens Problem
The 8 Queens Problem is a common challenge given to first year computer science students.
On a chessboard (which is an 8x8 grid) there are a finite number of ways that 8 queens can be placed. If you don't know chess, a queen can move any number of spaces in any direction, horizontal, vertical and diagonal. There are 92 possible ways to place 8 queens on a standard 8x8 chessboard chessboard.
This was another one of my university assignments and is an example of a brute-force problem. There is no simple algorithm that can determine this — you just have to run through the combinations and check them all.
I originally wrote a solution to this in Pascal, for a computer algorithms class during my freshman year in March 1989.
This seems like one of the first programs I wrote using Personal Pascal on my Atari ST, which I had only just acquired back in January. Previously I had been using Kyan Pascal on my Atari 800XL and PCs with Turbo Pascal at school.
This is not a long program (less than 200 lines), so here it is in its entirety:
PROGRAM eight_queens_problem;
{ Eight Queens Solution by Paul Lefebvre 3-20-89
This program will find and display all 92 ways to place 8 queens on
a chessboard.
}
TYPE
row_type = ARRAY[1..8] OF BOOLEAN;
sum_type = ARRAY[2..16] OF BOOLEAN;
dif_type = ARRAY[-7..7] OF BOOLEAN;
pick_type = ARRAY[1..8] OF INTEGER;
VAR
rowchk : row_type; { Values contain TRUE if row unavailable }
diagsum : sum_type; { Values contain TRUE if daigonal unavailable }
diagdif : dif_type; { Values contain TRUE if diagonal unavailable }
picked : pick_type; { Contains the row number of each column }
i : INTEGER;
{ ---------------------------------------------------------------------- }
PROCEDURE display_solution(picked : pick_type; VAR solnum : INTEGER);
{ This procedure will display the solution that was found to the screen }
VAR
i, j : INTEGER;
BEGIN
solnum := solnum + 1; { Keep a running count of the solutions }
writeln; writeln;
{ This puts the actual chessboard on the screen }
FOR i := 1 TO 8 DO BEGIN
FOR j := 1 TO 8 DO
IF (picked[j] = i) THEN
write('Q ')
ELSE
write('+ ');
writeln
END;
writeln('That is solution number ',solnum)
END; { display_solution }
{ ---------------------------------------------------------------------- }
PROCEDURE back_up(VAR row, col : INTEGER; VAR rowchk : row_type;
VAR diagsum : sum_type; VAR diagdif : dif_type;
VAR picked : pick_type);
{ This procedure allows the computer to 'back up' if it comes to a dead
end. The computer is moved back one column and the marking variables are
set back to FALSE. The row position is moved up by one so that the
computer does not try the same position twice. If the row position is
already in the last one (8), then the procedure loops again to back
up another column. }
BEGIN
REPEAT
col := col - 1;
IF (col > 0) THEN BEGIN
row := picked[col];
picked[col] := 0;
rowchk[row] := FALSE;
diagsum[col+row] := FALSE;
diagdif[col-row] := FALSE;
IF (row < 8) THEN
row := row + 1
ELSE
row := 99
END
UNTIL (row <= 8) OR (col = 0)
END; { back_up }
{ ---------------------------------------------------------------------- }
PROCEDURE control_back_ups(VAR row, col : INTEGER; VAR rowchk : row_type;
VAR diagsum : sum_type; VAR diagdif : dif_type;
VAR picked : pick_type; VAR found : BOOLEAN;
VAR solnum : INTEGER);
{ This is the procedure that determines if a solution has been found or
if the computer is stuck and should back up. }
BEGIN
{ Solution found! }
IF (col = 8) AND found THEN BEGIN
display_solution(picked, solnum);
found := FALSE;
col := 9;
back_up(row, col, rowchk, diagsum, diagdif, picked)
END
ELSE
{ Solution not found, so back up }
IF (row > 8) THEN
back_up(row, col, rowchk, diagsum, diagdif, picked)
END; { control_back_ups }
{ ---------------------------------------------------------------------- }
PROCEDURE find_solutions(rowchk : row_type; diagsum : sum_type;
diagdif : dif_type; picked : pick_type);
{ This is the procedure that does the actual checking for a correct solution.
It will return to the main body only when all the solutions are found. }
VAR
found, done : BOOLEAN;
start, solnum, row, col : INTEGER;
BEGIN
start := 1;
picked[1] := start;
rowchk[start] := TRUE;
diagsum[1+start] := TRUE;
diagdif[1-start] := TRUE;
done := FALSE;
solnum := 0;
col := 2;
REPEAT
row := 1;
REPEAT
found := FALSE;
IF (col > 0) THEN BEGIN
IF (NOT rowchk[row]) AND (NOT diagsum[col+row]) AND
(NOT diagdif[col-row]) THEN BEGIN
found := TRUE;
rowchk[row] := TRUE;
diagsum[col+row] := TRUE;
diagdif[col-row] := TRUE;
picked[col] := row
END
ELSE
row := row + 1;
control_back_ups(row, col, rowchk, diagsum, diagdif, picked,
found, solnum)
END
ELSE BEGIN
found := TRUE;
done := TRUE
END
UNTIL found;
col := col + 1
UNTIL done
END; { find_solutions }
{ ====================================================================== }
BEGIN { Main body }
{ Make sure all the arrays are correctly initialized }
FOR i := 1 TO 8 DO BEGIN
rowchk[i] := FALSE;
picked[i] := 0
END;
FOR i := 2 TO 16 DO
diagsum[i] := FALSE;
FOR i := -7 TO 7 DO
diagdif[i] := FALSE;
writeln('Working ...');
writeln;
find_solutions(rowchk,diagsum,diagdif,picked);
writeln;
writeln('That''s all folks!') { Program takes approx. 41 seconds to get here }
END.Years later, I ported the program to a variety of other languages I was using at the time, including: HiSoft BASIC, GFA BASIC, C and Modula-2. These ports all largely use the same overall algorithm, just with changes for the different language syntax.
Fortran
My Dad did a Fortran conversion as that was a language he was using at work at the time. I find that it looks the weirdest:
C Eight Queens Problem
C
C Converted to Fortran by Larry Lefebvre
C
C
INTEGER PICKED(8), I
C
LOGICAL ROWCHK(8), DIAGSUM(16), DIAGDIF(15)
C
DO 1000 I = 1,8,1
ROWCHK(I) = .FALSE.
PICKED(I) = 0
1000 CONTINUE
C
DO 1010 I = 1,16,1
DIAGSUM(I) = .FALSE.
1010 CONTINUE
C
DO 1020 I = 1,15,1
DIAGDIF(I) = .FALSE.
1020 CONTINUE
C
PRINT *,'Working ...'
PRINT *,' '
CALL FIND_SOLUTIONS (ROWCHK, DIAGSUM, DIAGDIF, PICKED)
PRINT *,' '
PRINT *,'Thats all folks!'
C
END
C
C
C
SUBROUTINE FIND_SOLUTIONS (ROWCHK, DIAGSUM, DIAGDIF, PICKED)
C
INTEGER PICKED(8), I
INTEGER START, SOLNUM, ROW, COL
C
LOGICAL ROWCHK(8), DIAGSUM(16), DIAGDIF(15)
LOGICAL FOUND, DONE
C
START = 1
SOLNUM = 0
COL = 2
PICKED(1) = START
ROWCHK(START) = .TRUE.
DIAGSUM(1+START) = .TRUE.
DIAGDIF(1-START+7) = .TRUE.
DONE = .FALSE.
C
9010 CONTINUE
ROW = 1
9000 CONTINUE
FOUND = .FALSE.
IF (COL .GT. 0) THEN
IF ((.NOT. ROWCHK(ROW)) .AND. (.NOT. DIAGSUM(COL+ROW))
+ .AND. (.NOT. DIAGDIF(COL-ROW+7))) THEN
PICKED(COL) = ROW
FOUND = .TRUE.
ROWCHK(ROW) = .TRUE.
DIAGSUM(COL+ROW) = .TRUE.
DIAGDIF(COL-ROW+7) = .TRUE.
ELSE
ROW = ROW + 1
ENDIF
CALL CONTROL_BACK_UPS (ROW, COL, ROWCHK, DIAGSUM,
+ DIAGDIF, PICKED, FOUND, SOLNUM)
ELSE
FOUND = .TRUE.
DONE = .TRUE.
ENDIF
IF (.NOT. FOUND) THEN
GOTO 9000
ENDIF
COL = COL + 1
IF (.NOT. DONE) THEN
GOTO 9010
ENDIF
C
RETURN
END
C
C
C
SUBROUTINE CONTROL_BACK_UPS (ROW, COL, ROWCHK, DIAGSUM,
+ DIAGDIF, PICKED, FOUND, SOLNUM)
C
INTEGER SOLNUM, ROW, COL, PICKED(8)
C
LOGICAL ROWCHK(8), DIAGSUM(16), DIAGDIF(15), FOUND
C
IF ((COL .EQ. 8) .AND. (FOUND)) THEN
CALL DISPLAY_SOLUTION (PICKED, SOLNUM)
COL = 9
FOUND = .FALSE.
CALL BACK_UP (ROW, COL, ROWCHK, DIAGSUM, DIAGDIF, PICKED)
ELSE IF (ROW .GT. 8) THEN
CALL BACK_UP (ROW, COL, ROWCHK, DIAGSUM, DIAGDIF, PICKED)
ENDIF
C
RETURN
END
C
C
C
SUBROUTINE DISPLAY_SOLUTION (PICKED, SOLNUM)
C
INTEGER PICKED(8), SOLNUM, I, J
C
CHARACTER * 17 LINEVAR
C
SOLNUM = SOLNUM + 1
LINEVAR = ' '
C
PRINT *,' '
PRINT *,' '
C
DO 1030 I = 1,8,1
DO 1040 J = 1,8,1
IF (PICKED(J) .EQ. I) THEN
LINEVAR((J*2)-1:(J*2)) = 'Q '
ELSE
LINEVAR((J*2)-1:(J*2)) = '+ '
ENDIF
1040 CONTINUE
PRINT *,LINEVAR
1030 CONTINUE
C
PRINT *,'That is solution number ',SOLNUM
C
RETURN
END
C
C
C
SUBROUTINE BACK_UP (ROW, COL, ROWCHK, DIAGSUM, DIAGDIF, PICKED)
C
INTEGER ROW, COL, PICKED(8)
C
LOGICAL ROWCHK(8), DIAGSUM(16), DIAGDIF(15)
C
9020 CONTINUE
COL = COL - 1
IF (COL .GT. 0) THEN
ROW = PICKED(COL)
PICKED(COL) = 0
ROWCHK(ROW) = .FALSE.
DIAGSUM(COL+ROW) = .FALSE.
DIAGDIF(COL-ROW+7) = .FALSE.
IF (ROW .LT. 8) THEN
ROW = ROW + 1
ELSE
ROW = 99
ENDIF
ENDIF
IF ((ROW .LE. 8) .OR. (COL .EQ. 0)) THEN
GOTO 9030
ELSE
GOTO 9020
ENDIF
9030 CONTINUE
C
RETURN
ENDI did end up taking a Fortran class at some point, but I don’t remember much about it.
Lisp
Another odd-looking version is Lisp, but it is also the shortest:
;
; Place n queens on a board
; See Winston and Horn Ch. 11
;
; Usage:
; (queens <n>)
; where <n> is an integer -- the size of the board - try (queens 4)
(defun cadar (x)
(car (cdr (car x))))
; Do two queens threaten each other ?
(defun threat (i j a b)
(or (equal i a) ;Same row
(equal j b) ;Same column
(equal (- i j) (- a b)) ;One diag.
(equal (+ i j) (+ a b)))) ;the other diagonal
; Is poistion (n,m) on the board safe for a queen ?
(defun conflict (n m board)
(cond ((null board) nil)
((threat n m (caar board) (cadar board)) t)
(t (conflict n m (cdr board)))))
; Place queens on a board of size SIZE
(defun queens (size)
(prog (n m board)
(setq board nil)
(setq n 1) ;Try the first row
loop-n
(setq m 1) ;Column 1
loop-m
(cond ((conflict n m board) (go un-do-m))) ;Check for conflict
(setq board (cons (list n m) board)) ; Add queen to board
(cond ((> (setq n (1+ n)) size) ; Placed N queens ?
(print (reverse board)))) ; Print config
(go loop-n) ; Next row which column?
un-do-n
(cond ((null board) (return 'Done)) ; Tried all possibilities
(t (setq m (cadar board)) ; No, Undo last queen placed
(setq n (caar board))
(setq board (cdr board))))
un-do-m
(cond ((> (setq m (1+ m)) size) ; Go try next column
(go un-do-n))
(t (go loop-m)))))As the comment indicates this is based on a problem in Lisp (Winston & Horn), Chapter 11. I’m not 100% sure that I wrote the queens function, but I did take and use Lisp in college, so I might have.
Many years later, after I started working at Xojo, I created a Xojo version based on the original Pascal program and it was included as one of the example projects for many years. Because 8Queens runs instantly on modern computers, the Xojo version is slowed down to graphically show how it solves the problem. Here’s an updated version:
Download 8Queens Source for Xojo
The rest of the 8Queens solutions that I wrote are available as part of the perks for Goto 10 paid members.
One of the many projects on my growing list of retrocomputing things to do is to get these old programming languages working on my Ataris and then to get 8Queens up and running in them.
I already have several programming languages working on my Atari Mega STE, but I have only just started getting things back up and running on my 130XE. In particular, I’d love to get a version of this working in Action! and Kyan Pascal.
If you’ve created a solution for 8Queens for other languages or computers, I’d love to see them. Please share in the comments.
The 8 Queens Problem
Not mine but very well documented: 8-queens for the HP42S calculator by Valentin Albillo, a legend in HP circles. https://albillo.hpcalc.org/articles/HP%20Article%20VA010%20-%20Long%20Live%20the%20HP42S.pdf