2
$\begingroup$

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)?

$\endgroup$
  • 2
    $\begingroup$ Did you check out the Wikipedia page? It has lots of links and pointers that look relevant. (I added the Wikipedia link to the question so I'm not suggesting that Mok-Kong linked to the page without reading it!) $\endgroup$ – David Richerby Oct 26 '14 at 15:49
  • 1
    $\begingroup$ @DavidRicherby: Yes. There is: "A computer program that finds a Knight's Tour for any starting position using Warnsdorff's rule can be found in the book 'Century/Acorn User Book of Computer Puzzles' edited by Simon Dally (ISBN 071260541X)." which seemed highly promising. But I failed to find that book even in the (fairly large) German Bavarian network of public libraries. $\endgroup$ – Mok-Kong Shen Oct 27 '14 at 16:15
  • 1
    $\begingroup$ @Mok-KongShen From the Wikipedia page: "By dividing the board into smaller pieces, constructing tours on each piece, and patching the pieces together, one can construct tours on most rectangular boards in polynomial time" with a citation to a paper by Ian Parberry that's freely available online. $\endgroup$ – David Richerby Oct 27 '14 at 16:28
  • $\begingroup$ The Knight's Tour was my implementation of choice when I was learning new assembler languages. Half the fun is coming up with optimizations and heuristics. For example, if your current move would isolate a corner and you aren't on move #62 (next to last move), you have failed. You can recurse and try something else. This is because if you don't move to the corner, you will isolate the corner. Once you do move there, you will be unable to leave so you'd better be done! $\endgroup$ – Tony Ennis Dec 27 '14 at 18:59
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is a nice writeup, but maybe a little beyond someone looking for an 'accessible' knight's tour algorithm? $\endgroup$ – Tony Ennis Dec 27 '14 at 19:51
0
$\begingroup$

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[0][0] = 2, a[0][1] = 1
a[1][0] = 2, a[1][1] = -1
a[2][0] = 2, a[2][1] = 1
a[3][0] = -2, a[3][1] = -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.

Preparation:

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I'm not sure that a 30-year-old, presumably long out of print, hobbyist book is going to be a "convenient" reference! Is the algorithm presented there clear? Is it "fairly efficient"? Is it plausible to translate it into a modern language or is it goto-spaghetti? $\endgroup$ – David Richerby Sep 28 '16 at 10:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.