The Eight Queens Problem

Type
Education
Category
Puzzle solver (backtracking search with a live display)
Author
Angelo Giambra
Published in
Antic, April 1985 (Vol. 3, No. 12)
Year
1985
Language
Atari BASIC
Requirements
24K RAM with cassette or 32K with disk (according to the magazine), Atari BASIC
A red and black chessboard with five white queen symbols placed in the first five rows, above a text window reading EIGHT QUEENS PROBLEM

About the program

The Eight Queens Problem is an old chess puzzle: place eight queens on a chessboard so that none of them can attack another. A queen attacks any distance along a row, column or diagonal. Antic challenged its readers to find all 92 solutions by hand ("It shouldn't have taken more than a few hours to find at least three"), and then offered this program to let the Atari do the work.

Angelo Giambra, a technical analyst from Buffalo, New York, who normally worked on mainframes in COBOL and ALGOL, called the method "brute computing". The program tries every possibility in an orderly way, and you can watch it place queens and back out of the moves that don't work. He compared it to the route-planning software that trucking firms used to compare every possible route. The article ended with a challenge: change the program so that it finds only the 12 unique solutions (the others are rotations or reflections of these). In September 1985 Antic printed Dave Oblad's answer, an Action! program that found all 92 in about 40 seconds and the 12 unique ones in 30.

Typing it in

Line 220 contains screen-control characters inside the quotes: {CLEAR} (ESC then SHIFT-CLEAR), {DOWN} (ESC then CTRL-=) and {TAB} (ESC then TAB). Line 280 uses {UP} (ESC then CTRL-−). Everything else is plain text. The magazine printed TYPO II codes for checking.

How to use it

RUN it and type a starting position from 1 to 8. That is the column for the first queen in the top row. The board appears and the search begins. When a solution is found, the screen flashes and shows SOLUTION and its number. Press any key to look for the next one. If you start at 1 you see all 92, ending with DONE.

How it works

  • Backtracking. COL(ROW) is the column being tried in each row, and A(,) marks where queens stand. Lines 30–40 test the column above, and lines 60–120 walk the four diagonals using step values worked out with logical expressions. If the square is safe, the queen is placed and the program moves to the next row. If a row runs out of columns, line 160 takes back the queen in the row above and moves it along one square.
  • A chessboard made of players. The squares are player/missile graphics. Line 340 DIMs a 2,048-byte string, PL$, and rounds its address up to a 1K boundary for PMBASE. The players then live inside the string, and string assignments draw the board: bytes of 240 and 15 alternate down the four players to make the checks, and the missiles, filled solid, form the edges. POKE 623,20 puts the playfield in front of the players, so the queens show on top.
  • The queen. Lines 380–410 copy the ROM font to RAM and replace the ! character with a crown shape (DATA line 390). Line 140 just prints ! in GRAPHICS 2.

Listing

