How to resolve the algorithm Knight's tour step by step in the XPL0 programming language

Published on 12 May 2024 09:40 PM
#Xpl0

How to resolve the algorithm Knight's tour step by step in the XPL0 programming language

Table of Contents

Problem Statement

Problem: you have a standard 8x8 chessboard, empty but for a single knight on some square. Your task is to emit a series of legal knight moves that result in the knight visiting every square on the chessboard exactly once. Note that it is not a requirement that the tour be "closed"; that is, the knight need not end within a single move of its start position. Input and output may be textual or graphical, according to the conventions of the programming environment. If textual, squares should be indicated in algebraic notation. The output should indicate the order in which the knight visits the squares, starting with the initial position. The form of the output may be a diagram of the board with the squares numbered according to visitation sequence, or a textual list of algebraic coordinates in order, or even an actual animation of the knight moving around the chessboard. Input: starting square Output: move sequence

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Knight's tour step by step in the XPL0 programming language

Source code in the xpl0 programming language

int     Board(8+2+2, 8+2+2);            \board array with borders
int     LegalX, LegalY;                 \arrays of legal moves
def     IntSize=4;                      \number of bytes in an integer (4 or 2)
include c:\cxpl\codes;                  \intrinsic 'code' declarations


func    Try(I, X, Y);                   \Make a tentative move from X,Y
int     I, X, Y;
int     K, U, V;
[for K:= 0 to 8-1 do                    \for all possible moves...
    [U:= X + LegalX(K);                 \U and V are next square
     V:= Y + LegalY(K);
     if Board(U,V) = 0 then             \if square has not been visited then
        [Board(U,V):= I;                \ mark square with sequence number
        if I = 8*8 then return true;
        if Try(I+1, U, V) then return true      \led to solution?
        else Board(U,V):= 0;                    \no, undo tenative move
        ];
    ];
return false;
];      \Try


int  I, J;
[LegalX:= [2, 1, -1, -2, -2, -1, 1, 2];
 LegalY:= [1, 2, 2, 1, -1, -2, -2, -1];

for J:= 0 to 8+2+2-1 do                 \set up surrounding border for speed
    for I:= 0 to 8+2+2-1 do
        Board(I,J):= 1;
for J:= 0 to 8+2+2-1 do                 \reposition Board(0,0) to Board(2,2)
        Board(J):= Board(J) + 2*IntSize;
Board:= Board + 2*IntSize;
for J:= 0 to 8-1 do                     \empty board
    for I:= 0 to 8-1 do
        Board(I,J):= 0;
Text(0, "Starting square (1-8,1-8): ");  I:= IntIn(0)-1;  J:= IntIn(0)-1;
Board(I,J):= 1;                         \starting location is 0,0

if Try(2, I, J) then                    \try to find second square
        [for J:= 0 to 8-1 do            \draw board with knight's move sequence
            [for I:= 0 to 8-1 do
                [if Board(I,J) < 10 then ChOut(0, ^ );
                IntOut(0, Board(I,J));
                ChOut(0, ^ );
                ];
            CrLf(0);
            ];
        ]
else    Text(0, "No Solution.^M^J");
]

You may also check:How to resolve the algorithm String comparison step by step in the J programming language
You may also check:How to resolve the algorithm Catalan numbers step by step in the MATLAB / Octave programming language
You may also check:How to resolve the algorithm Program name step by step in the zkl programming language
You may also check:How to resolve the algorithm Levenshtein distance step by step in the CoffeeScript programming language
You may also check:How to resolve the algorithm Conditional structures step by step in the Grain programming language