Knight’s Tour

This program solves the Knight’s Tour problem, finding a path for a chess knight to visit every square on an adjustable board (up to 8×8) exactly once. It uses a backtracking algorithm implemented in BASIC, storing the knight’s path in a two-dimensional array `s(e,3)` where each entry holds the row, column, and move index at each step. The board is rendered as a grid using repeated string slicing on fixed 8-column ruler and divider strings, with move numbers printed at screen coordinates scaled by factors of 2 (rows) and 3 (columns) to align with cell centers. A `RANDOMIZE USR` call at line 400 with two addresses (64719 and 64716) invokes machine code routines, likely the ZX Spectrum’s built-in COPY command to dump the screen to a printer. The program supports finding multiple solutions from the same starting position by re-entering the main loop, or a full restart to choose a new board size and starting square.

---

Program Analysis

Program Structure

The program is organized into several functional blocks, entered via GO TO rather than GO SUB. Execution begins at line 5 with a jump to line 1200, which initializes the knight-move offset table before falling through to the setup routine at line 800.

Lines	Purpose
1200–1290	Initialize move-offset array a(8,2) and jump to board setup
800–1190	Board setup: get size, draw grid, get starting square, seed first move
10–140	Core backtracking loop: try each of 8 knight moves, backtrack on failure
150–220	Move accepted: record position, mark board, advance to next move
300–360	Solution found: prompt for another solution, restart, or screen copy
400	Machine code COPY screen to printer, return to prompt

Backtracking Algorithm

The solver uses an explicit stack stored in the array s(e,3), where dimension 3 holds the saved loop variable i (the move index) at each depth level. The variable c is the current depth (move number being placed) and p is the next move number to place.

1. At line 10, a FOR i=1 TO 8 loop tries each of the 8 knight moves.
2. Line 40 checks board bounds and that the target square is unvisited.
3. If valid, line 150 records the move and advances p and c.
4. If no valid move exists (loop exhausts at line 50), the code backtracks: erases the current position, decrements c, restores the saved i from s(c,3), and continues the NEXT i at line 130.
5. If c reaches zero at line 90, all possibilities are exhausted and the program stops.

Crucially, line 130 executes NEXT i after restoring i from the stack, which advances to the next untried move at the backtracked depth — a neat reuse of the BASIC FOR/NEXT mechanism without an explicit loop restart.

Board Display

The grid is drawn by slicing fixed 8-column strings. Line 1000 prints a column header, and lines 1020–1050 print alternating separator and cell rows, all truncated to x = l*3+1 characters so the grid matches the chosen board size. Move numbers are displayed at screen coordinates AT s(c,1)*2, s(c,2)*3, placing them inside the cell interiors of the printed grid. The current “head” of the path is shown with INVERSE 1 and INK 2 (red) to distinguish it from completed moves.

Machine Code Usage

Line 400 calls RANDOMIZE USR 64719 followed by RANDOMIZE USR 64716. These addresses correspond to the ZX Spectrum ROM’s COPY routine entry points, which transfer the screen contents to the ZX Printer. Two calls are used, likely targeting slightly different entry points to handle initialization and the actual copy pass.

Key BASIC Idioms

• String slicing for grid truncation: " 1 2 3..."( TO x) at lines 1000–1050 clips the fixed string to the board width without needing a loop.
• Boolean string selection: Line 1120 uses ("Row" AND i=1)+("column" AND i=2) to pick a label string based on the loop counter, a standard Sinclair BASIC trick exploiting the fact that AND 1 = string and AND 0 = "".
• Stack save/restore via array: s(c,3) stores and restores the FOR/NEXT variable i across backtrack steps.
• Board occupancy as string array: b$(l,l) is a character matrix initialized to spaces; squares are marked "X" on entry and reset to " " on backtrack.

Notable Anomalies and Remarks

• Lines 35 and 65 contain REM This line is to delete a line in the other program, indicating this is one of a pair of program files designed to be used together, with inter-program editing in mind.
• Line 5 jumps to 1200 to initialize the move table before any other setup, ensuring a(8,2) exists before it is used in the main loop.
• Line 155 handles the special case where p=e (last move) separately from line 150’s p<e case, printing the final move number without inverse video.
• Line 1195 contains an unreachable STOP between the initialization flow and the data block at 1200, serving as a safety barrier against accidental fall-through.