5 REM THE EIGHT QUEENS PROBLEM
6 REM BY ANGELO GIAMBRA
7 REM ANTIC MAGAZINE
10 GOTO 210
20 IF COL(ROW)>8 THEN 160
30 FOR I=1 TO 8:IF A(I,COL(ROW))=1 THEN STARTOVER=1:I=8
40 NEXT I
50 IF STARTOVER THEN STARTOVER=0:COL(ROW)=COL(ROW)+1:GOTO 20
60 FOR CT=1 TO 4
70 INC=(CT=1 OR CT=2)*-1+(CT=3 OR CT=4):INC1=(CT=1 OR CT=4)*-1+(CT=2 OR CT=3)
80 X=ROW+INC:Y=COL(ROW)+INC1:IF X<1 OR X>8 OR Y<1 OR Y>8 THEN 120
90 IF A(X,Y)=1 THEN STARTOVER=1:GOTO 50
100 X=X+INC:Y=Y+INC1:IF X<1 OR X>8 OR Y<1 OR Y>8 THEN 120
110 GOTO 90
120 NEXT CT
130 A(ROW,COL(ROW))=1:COLOR 1:SOUND 0,50,10,10
140 T=COL(ROW)+5:Q=ROW:POSITION T,Q:? #6;"!":SOUND 0,0,0,0:ROW=ROW+1:IF ROW=9 THEN 280
150 COL(ROW)=1:GOTO 30
160 ROW=ROW-1:A(ROW,COL(ROW))=0:SOUND 0,100,10,8
170 COLOR 0:T=COL(ROW)+5:Q=ROW:POSITION T,Q:? #6;" ":SOUND 0,0,0,0
180 COL(ROW)=COL(ROW)+1:IF COL(ROW)=9 AND ROW=1 THEN 320
190 IF COL(ROW)=9 THEN 160
200 GOTO 30
210 DIM A(8,8),COL(8),C(8,8)
220 ? "{CLEAR}{DOWN}{DOWN}{DOWN}{DOWN}{TAB}STARTING POSITION (1-8)";:INPUT C
230 OPEN #1,4,0,"K":X=1:COLOR 1
240 FOR I=1 TO 8:FOR Z=1 TO 8:A(I,Z)=0:NEXT Z:NEXT I
250 FOR I=1 TO 8:COL(I)=I:NEXT I:COL(1)=C
260 GOSUB 340
270 ROW=1:S=0:GOTO 130
280 S=S+1:? "            SOLUTION ";S:? "           PRESS ANY KEY{UP}"
290 FOR I=1 TO 10:SETCOLOR 4,15,4:FOR Z=1 TO 10:SOUND 0,Z*2,10,10:SOUND 1,Z*10,10,10:NEXT Z
300 SETCOLOR 4,0,0:FOR Z=1 TO 10:NEXT Z:NEXT I:SOUND 0,0,0,0:SOUND 1,0,0,0
310 GET #1,CH:? "                        {UP}{UP}":GOTO 160
320 ? "{DOWN}               DONE     "
330 GOTO 330
340 DIM X$(1),PL$(2048):PL$(1)=CHR$(0):PL$(2048)=CHR$(0):PL$(2)=PL$:A=ADR(PL$):PMBASE=INT(A/1024)*1024
350 IF PMBASE<A THEN PMBASE=PMBASE+1024
360 S=PMBASE-A+1:POKE 106,144:POKE 106,PEEK(106)-4
370 POKE 106,PEEK(106)-16:GRAPHICS 2:POKE 704,34:POKE 705,34:POKE 710,0:POKE 709,0:POKE 710,40:POKE 559,0
380 POKE 752,1:? "       EIGHT QUEENS PROBLEM":POKE 756,PEEK(106):Z=PEEK(106)*256
390 DATA 85,85,127,28,28,127
400 FOR I=57344 TO 57344+512:POKE Z,PEEK(I):Z=Z+1:NEXT I:Z=PEEK(106)*256+9
410 FOR I=1 TO 6:READ A:POKE Z,A:Z=Z+1:NEXT I
420 POKE 706,34:POKE 707,34:POKE 53248,96:POKE 53249,112:POKE 53250,128:POKE 53251,144
430 FOR I=408 TO 471:PL$(S+I,S+I)=CHR$(255):NEXT I
440 X1=63:X$=CHR$(240):X=535:GOSUB 500:X=663:GOSUB 500:X=791:GOSUB 500:X=919:GOSUB 500
450 X1=55:X$=CHR$(15):X=543:GOSUB 500:X=671:GOSUB 500:X=799:GOSUB 500:X=927:GOSUB 500
460 POKE 53277,3:POKE 54279,PMBASE/256
470 FOR I=0 TO 3:POKE 53256+I,1:NEXT I:POKE 559,46
480 POKE 53252,95:POKE 53253,161:POKE 711,34:POKE 623,20
490 RETURN
500 FOR I=X TO X+X1 STEP 16:FOR D=1 TO 8:PL$(S+I+D,S+I+D)=X$:NEXT D:NEXT I:IF X1=63 THEN PL$(S+X)=CHR$(255)
510 PL$(S+X+X1+1,S+X+X1+1)=CHR$(255):RETURN

Download

The original program from the Antic disk, to LOAD or ENTER instead of typing it: QUEENS8.BAS.

Credits