In 1982, I went on a course and learnt to program in BASIC.
I read about the Eight Queens problem on p343 of Computer Science, A First Course, Second Edition. To solve it, you have to place eight queens on a chess board so that none of them can take any of the others. I wrote a Microsoft BASIC program to find all the solutions. In the mid 1980's, it took around 20 minutes to run on an ICL DRS multi-user microcomputer, even when nobody else was using it.
I found it again recently, printed on "pyjama paper". I also located a copy of GWBASIC on a 3.5” floppy disk, typed the program on my home PC and ran it. My PC is almost 10 years old but, even so, it executed the program in about a second. The source code and output are shown below. In case it isn’t obvious, if the program prints 1 5 8 6 3 7 2 4, that means that the queens go on squares a1, b5, c8, d6, e3, f7, g2 and h4.
I mentioned this problem to a colleague at work called Mukesh. He is keen on chess and worked out one possible answer by hand in around 5 minutes. I have put his name beside the solution he found.
10 REM EXAMPLE OF TREE PROCESSING
20 REM
30 REM PROGRAM TO WORK OUT ALL THE DIFFERENT WAYS
40 REM TO PUT 8 QUEENS ON A CHESS BOARD SO THAT
50 REM THEY CANNOT TAKE ONE ANOTHER
60 REM
70 OPEN "SOLUTION" FOR OUTPUT AS #1
80 DIM Q(8,3)
90 FOR J=1 TO 8
100 FOR K=1 TO 3
110 Q(J,K)=0
120 NEXT K
130 NEXT J
140 I=1
150 GOSUB 200
160 GOSUB 390
170 IF I>0 THEN 150
180 CLOSE 1
190 END
200 Q(I,1)=Q(I,1)+1
210 S=0
220 IF Q(I,1)>8 THEN 260
230 GOSUB 270
240 IF S=1 THEN 260
250 GOTO 220
260 RETURN
270 S=1
280 Q(I,2)=(Q(I,1)+I)-1
290 Q(I,3)=(8-Q(I,1))+I
300 IF I=1 THEN 380
310 FOR J=1 TO I-1
320 FOR K=1 TO 3
330 IF Q(J,K)=Q(I,K) THEN S=0
340 NEXT K
350 NEXT J
360 IF S=1 THEN 380
370 Q(I,1)=Q(I,1)+1
380 RETURN
390 IF S=1 THEN 450
400 Q(I,1)=0
410 Q(I,2)=0
420 Q(I,3)=0
430 I=I-1
440 GOTO 520
450 IF I<>8 THEN 510
460 FOR J=1 TO 8
470 PRINT #1,Q(J,1);
480 NEXT J
490 PRINT #1," "
500 GOTO 400
510 I=I+1
520 RETURN
1 5 8 6 3 7 2 4
1 6 8 3 7 4 2 5
1 7 4 6 8 2 5 3
1 7 5 8 2 4 6 3
2 4 6 8 3 1 7 5 <--- Mukesh's solution
2 5 7 1 3 8 6 4
2 5 7 4 1 8 6 3
2 6 1 7 4 8 3 5
2 6 8 3 1 4 7 5
2 7 3 6 8 5 1 4
2 7 5 8 1 4 6 3
2 8 6 1 3 5 7 4
3 1 7 5 8 2 4 6
3 5 2 8 1 7 4 6
3 5 2 8 6 4 7 1
3 5 7 1 4 2 8 6
3 5 8 4 1 7 2 6
3 6 2 5 8 1 7 4
3 6 2 7 1 4 8 5
3 6 2 7 5 1 8 4
3 6 4 1 8 5 7 2
3 6 4 2 8 5 7 1
3 6 8 1 4 7 5 2
3 6 8 1 5 7 2 4
3 6 8 2 4 1 7 5
3 7 2 8 5 1 4 6
3 7 2 8 6 4 1 5
3 8 4 7 1 6 2 5
4 1 5 8 2 7 3 6
4 1 5 8 6 3 7 2
4 2 5 8 6 1 3 7
4 2 7 3 6 8 1 5
4 2 7 3 6 8 5 1
4 2 7 5 1 8 6 3
4 2 8 5 7 1 3 6
4 2 8 6 1 3 5 7
4 6 1 5 2 8 3 7
4 6 8 2 7 1 3 5
4 6 8 3 1 7 5 2
4 7 1 8 5 2 6 3
4 7 3 8 2 5 1 6
4 7 5 2 6 1 3 8
4 7 5 3 1 6 8 2
4 8 1 3 6 2 7 5
4 8 1 5 7 2 6 3
4 8 5 3 1 7 2 6
5 1 4 6 8 2 7 3
5 1 8 4 2 7 3 6
5 1 8 6 3 7 2 4
5 2 4 6 8 3 1 7
5 2 4 7 3 8 6 1
5 2 6 1 7 4 8 3
5 2 8 1 4 7 3 6
5 3 1 6 8 2 4 7
5 3 1 7 2 8 6 4
5 3 8 4 7 1 6 2
5 7 1 3 8 6 4 2
5 7 1 4 2 8 6 3
5 7 2 4 8 1 3 6
5 7 2 6 3 1 4 8
5 7 2 6 3 1 8 4
5 7 4 1 3 8 6 2
5 8 4 1 3 6 2 7
5 8 4 1 7 2 6 3
6 1 5 2 8 3 7 4
6 2 7 1 3 5 8 4
6 2 7 1 4 8 5 3
6 3 1 7 5 8 2 4
6 3 1 8 4 2 7 5
6 3 1 8 5 2 4 7
6 3 5 7 1 4 2 8
6 3 5 8 1 4 2 7
6 3 7 2 4 8 1 5
6 3 7 2 8 5 1 4
6 3 7 4 1 8 2 5
6 4 1 5 8 2 7 3
6 4 2 8 5 7 1 3
6 4 7 1 3 5 2 8
6 4 7 1 8 2 5 3
6 8 2 4 1 7 5 3
7 1 3 8 6 4 2 5
7 2 4 1 8 5 3 6
7 2 6 3 1 4 8 5
7 3 1 6 8 5 2 4
7 3 8 2 5 1 6 4
7 4 2 5 8 1 3 6
7 4 2 8 6 1 3 5
7 5 3 1 6 8 2 4
8 2 4 1 7 5 3 6
8 2 5 3 1 7 4 6
8 3 1 6 2 5 7 4
8 4 1 3 6 2 7 5
No comments:
Post a Comment