--- title: "Knight’s Tour" id: 56108 type: "computer_media" slug: "knights-tour" url: "http://localhost/computer_media/knights-tour/" markdown_url: "http://localhost/computer_media/knights-tour.md" published_at: "2024-07-19T01:32:10+00:00" modified_at: "2026-03-30T21:43:26+00:00" author: "David Anderson" featured_image: url: "http://localhost/wp-content/uploads/2024/07/SCR-20240718-sqfb.png" excerpt: "A backtracking Knight's Tour solver lets you pick any board size up to 8×8, find solutions, and print the completed board via machine code." category: - name: "Archived Media" slug: "archived-media" taxonomy: "category" url: "http://localhost/category/archived-media/" post_tag: - name: "Downloadable" slug: "downloadable" taxonomy: "post_tag" url: "http://localhost/tag/downloadable/" - name: "TS 2068" slug: "ts2068" taxonomy: "post_tag" url: "http://localhost/tag/ts2068/" model: - name: "Timex/Sinclair 2068" slug: "ts-2068" taxonomy: "model" url: "http://localhost/model/ts-2068/" indiv: - name: "James Brezina" slug: "james-brezina" taxonomy: "indiv" url: "http://localhost/indiv/james-brezina/" genre: - name: "Game" slug: "game" taxonomy: "genre" url: "http://localhost/type/game/" media_type: "Program" programmers: - name: "James Brezina" slug: "james-brezina" taxonomy: "indiv" url: "http://localhost/indiv/james-brezina/" download_url: "https://archive.org/download/timex-sinclair-software-archive/KnightTour%20%28198x%29%28Brezina%2C%20James%29%28TS2068%29%28US%29%28Program%29.zip" mediadate: "198x" images: - url: "http://localhost/wp-content/uploads/2024/07/SCR-20240718-sqfb.png" media_type_tags: "Game" --- 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 `p0 AND y>0 AND x<=l AND y<=l THEN IF b$(x,y)=" " THEN GO TO 150 50 NEXT i 60 PRINT AT s(c,1)*2,s(c,2)*3;" " 65 REM This line is to delete a line in the other program 70 LET b$(s(c,1),s(c,2))=" " 80 LET c=c-1 90 IF NOT c THEN STOP 100 INVERSE 1: PRINT AT s(c,1)*2,s(c,2)*3; INK 2;c: INVERSE 0 110 LET p=p-1 120 LET i=s(c,3) 130 NEXT i 140 GO TO 60 150 PRINT AT s(c,1)*2,s(c,2)*3;c: IF p8 THEN GO TO 910 930 LET e=l*l 940 LET x=l*3+1 950 CLS 1000 PRINT " 1 2 3 4 5 6 7 8"( TO x) 1010 FOR i=1 TO l 1020 PRINT TAB 2;"+--+--+--+--+--+--+--+--+"( TO x) 1030 PRINT i;TAB 2;"+ + + + + + + + +"( TO x) 1040 NEXT i 1050 PRINT TAB 2;"+--+--+--+--+--+--+--+--+"( TO x) 1060 DIM s(e,3) 1070 DIM b$(l,l) 1080 LET p=2 1090 LET c=1 1100 PRINT "Enter starting location" 1110 FOR i=1 TO 2 1120 PRINT AT i+l*2+2,0;"Enter ";("Row" AND i=1)+("column" AND i=2) 1130 INPUT x 1135 PRINT AT i+l*2+2,14;x 1140 IF x<1 OR x>l THEN GO TO 1130 1145 PRINT AT i+l*2+2,0;" "; 1150 LET s(c,i)=x 1160 NEXT i 1165 PRINT AT l*2+2,0;" " 1170 PRINT AT s(c,1)*2,s(c,2)*3;"1" 1180 LET b$(s(c,1),s(c,2))="X" 1190 GO TO 10 1195 STOP 1200 DIM a(8,2) 1210 LET a(1,1)=-1: LET a(1,2)=-2 1220 LET a(2,1)=-2: LET a(2,2)=-1 1230 LET a(3,1)=-2: LET a(3,2)=1 1240 LET a(4,1)=-1: LET a(4,2)=2 1250 LET a(5,1)=1: LET a(5,2)=2 1260 LET a(6,1)=2: LET a(6,2)=1 1270 LET a(7,1)=2: LET a(7,2)=-1 1280 LET a(8,1)=1: LET a(8,2)=-2 1290 GO TO 800 9000 SAVE "Knighto1": PRINT "Rewind & press ENTER to VERIFY.": VERIFY "Knighto1": PRINT "Knighto1 Verified." ```