' Knight's tour
DECLARE FUNCTION ChooseMove% (X1 AS INTEGER, Y1 AS INTEGER)
DECLARE SUB TryMove (BYVAL X AS INTEGER, BYVAL Y AS INTEGER, M AS INTEGER, NewX AS INTEGER, NewY AS INTEGER)
DECLARE FUNCTION ValidMove% (X AS INTEGER, Y AS INTEGER)

RANDOMIZE TIMER
CONST TRUE% = -1, FALSE% = 0

SCREEN 7
WINDOW (1, 1)-(512, 512)
COLOR 15, 0 ' white foreground, black background
DIM X AS INTEGER, Y AS INTEGER, Total AS INTEGER
DIM SX AS INTEGER, SY AS INTEGER, SW AS INTEGER
DIM Board(0 TO 7, 0 TO 7) AS INTEGER
SW = 512 \ 8
FOR X = 0 TO 6 STEP 2
  SX = X * SW
  FOR Y = 0 TO 6 STEP 2
    SY = Y * SW
    'filled boxes
    LINE (SX + SW, SY + SW)-(SX + 2 * SW, SY + 2 * SW), , BF
    LINE (SX, SY)-(SX + SW, SY + SW), , BF
  NEXT Y
NEXT X

X = 0
Y = 0
Board(X, Y) = TRUE%
PSET (X * SW + SW \ 2, Y * SW + SW \ 2), 12
Total = 1
DO WHILE ChooseMove%(X, Y)
  Board(X, Y) = TRUE%
  LINE -(X * SW + SW \ 2, Y * SW + SW \ 2), 12
  Total = Total + 1
LOOP
IF Total <> 64 THEN STOP
END

FUNCTION ChooseMove% (X1 AS INTEGER, Y1 AS INTEGER)
' X1, Y1 are returned
  DIM M AS INTEGER, NewX AS INTEGER, NewY AS INTEGER
  M = 9
  CALL TryMove(X1 + 1, Y1 + 2, M, NewX, NewY)
  CALL TryMove(X1 + 1, Y1 - 2, M, NewX, NewY)
  CALL TryMove(X1 - 1, Y1 + 2, M, NewX, NewY)
  CALL TryMove(X1 - 1, Y1 - 2, M, NewX, NewY)
  CALL TryMove(X1 + 2, Y1 + 1, M, NewX, NewY)
  CALL TryMove(X1 + 2, Y1 - 1, M, NewX, NewY)
  CALL TryMove(X1 - 2, Y1 + 1, M, NewX, NewY)
  CALL TryMove(X1 - 2, Y1 - 1, M, NewX, NewY)
  IF M = 9 THEN
    ChooseMove% = FALSE%
  ELSE
    X1 = NewX
    Y1 = NewY
    ChooseMove% = TRUE%
  END IF
END FUNCTION

SUB TryMove (BYVAL X AS INTEGER, BYVAL Y AS INTEGER, M AS INTEGER, NewX AS INTEGER, NewY AS INTEGER)
' M, NewX, NewY are returned
  N = 0
  IF ValidMove%(X, Y) THEN
    IF ValidMove%(X + 1, Y + 2) THEN N = N + 1
    IF ValidMove%(X + 1, Y - 2) THEN N = N + 1
    IF ValidMove%(X - 1, Y + 2) THEN N = N + 1
    IF ValidMove%(X - 1, Y - 2) THEN N = N + 1
    IF ValidMove%(X + 2, Y + 1) THEN N = N + 1
    IF ValidMove%(X + 2, Y - 1) THEN N = N + 1
    IF ValidMove%(X - 2, Y + 1) THEN N = N + 1
    IF ValidMove%(X - 2, Y - 1) THEN N = N + 1
    IF (N < M) OR (N = M AND RND >= .5) THEN
      M = N
      NewX = X
      NewY = Y
    END IF
  END IF
END SUB

FUNCTION ValidMove% (X AS INTEGER, Y AS INTEGER)
  SHARED Board() AS INTEGER
  IF X < 0 OR X > 7 OR Y < 0 OR Y > 7 THEN
    ValidMove% = FALSE%
  ELSE
    ValidMove% = NOT (Board(X, Y))
  END IF
END FUNCTION