Could someone give an easily accessible reference containing an algorithm that could be conveniently implemented into a code for computing Knight's Tour (preferably also with fairly good efficiency)?
The idea is that we have a board of size $n \times n$, where $n$ is say 8 for your usual chessboard. We start from one of the corners (typically), and place a knight chess piece to this corner cell. The question is, can we move the knight through the board such that we visit each cell exactly once?
In graph theoretic terms, this is the Hamiltonian path problem, which in general is NP-complete. The Warnsdorff's rule you describe in the comments is a way to solve the problem pretty efficiently in practice. More generally, the Warnsdorff's rule is a fail first heuristic. This means that by running into dead-ends quickly, we prune the search tree aggressively, and thus succeed quickly.
For a programming exercise (and for the easiness of presentation), it is convenient to represent the graph as an implicit graph: you will have no explicit graph stored, but instead you can just store the coordinates visited, and compute the edges "on the fly".
- At every step, your knight is in position $v$ on the board. The set of possible next moves is given by the successor function ("what unvisited cells I can move to from my position $v$?"), let us denote the possible next cells by $N(v)$.
- When considering what cell $u \in N(v)$ to pick, we look at the degree of the vertices in $N(v)$. In this case, the degree of a vertex $u \in N(v)$ is given by the number of possible moves the knight can take from $u$.
- Let $N^\delta(v)$ denote the set of neighbors of a vertex $v$ with the smallest degree. Our goal is to choose the vertex with the smallest degree; this is really easy if there is only one choice, i.e. if $|N^\delta(v)| = 1$. If this is not the case, we can employ some tie breaking strategy.
- A simple and a pretty effective tie breaking strategy is to pick the next vertex $u \in N^\delta(v)$ uniformly at random -- this is simple to implement as well.
For a programming exercise, I definitely recommend using implicit graphs, and also not fixing the chess piece as a knight. Instead, build say an array of moves your piece can take -- it's pretty fun to try to see how the set of possible moves affect path finding. It's also fun to experiment with vertex choosing heuristics other than Warndorff's, and similarly with tie-breaking strategies.
For accessibility, implement the board as a 12x12 grid. The squares in the outer 2 rows/columns are initialized to 'have been visited.' Now you don't have to bother checking x and y coordinates for boundary conditions. Your knight can't go to those squares and thus can't leap off the board into hyperspace. An old version of Sargon used this technique.
Then you'll need a 2x8 array for the offsets to move the knight:
a = 2, a = 1 a = 2, a = -1 a = 2, a = 1 a = -2, a = -1 (etc)
The first row means you'd move your knight up-2-and-one-to-the-right. The last row means you'd move the knight back-2-and-one-to-the-left.
Initialize the board to all -1's. Each time you make a move, stamp the move number onto the board. You can't move to a square that has a number greater than -1.
1. create a 12x12 board. 2. initialize the outer 2 rows and columns to 0 so the knight can never visit them. only squares with a value of -1 can be visited. 3. initialize the 8x8 center to -1. 4. Create the 2x8 knight array as described above.
To start the tour, jump! Note the 0, which is the first move. The x and y coordinates of 6 are wholly arbitrary.
IF (Jump(0, 6, 6)) output the board ELSE print "There was no solution"; function Jump(moveNumber, x, y) BEGIN if (board[x, y] has been visited) return FALSE; board[x, y] = moveNumber; IF (moveNumber == 63) THEN return TRUE -- Success! FOR(i=0; i<8;i++) BEGIN IF (Jump(moveNumber+1, x+x_offset[i], y+x_offset[i])) return TRUE END -- If we get here, we fail. There is no solution going forward, we must backtrack. board[x, y] = -1 // Don't forget to restore the board! return FALSE END FUNCTION
This is your garden variety brute-force algorithm. It is not speedy. The wiki page shows some optimizations. They can be generalized as 'fail early, fail often.' For example, after every successful leap, if you can find a isolated square, you can safely fail.
Also, it is possible to nitpick the algorithm I present. No amount of tweaking will make it run appreciably faster. The run time in the problem is in its fundamental difficulty, not where we do a few checks or variable assignments. For example, it would be possible to move to the FOR loop the check to see if a square has already been visited. You would save a few seconds, maybe. That is, this pokey algorithm might run in an hour instead of 3,602 seconds.
An interesting thing about this problem is that the starting position of the knight greatly influences how long it takes to find a solution. And because the knight-offset array is independent of the starting position, the board is not really symmetric. That is, starting in the upper left column might yield a solution much sooner than starting in the lower right.
A computer program that solves the knight's Tour is published in 'Century/Acorn User Book of Computer Puzzles' edited by Simon Dally https://openlibrary.org/books/OL15157004M/Book_of_computer_puzzles