Step by Step solution about How to resolve the algorithm Knight's tour step by step in the Mathematica/Wolfram Language programming language

The provided Wolfram programming language source code calculates the sequence of moves for the Knight's Tour problem, where the goal is to find a path for a knight on a chessboard that visits each square exactly once. Here's an explanation of the code step by step:

knightsTourMoves[start_] Function: This function takes a starting position start in the form of a chessboard square notation (e.g., "a1" or "d6") as input and returns a list of moves for the Knight's Tour.

Initialization:

• vertexLabels creates a mapping from each vertex (square) number to a chessboard square notation label (e.g., 1 -> "a1").
• knightsGraph generates a KnightTourGraph based on the initial position i and i. The graph has vertices labeled with chessboard square notations.
• hamiltonianCycle finds a Hamiltonian cycle in the KnightTourGraph using FindHamiltonianCycle and converts it to a list of directed edges using a pattern replacement operation (/. UndirectedEdge -> DirectedEdge).
• end extracts the directed edge from the Hamiltonian cycle that leads from the initial position start.
• FindShortestPath[g, start, end] finds the shortest path from the initial position start to the end position in the Hamiltonian cycle.

Main Calculation:

The code first initializes the data structures and the graph. Then, it finds the Hamiltonian cycle, which is a closed path that visits each vertex (square) exactly once. Next, it locates the starting position start within the Hamiltonian cycle and identifies the end position that leads back to start. Finally, it calculates the shortest path from the initial position start to the end position.

Example:

In the provided example, the code is used to find the Knight's Tour moves starting from the square "d8." The output shows the sequence of moves:

{"d8", "e6", "d4", "c2", "a1", "b3", "a5", "b7", "c5", "a4", "b2", "c4", "a3", "b1", "c3", "a2", "b4", "a6", "b8", "c6", "a7", "b5", \
"c7", "a8", "b6", "c8", "d6", "e4", "d2", "f1", "e3", "d1", "f2", "h1", "g3", "e2", "c1", "d3", "e1", "g2", "h4", "f5", "e7", "d5", \
"f4", "h5", "g7", "e8", "f6", "g8", "h6", "g4", "h2", "f3", "g1", "h3", "g5", "h7", "f8", "d7", "e5", "g6", "h8", "f7"}

This sequence of moves represents a solution to the Knight's Tour problem starting from "d8."

knightsTourMoves[start_] :=
  Module[{
    vertexLabels = (# -> ToString@c[[Quotient[# - 1, 8] + 1]] <>  ToString[Mod[# - 1, 8] + 1]) & /@ Range[64], knightsGraph, 
       hamiltonianCycle, end}, 
    knightsGraph = KnightTourGraph[i, i, VertexLabels -> vertexLabels,  ImagePadding -> 15];
    hamiltonianCycle = ((FindHamiltonianCycle[knightsGraph] /. UndirectedEdge -> DirectedEdge) /. labels)[[1]];
    end = Cases[hamiltonianCycle, (x_ \[DirectedEdge] start) :> x][[1]];
    FindShortestPath[g, start, end]]


knightsTourMoves["d8"]

(* out *)
  {"d8", "e6", "d4", "c2", "a1", "b3", "a5", "b7", "c5", "a4", "b2", "c4", "a3", "b1", "c3", "a2", "b4", "a6", "b8", "c6", "a7", "b5", \
"c7", "a8", "b6", "c8", "d6", "e4", "d2", "f1", "e3", "d1", "f2", "h1", "g3", "e2", "c1", "d3", "e1", "g2", "h4", "f5", "e7", "d5", \
"f4", "h5", "g7", "e8", "f6", "g8", "h6", "g4", "h2", "f3", "g1", "h3", "g5", "h7", "f8", "d7", "e5", "g6", "h8", "f7"}


  vertexLabels = (# -> ToString@c[[Quotient[# - 1, 8] + 1]] <>  ToString[Mod[# - 1, 8] + 1]) & /@ Range[64]

(* out *)
 {1 -> "a1", 2 -> "a2", 3 -> "a3", 4 -> "a4", 5 -> "a5", 6 -> "a6", 7 -> "a7", 8 -> "a8", 
  9 -> "b1", 10 -> "b2", 11 -> "b3", 12 -> "b4", 13 -> "b5", 14 -> "b6", 15 -> "b7", 16 -> "b8", 
 17 -> "c1", 18 -> "c2", 19 -> "c3", 20 -> "c4", 21 -> "c5", 22 -> "c6", 23 -> "c7", 24 -> "c8", 
 25 -> "d1", 26 -> "d2", 27 -> "d3",  28 -> "d4", 29 -> "d5", 30 -> "d6", 31 -> "d7", 32 -> "d8",  
 33 -> "e1", 34 -> "e2", 35 -> "e3", 36 -> "e4", 37 -> "e5", 38 -> "e6", 39 -> "e7", 40 -> "e8", 
 41 -> "f1", 42 -> "f2", 43 -> "f3", 44 -> "f4", 45 -> "f5", 46 -> "f6", 47 -> "f7", 48 -> "f8", 
 49 -> "g1", 50 -> "g2", 51 -> "g3", 52 -> "g4", 53 -> "g5", 54 -> "g6",55 -> "g7", 56 -> "g8", 
 57 -> "h1", 58 -> "h2", 59 -> "h3", 60 -> "h4", 61 -> "h5", 62 -> "h6",  63 -> "h7", 64 -> "h8"}


knightsGraph = KnightTourGraph[i, i, VertexLabels -> vertexLabels,  ImagePadding -> 15];


hamiltonianCycle = ((FindHamiltonianCycle[knightsGraph] /. UndirectedEdge -> DirectedEdge) /. labels)[[1]];


end = Cases[hamiltonianCycle, (x_ \[DirectedEdge] start) :> x][[1]];


FindShortestPath[g, start, end]]