Quite BASIC -- Eight Queens - Classic Chess Puzzle

Output
Canvas
BASIC Program

REM Eight Queens Project (conflict heuristics search) 
REM Quite BASIC Puzzle Project
REM ------------------------ 
CLS
PRINT "This is a heuristic search solution to the eight queens puzzle.  The program first places one queen on each row on a random column.  Then it repeatedly moves the queen with the most conflicts to another column with the least possible conflicts.  After moving a number of queens around without finding a solution, the program will restart from a random placement."
LET A = 0
REM C is the array of queens 
REM Example: C[5-1] = 4-1 means a queen in the 5th row, 4th column
ARRAY C
REM Q is a representation of the board
REM Q[(5-1)*8 + (4-1)] = 3 means that the square at the 5th row, 4th column, can be reached by three different queens
ARRAY Q
REM Reset the board
GOSUB 4000
LET N = 0
LET A = A + 1
REM Place all queens randomly
FOR R = 0 TO 7
LET Z = 1
LET K = ROUND(RAND(7) + 0.5)
LET C[R] = K
GOSUB 5000
NEXT R
REM Main iteration loop
REM First find the worst row R
LET M = 0
FOR R = 0 TO 7
LET E = Q[R*8 + C[R]] 
IF E = M AND RAND(1) > 0.5 THEN GOTO 2280
IF E <= M THEN GOTO 2280
LET M = E
LET X = R
NEXT R
GOSUB 7000
REM A value of 1 means no conflicts
IF M = 1 THEN END
REM Remove the worst queen from the board
LET R = X
LET K = C[R]
LET Z = -1
GOSUB 5000
REM Find best K to put a queen back on row R
LET M = 10
FOR K = 0 TO 7
LET E = Q[R*8 + K]
IF E = M AND RAND(1) > 0.5 THEN GOTO 2450
IF E > M THEN GOTO 2450
LET M = E
LET X = K
NEXT K
REM Place a queen at the best K
LET K = X
LET Z = 1
GOSUB 5000
LET C[R] = K
REM Increase the iterations counter and draw the board
LET N = N + 1
REM Either start a new iteration or give up and start a new attempt
IF N = 10 THEN GOTO 2090 ELSE GOTO 2190
REM Subroutine: Clear the board
FOR I = 0 TO 63
LET Q[I] = 0
NEXT I
RETURN
REM Subroutine: Add / Remove a Queen
REM Position (R, K) 
REM Z = 1 for adding and Z = -1 for removing
FOR I = 0 TO 7
REM Update the row
LET Q[8*R+I] = Q[8*R+I] + Z
REM Update the column
LET Q[8*I+K] = Q[8*I+K] + Z
NEXT I
LET Q[8*R+K] = Q[8*R+K] - Z
REM Update the first diagonal
LET U = K
LET V = R
LET U = U + 1
LET V = V + 1
IF U = 8 OR V = 8 THEN GOTO 5160
LET Q[V*8+U] = Q[V*8+U] + Z
GOTO 5110
LET U = K
LET V = R
LET U = U - 1
LET V = V - 1
IF U < 0 OR V < 0 THEN GOTO 5230
LET Q[V*8+U] = Q[V*8+U] + Z
GOTO 5180
REM Update the second diagonal
LET U = K
LET V = R
LET U = U + 1
LET V = V - 1
IF U = 8 OR V < 0 THEN GOTO 5310
LET Q[V*8+U] = Q[V*8+U] + Z
GOTO 5260
LET U = K
LET V = R
LET U = U - 1
LET V = V + 1
IF U < 0 OR V = 8 THEN GOTO 5380
LET Q[V*8+U] = Q[V*8+U] + Z
GOTO 5330
RETURN
REM Subroutine: Draw Queens
CLS
LET G = 0
FOR I = 0 TO 7
LET E = Q[I*8+C[I]]
LET G = G + E 
IF E > 1 THEN PLOT I, C[I], "red" ELSE  PLOT I, C[I], "green"
NEXT I
PRINT "Attempt: ";
PRINT A
PRINT "Iteration: ";
PRINT N
PRINT "Conflicts: ";
PRINT (G - 8) / 2
RETURN
      
  
Controls
Line:
Expr:
Value:
>QUITE BASIC
>

fun and learning for smart kids

nostalgia for the rest of us

>QUITE BASIC>

fun and learning for smart kids

nostalgia for the rest of us

>QUITE BASIC
>
