REM Eight Queens Problem
REM in HiSoft BASIC 1.23
REM 10-12-92
REM by Paul Lefebvre

DIM rowchk%(8),diagsum%(16),diagdif%(15),picked%(8)
'
DIM SHARED TRUE%, FALSE%

TRUE%=-1 : FALSE%=0
FOR i%=1 TO 8
  rowchk%(i%)=FALSE%
  picked%(i%)=0
NEXT i%
FOR i%=1 TO 16
  diagsum%(i%)=FALSE%
NEXT i%
FOR i%=0 TO 15
  diagdif%(i%)=FALSE%
NEXT i%
PRINT "Working ..."
PRINT
find_solutions rowchk%(),diagsum%(),diagdif%(),picked%()
PRINT
PRINT "That's all folks!"
END
SUB display_solution(picked%(8), solnum%)
  LOCAL i%,j%
  INCR solnum%
  PRINT
  PRINT
  FOR i%=1 TO 8
    FOR j%=1 TO 8
      IF (picked%(j%)=i%) THEN
        PRINT "Q ";
      ELSE
        PRINT "+ ";
      END IF
    NEXT j%
    PRINT
  NEXT i%
  '
  PRINT "That is solution number ";solnum%
END SUB

SUB back_up(row%,col%,rowchk%(8),diagsum%(16),diagdif%(15),picked%(8))
  DO
    DECR col%
    IF (col%>0) THEN
      row%=picked%(col%)
      picked%(col%)=0
      rowchk%(row%)=FALSE%
      diagsum%(col%+row%)=FALSE%
      diagdif%(col%-row%+7)=FALSE%
      IF row%<8 THEN
        INCR row%
      ELSE
        row%=99
      END IF
    END IF
  LOOP UNTIL (row%<=8) OR (col%=0)
END SUB
 
SUB control_back_ups(row%,col%,rowchk%(8),diagsum%(16),diagdif%(15),picked%(8),found%,solnum%)
  IF (col%=8) AND found% THEN
    display_solution picked%(),solnum%
    found%=FALSE%
    col%=9
    back_up row%,col%,rowchk%(),diagsum%(),diagdif%(),picked%()
  ELSE
    IF (row%>8) THEN
      back_up row%,col%,rowchk%(),diagsum%(),diagdif%(),picked%()
    END IF
  END IF
END SUB
 
SUB find_solutions(rowchk%(8),diagsum%(16),diagdif%(15),picked%(8))
  LOCAL found%,done%,start%,solnum%,row%,col%
  start%=1
  picked%(1)=start%
  rowchk%(start%)=TRUE%
  diagsum%(1+start%)=TRUE%
  diagdif%(1-start%+7)=TRUE%
  done%=FALSE%
  solnum%=0
  col%=2
  DO
    row%=1
    DO
      found%=FALSE%
      IF (col%>0) THEN
        IF (NOT rowchk%(row%)) AND (NOT diagsum%(col%+row%)) AND (NOT diagdif%(col%-row%+7)) THEN
          found%=TRUE%
          rowchk%(row%)=TRUE%
          diagsum%(col%+row%)=TRUE%
          diagdif%(col%-row%+7)=TRUE%
          picked%(col%)=row%
        ELSE
          INCR row%
        END IF
        control_back_ups row%,col%,rowchk%(),diagsum%(),diagdif%(),picked%(),found%,solnum%
      ELSE
        found%=TRUE%
        done%=TRUE%
      END IF
    LOOP UNTIL found%
    INCR col%
  LOOP UNTIL done%
END SUB