56 lines
1.6 KiB
Plaintext
56 lines
1.6 KiB
Plaintext
100 REM N-QUEENS PROBLEM IN CBM BASIC 2
|
|
110 NQ = 8: GOSUB 200: IF A THEN NQ=A
|
|
120 PRINT CHR$(147) "SOLVING FOR" NQ "QUEENS"
|
|
130 DIM B(NQ), C(NQ), R(NQ):REM BOARD, COLUMN, ROW
|
|
140 SP = 0: REM STACK POINTER
|
|
150 TI$ = "000000": REM RESET TIMER
|
|
160 R(SP) = 0: SP = SP + 1: GOSUB 500: SP = SP - 1:REM PLACE.QUEEN(0)
|
|
170 PRINT "FOUND" SC "SOLUTIONS IN" TI / 60 "SECONDS"
|
|
180 END
|
|
190 REM
|
|
200 REM PARSE COMMAND-LINE ARGUMENT
|
|
210 P = 512
|
|
220 C = PEEK(P): P = P + 1: IF C <> 0 THEN 220
|
|
230 C = PEEK(P): P = P + 1: IF C = 78 THEN 290
|
|
240 A = 0
|
|
250 IF C = 0 THEN 290
|
|
260 IF C < 48 OR C > 57 THEN PRINT "USAGE: RUN:<NUMQUEENS>": END
|
|
270 A = A * 10 + C - 48
|
|
280 C = PEEK(P): P = P + 1: GOTO 250
|
|
290 RETURN
|
|
295 REM
|
|
300 REM COULD.PLACE(ROW, COL): BOOL
|
|
310 CP = -1
|
|
320 R = R(SP - 1): IF R = 0 THEN RETURN
|
|
330 C = C(SP - 1)
|
|
340 FOR I = 0 TO R - 1
|
|
350 : IF B(I) = C OR B(I) - I = C - R OR B(I) + I = C + R THEN CP = 0
|
|
360 : IF CP = 0 THEN I = R - 1
|
|
370 NEXT I
|
|
380 RETURN
|
|
390 REM
|
|
400 REM PRINT.SOLUTION
|
|
410 SC = SC + 1: PRINT CHR$(19) CHR$(17) CHR$(17) "FOUND SOLUTION" SC CHR$(13)
|
|
420 FOR I=0 TO NQ - 1
|
|
430 : PRINT " ";
|
|
440 : IF B(I) THEN N=B(I):CH=46:GOSUB 600
|
|
450 : PRINT "Q";
|
|
460 : IF B(I) < NQ - 1 THEN N=NQ - 1 - B(I):CH=46:GOSUB 600
|
|
470 : PRINT
|
|
480 NEXT I
|
|
490 PRINT: RETURN
|
|
495 REM PLACE.QUEEN(ROW)
|
|
500 IF R(SP - 1) = NQ THEN GOSUB 400: RETURN
|
|
510 C(SP - 1) = 0
|
|
520 IF C(SP - 1) = NQ THEN 590
|
|
530 GOSUB 300: IF CP = 0 THEN 570
|
|
540 B(R(SP - 1)) = C(SP - 1)
|
|
550 R(SP) = R(SP - 1) + 1: SP = SP + 1:GOSUB 500: SP = SP - 1
|
|
560 B(R(SP - 1)) = 0
|
|
570 C(SP - 1) = C(SP - 1) + 1
|
|
580 GOTO 520
|
|
590 RETURN
|
|
600 REM PRINT A CHARACTER N TIMES
|
|
610 FOR QQ=1 TO N:PRINT CHR$(CH);:NEXT
|
|
620 RETURN
|