Knight's Tour (Amstrad CPC) by muckypaws

==========================================================

KNIGHT'S TOUR - BASIC10 SCHAU Competition Entry

==========================================================

Author  : Jason Brooks

Website : www.muckypaws.com

System  : Amstrad CPC 664 / CPC 6128

Date    : 18th March 2026

------------------------------------------------------------

DESCRIPTION

------------------------------------------------------------

Knight's Tour is a classic chess puzzle in which a knight must visit every square on an 8x8 chessboard exactly once, using only legal knight moves (an L-shaped move of two squares in one direction and one square perpendicular).

This program solves the puzzle automatically from any user-chosen starting square, rendering each visited cell as a chess knight graphic drawn in Locomotive BASIC using relative vector coordinates (DRAWR), with the move number displayed inside each knight. The board fills visually in real time as the solution is computed and drawn.

The program uses Warnsdorff's Heuristic to solve the tour efficiently without backtracking. At each step, the knight moves to the unvisited square that has the fewest onward moves available (i.e. it prefers squares that are hardest to reach later). Ties are broken by preferring the square closest to the centre of the board (Euclidean distance to position 4.5,4.5), which improves tour completion from corner and edge starting positions.

This heuristic reliably produces a complete tour from virtually any starting square on the board, typically completing all 64 moves without backtracking.

The knight graphic itself was generated by processing an SVG chess knight outline: the Bezier curves were approximated as polylines using the Douglas-Peucker  simplification algorithm, then the coordinates were scaled, Y-axis flipped (SVG is Y-down, CPC is Y-up), and the base rectangle was topologically merged into the body outline to produce a single continuous stroke. This allows the entire knight shape to be drawn with one WHILE/WEND loop reading from a single DATA line - no pen lifts needed.

The knight alternates between white (INK 1) and red (INK 2) on successive squares to make the tour path visually readable. Move numbers are printed in green (INK 3) using TAG mode (text-follows-graphics-cursor) so the number appears at the correct board position automatically.

NOTE: This program requires Amstrad CPC 664 or CPC 6128.

It uses BASIC 1.1 features (FILL, GRAPHICS PEN, TAG/TAGOFF)

not available in the CPC 464's BASIC 1.0.

The author previously implemented Knight's Tour in Python:

https://muckypaws.com/2025/05/19/knights-tour/

CATEGORY

------------------------------------------------------------

SCHAU: 10 lines, max 256 characters per logical line.

Active code lines: 8 (lines 3-10)

Comment lines: 2 (lines 1-2, author/title information)

==========================================================

KNIGHT'S TOUR - ANNOTATED PROGRAM LISTING

BASIC10 SCHAU Competition Entry

==========================================================

Author  : Jason Brooks  |  www.muckypaws.com

System  : Amstrad CPC 6128 / CPC 664 (Locomotive BASIC 1.1)

Date    : 18th March 2026

==========================================================

OVERVIEW

--------

This program solves the Knight's Tour puzzle on an 8x8 chessboard, rendering each solution step as a hand-crafted chess knight graphic. The solver uses Warnsdorff's Heuristic for near-instant solutions from any starting position.

The board follows standard chess orientation: coordinate 1,1 is the bottom-left corner as seen from White's side, matching the chess convention of files a-h (left to right) and ranks 1-8 (bottom to top).

HOW WARNSDORFF'S HEURISTIC WORKS

---------------------------------

At each move, instead of trying all possibilities (brute-force backtracking), the knight always moves to the unvisited square that has the FEWEST onward moves available from it. The intuition: visit hard-to-reach squares early, before they become stranded dead-ends. This greedy heuristic finds a complete 64-move tour from almost any start square without backtracking, running in O(n) time.

Tie-breaking: when two candidate squares have equal onward move counts, the square nearer the board centre (4.5, 4.5) is preferred. This prevents the tour getting stuck in corners on certain starting positions.

I previously implemented this algorithm in Python:

https://muckypaws.com/2025/05/19/knights-tour/

THE KNIGHT GRAPHIC

------------------

The chess knight outline was derived from an SVG vector  graphic. The SVG Bezier curves were approximated as polylines using the Douglas-Peucker simplification algorithm, then:

  - Scaled to fit within one board cell

  - Y-axis flipped (SVG Y increases downward; CPC graphics Y increases upward)

  - The base rectangle was topologically merged into the body outline to produce a single continuous pen stroke

This allows the entire knight shape to be drawn with one WHILE/WEND loop from a single DATA line - no pen lifts, no GOSUB overhead per segment.

PIXEL ALIGNMENT - THE AND MASK TECHNIQUE

-----------------------------------------

The CPC's graphics system uses logical coordinates:

 X: 0 to 639  (maps to 320 physical pixels, 2:1 ratio)

  Y: 0 to 399  (maps to 200 physical pixels, 2:1 ratio)

