Hello, I want to solve this classic problem. Could you please help me by sharing the solution approach, some code ideas, and a link to the problem? I would be very happy if you could share these with me.
Thank you!
You have a standard 8×8 chessboard and a knight placed on a starting cell (x,y) — coordinates are 1-based (from 1 to 8).
Your task is to find a sequence of knight moves such that:
The knight visits every square on the board exactly once (i.e., it makes 64 moves in total, including the starting square).
The sequence forms a closed tour, meaning that after the knight’s final move (the 64th move), the knight can move again by a single knight’s move to return to the starting cell (x,y).
If such a closed knight’s tour exists from the given starting position, print the board with numbers 1 through 64, where the number at each cell represents the move number when the knight visits that cell. Otherwise print "No".
Auto comment: topic has been updated by I_love_Computer_science (previous revision, new revision, compare).
Record and output these squares.
But will a sequence of moves ever not exist from a square? No, because:
Make a graph based on the chess board, where two vertices are connected with an edge if and only if a knight can move between the coresponding squares in one move. Now, for a given starting point you just need to find a Hamiltonian cycle.
Cses has this problem. Solution is Warnsdorf's rule: brute force search with backtracking but visit neighbours in ascending order of how many remaining moves they have — in practice it finds a solution quickly
edit: just saw the loop has to be closed. The above solution isn't always effective then, but I tested it out and for some starting squares it can find a solution on an 8x8 board (on others it times out)