Knight's Tour

Subscribe to my newsletter and never miss my upcoming articles

A Knight's tour is a sequence of moves starting from any square and visiting every other square such that every square must be visited exactly once.

The earliest known reference to this problem dates back to the 9th Century, India.

The knight's tour can be differentiated into 2 types:

  1. Closed Tour: If the first visited square is reachable from the last visited square by a knight's move, it is a Closed Tour.

  2. Open Tour: If the first visited square is not reachable from the last visited square by a knight's move, it is an Open Tour.

On an 8x8 board, there are exactly 26,534,728,821,064 closed tours. That's 26 trillion!

There are many solutions to this problem. Let's find one of them.

These are valid knight moves:

So, given (r, c); a Knight can jump to:

  1. (r+1, c+2)

  2. (r+1, c-2)

  3. (r-1, c+2)

  4. (r-1, c+2)

  5. (r-2, c+1)

  6. (r-2, c-1)

  7. (r+2, c+1)

  8. (r+2, c-1)

Here's one possible path:

Solution 1: A Brute Force solution is not a recommended one for this problem as this has a huge number of possibilities. So, we can use some other techniques to solve this problem in a better way.

Solution 2: As this problem has many possibilities, why not try each one of them and on the way, if they don't work out, we can just return and try other combinations. This technique, known as Backtracking is popular for these kind of problems.

Setup: The board is 8x8 and every cell in this board is set to 0 initially. Since each cell has to be visited exactly once, we'll use an 8x8 visited array to represent the visited status of each cell so as to avoid infinite loops. Initially, every cell is set to false.

Safe Position: As the board is limited, we must make sure not to get out of boundaries. So, a safe position is a position with (r, c) limited to board boundaries (0-indexed). So, the conditions are:

  1. r >= 0
  2. r < 8
  3. c >= 0
  4. c < 8
  5. board(r, c) == 0
bool safe(int r, int c) {
        return (r >= 0 && r < 8 && c >= 0 && c < 8 && !board[r][c]);
}

Moves List: Since we know what are valid knight moves, we can create an array of moves in a sequence. The eight moves above can be made into a list. We can create a 2x8 array where the 0th row represents next row position and the 1st row represents next column position from the current (r, c) position.

So, it can be implemented as:

int moves[2][8] = {
                   { 1, 1, -1, -1, -2, -2, 2, 2 },
                   { 2, -2, 2, -2, 1, -1, 1, -1 }
                  };

Backtrack: Since there are eight valid moves for a knight, we try all 8 moves and check if it leads to the correct solution. If not, we backtrack. It means that we place the number in (which we send as a parameter to this function) in the board's next position and recursively call the function with next positions and in+1 as a parameter and check if it gives a correct solution. If it doesn't, we replace the board's next position value with 0 again.

Next Position: It can be obtained by using the moves array. If we add the (0, ith) position to current (r) value and (1, ith) position to current (c) value, the resulting (r, c) is our next position.

So, as there are 8 valid moves; we run a loop from 0 to 7 and check for each move. The base condition for this function is if the value of in is 64. (Since there are 8*8 = 64 valid squares)

bool Solve(int r, int c, int in) {
    if (in == 64) return true;

    for (int i=0;i<8;++i) {
        int rr = r + moves(0, t);
        int cc = c + moves(1, t);

        if (safe(rr, cc)) {
            board[rr][cc] = in; // Trying the (rr, cc) square.

            if (Solve(rr, cc, in+1)) return true;  // Got a correct solution.

            else board[rr][cc] = 0;  // Didn't get a solution, Backtrack.
        }
    }
    return false; // No Solution with current (rr, cc) position.
}

We can see that in is being incremented on each call. This is to number the visit squares to know which cell was visited when.

We call this function by Solve(0, 0, 1);

The final board looks like:

Complete Code

No Comments Yet