This means odd logical coordinates fall between physical pixels. When the knight graphic DATA uses integer DRAWR steps, the starting position must be on an even boundary or rendering drift occurs across the 64 cells.

The fix: bitwise AND masks clear bit 0 of each coordinate, forcing alignment to the nearest even logical unit:

  cx = nx AND 1022  (binary 1111111110 - clears bit 0)

  cy = ny AND 510   (binary  111111110 - clears bit 0)

Different masks are needed for each axis:

  X uses AND 1022: the X range is 0-639 (10 bits needed).

                   AND 510 would wrongly cap X at 510,

                   potentially corrupting positions above

                   512 on a wider board layout.

  Y uses AND 510:  the Y range is 0-399 (9 bits needed).

                   510 safely covers the full Y range.

In this program the board's maximum X coordinate is only 491 (xo=124, 7 cells x 49 + 24 offset), so AND 510 on X would not have caused a visible error - but it was logically incorrect and would fail on any layout where X exceeds 510.

==========================================================

ANNOTATED LISTING

==========================================================

Line 1 - Title comment

-----------------------

1 ' Knights Tour - Jason Brooks - BASIC10 - Schau Entry 18th March 2026

Line 2 - Author URL comment

----------------------------

2 ' Find me at www.muckypaws.com

Line 3 - Initialisation

------------------------

3 MODE 1:BORDER 0:PAPER 0:INK 0,0:INK 1,26:INK 2,6:INK 3,18:PEN 1:CLS:

  DEFINT a-z:DIM b(8,8),dx(8),dy(8):FOR i=1 TO 8:READ dx(i),dy(i):NEXT:

  xo=124:yo=4:s=49:h=392:p=3:

  DATA 2,1,1,2,-1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1

  MODE 1         - 4-colour, 320x200 pixel graphics mode

  BORDER 0       - Black border

  PAPER/INK      - Set colour palette:

                     INK 0 = black (background)

                     INK 1 = white (odd-move knight outline)

                     INK 2 = red   (even-move knight outline)

                     INK 3 = green (move numbers)

  DEFINT a-z     - All variables default to INTEGER type.

                   Crucial for speed: avoids floating-point overhead on all loop counters and board array indices.

  DIM b(8,8)     - Board array: b(x,y) holds the move number that visited square (x,y), or 0 if unvisited

  DIM dx(8),dy(8)- The 8 possible knight move offsets

  FOR/READ/NEXT  - Load the 8 knight move vectors from DATA:

                     ( 2, 1)( 1, 2)(-1, 2)(-2, 1)

                     (-2,-1)(-1,-2)( 1,-2)( 2,-1)

  xo=124,yo=4    - Board bottom-left pixel coordinate

  s=49           - Cell size in pixels (49 x 8 = 392)

  h=392          - Board total width/height in pixels

  p=3            - Pen colour placeholder (set per move in line 9)

                   Draw first Knight in Green for Starting Point

Line 4 - User input and board drawing

--------------------------------------

4 INPUT"START X,Y (1-8)";x,y:

  IF x<1 OR x>8 OR y<1 OR y>8 THEN 4

  ELSE CLS:

  FOR i=0 TO 8:

    MOVE xo+i*s,yo,1,0:DRAW xo+i*s,yo+h:  ' 9 vertical lines

    MOVE xo,yo+i*s:DRAW xo+h,yo+i*s:      ' 9 horizontal lines

  NEXT:

  cx=(xo+(x-1)*s+24) AND 1022:  ' Starting knight X, pixel-aligned

  cy=(yo+(y-1)*s+24) AND 510:   ' Starting knight Y, pixel-aligned

  TAG                           ' Text follows graphics cursor

  INPUT re-prompts if coordinates are outside 1-8.

  9 vertical and 9 horizontal lines form the 8x8 grid.

  MOVE ...1,0 sets line type solid using INK MODE

  AND 1022 / AND 510: see "PIXEL ALIGNMENT" section above.

  TAG: subsequent PRINT statements place text at the

  current graphics cursor position, not the text cursor.

Line 5 - Draw first knight, fill cell, begin tour loop

-------------------------------------------------------

5 GOSUB 9:           ' Draw knight at starting position

  MOVE cx,cy:FILL 2: ' Flood-fill starting cell with INK 2 (red)

  FOR m=1 TO 64:     ' Main loop: 64 moves to complete the board

    b(x,y)=m:        ' Mark current square as visited (move m)

    bt=99:bx=x:by=y: ' Reset best-move tracker (99 = none found)

    FOR k=1 TO 8:    ' Test all 8 possible knight destinations

      nx=x+dx(k):ny=y+dy(k): ' Next X/Y Board Position to check

      IF nx<1 OR nx>8 OR ny<1 OR ny>8 THEN 8  ' Off board: skip

      ELSE IF b(nx,ny)<>0 THEN 8              ' Visited: skip

  FILL 2 flood-fills the initial knight with INK 2 (red)

  

Line 6 - Count onward moves (Warnsdorff's degree count)

---------------------------------------------------------

6 d=0:FOR j=1 TO 8:

    tx=nx+dx(j):ty=ny+dy(j):   ' Get next Test X/Y Position

    IF tx<1 OR tx>8 OR ty<1 OR ty>8 THEN 7  ' Off board

    ELSE IF b(tx,ty)=0 THEN d=d+1           ' Unvisited: count

  (falls through to line 7)

  Core of Warnsdorff's: counts how many unvisited squares are reachable from candidate (nx,ny). Lower = more isolated = should be visited sooner.

Line 7 - Warnsdorff selection with centre tiebreak

----------------------------------------------------

7 NEXT j:

                                 ' Update best degree count

  IF d<bt OR (d=bt AND ABS(nx-4.5)+ABS(ny-4.5)<c) THEN bt=d:

    c=ABS(nx-4.5)+ABS(ny-4.5):   ' Store distance to centre

    bx=nx:by=ny                  ' Record best candidate square

  Primary:  fewer onward moves wins (d < bt)

  Tiebreak: Manhattan distance to board centre (4.5, 4.5).

            More central squares preferred when degrees tie.

            Significantly improves completion rate from edge and corner starting positions.

Line 8 - Move commitment and termination handling

--------------------------------------------------

8 NEXT k:

  IF m=64 THEN

    LOCATE 1,1:PEN 1:TAGOFF:PRINT"DONE":END

  ELSE IF bt=99 THEN

    LOCATE 1,1:PEN 2:TAGOFF:PRINT"STUCK AT ";m:END

  ELSE

    x=bx:y=by:

    nx=xo+(x-1)*s+24:ny=yo+(y-1)*s+24:

    cx=nx AND 1022:cy=ny AND 510:  ' Pixel-align (see above)

    MOVE cx,cy:GOSUB 9:

  NEXT m:END

  m=64: all squares visited. Print DONE in white, stop.

  bt=99: no valid move found (rare with Warnsdorff's).

         Print STUCK AT [move] in red, stop.

  Otherwise: commit to best move, pixel-align coordinates, move graphics cursor, draw knight, continue loop.

  AND 1022 on X (not AND 510) correctly handles the full

  0-639 logical X range (see PIXEL ALIGNMENT above).

Line 9 - Knight drawing subroutine

------------------------------------

9 RESTORE 10:           ' Reset DATA pointer to line 10

  MOVE cx+4,cy+16:      ' Position pen at top of knight shape

  PEN p:                ' Set outline colour (1=white, 2=red)

  READ a,b:             ' Read first coordinate pair

  WHILE a<>999:         ' Sentinel 999,999 signals end of data

    DRAWR a,b,p,0:      ' Draw relative segment, ink p, no XOR

    READ a,b:

  WEND:

  MOVE cx-36,cy-4:      ' Move to move-number print position

  p=m MOD(2)+1:         ' Alternate: odd move=1(white) even=2(red)

  GRAPHICS PEN 3,1:     ' Set graphics and text pen to INK 3 (green)

  PRINT m+1;:           ' Print move number via TAG at graphic pos

  RETURN

  DRAWR a,b,p,0 draws relative to current position.

  p sets ink colour; 0 disables XOR mode.

  GRAPHICS PEN 3,1 sets both graphics and text pen, XOR mode simultaneously, so the TAG-mode PRINT uses INK 3 (green).

Line 10 - Knight graphic vector data

--------------------------------------

10 DATA 1,-1,2,2,2,1,1,0,1,0,1,0,-2,-5,4,-2,0,-4,7,-11,-4,-3,

        -2,3,-2,2,-2,1,-4,0,-7,8,-1,-1,4,-4,-1,-3,0,-3,1,-2,

        2,-2,2,-2,2,-2,0,-2,2,0,0,-6,-31,0,0,6,2,2,2,14,4,8,

        5,5,5,2,4,0,2,0,999,999

  36 (X,Y) relative coordinate pairs in CPC logical units, encoding the chess knight silhouette as a single unbroken stroke. Derived from SVG vector data via:

    1. Bezier curve approximation (Douglas-Peucker, 8 segments

       per curve, epsilon=0.2)

    2. Base rectangle merged into body outline at the neck

       junction point - eliminates any pen-lift move

    3. Scaled to board cell size, Y-axis flipped

  Terminated by sentinel 999,999.

  Integer coordinates work correctly because cx/cy are always AND-masked to even boundaries before drawing begins (lines 4 and 8), ensuring the first MOVE lands on a pixel boundary and all subsequent DRAWR steps accumulate without sub-pixel drift.

==========================================================

END OF ANNOTATED LISTING

==========================================================