The Knight's Tour

Nearly forty years ago, a friend of mine challenged me to write a program to solve The Knight's Tour problem. Simply put: can a knight move around the chess board landing on every space only once?

At the time, I was working with a WYSE-386 computer with 2MB of memory and 40MB of hard drive space. After coming up with a suitable algorithm, I implemented it in 16-bit assembler. Running on a single CPU at 16MHz, It took 29 days for it to find a solution.

Since then, I have periodically revisited this using a number of different approaches. The most recent iteration of my algorithm took another turn. Instead of using a two-dimensional array for the board, I linearized it into a single vector which provides substantial computational advantages over my previous efforts.

I start by defining the board to virtually look like this:

By traversing the bottom row (left to right) and then the next row, etc., I implement this with a one-dimensional array of 144 values ("board[144]"). Moving up or down or left or right is simply a matter of adding the indexed offset to the current location.

The eight possible moves with 0 through 7 (and their offsets):

These moves are stored in an eight-element array of offsets ("dirloc[8]") from the current location. Given the direction (0-7), adding the value of the ith element gives the new location. If the new location is not zero, then it is an invalid move.

For each location visited on the board, the number of moves up until then is stored. At each location, the moves array is indexed by the current direction. When a new move cannot be found (i.e., moves[cur] = 8), the move is retracted by subtracting the appropriate offset in the dirloc array. The direction is incremented to the next trial and repeated again until it equals eight.

When 63 moves have been made, the program stops and prints out the board. Here is the basic C code to make it happen:

// knight1.c (Knight's Tour)

#include <stdio.h>

int cur,loc,curloc,i,j;
int dirloc[] = { -25,-14,10,23,25,14,-10,-23 };
int moves[64];
int board[144];

void init(void)
{
  cur = 0;
  curloc = 32;
  for (i = 0; i < 64; i++)
  {
    moves[i] = 0;
  }
  for (i = 0; i < 144; i++)
  {
    board[i] = 1;
  }
  for (i = 2; i < 10; i++)
  {
    for (j = 2; j < 10; j++)
    {
      board[i + j * 12] = 0;
    }
  }
  board[curloc] = 1;
}

void print_board(void)
{
  for(i=110;i>25;i-=12)
  {
    for(j=0;j<8;j++)
    {
      printf("\t%d",board[i+j]);
    }
    printf("\n\n");
  }
}

int main()
{
  init();
  while (cur < 63)
  {
    if (moves[cur] == 8)
    {
      if (cur == 0)
      {
        break; // exit if no solution is found
      }
      moves[cur] = 0;
      board[curloc] = 0;
      cur--;
      curloc -= dirloc[moves[cur]];
      moves[cur]++;
    }
    else
    {
      loc = curloc + dirloc[moves[cur]];
      if (board[loc] == 0)
      {
        board[loc] = cur + 2;
        curloc = loc;
        cur++;
      }
      else
      {
        moves[cur]++;
      }
    }
  }
  if(cur == 63)
  {
    print_board();
    return 0;
  }
  return 1;
}

First solution found by the example code:

There are many ways to optimize code to find a solution using a more efficient algorithm than the Brute Force one outlined here. However, my goal was to find a way to make the exhaustive approach as efficient as possible.

This same embedded algorithm, running for twenty-nine days on a Raspberry Pi , produced over 785,000 unique directional solutions. That's an amazing improvement over my 386. 😄

* * * [ ADDED 4/17/2023 ] * * *

I asked ChatGPT for a solution: "Write a C program that provides a solution to the Knight's Tour chess problem." This is the result:

#include <stdio.h>
#include <stdbool.h>

#define N 8 // Size of the chessboard

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

bool isSafe(int x, int y, int sol[N][N]) {
    return (x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
}

void printSolution(int sol[N][N]) {
    for (int x = 0; x < N; x++) {
        for (int y = 0; y < N; y++) {
            printf("%2d ", sol[x][y]);
        }
        printf("\n");
    }
}

bool solveKnightTour(int x, int y, int moveCount, int sol[N][N]) {
    if (moveCount == N * N) {
        return true; // All squares visited
    }

    for (int i = 0; i < 8; i++) {
        int nextX = x + moveX[i];
        int nextY = y + moveY[i];

        if (isSafe(nextX, nextY, sol)) {
            sol[nextX][nextY] = moveCount;
            if (solveKnightTour(nextX, nextY, moveCount + 1, sol)) {
                return true; // Move leads to a solution
            } else {
                sol[nextX][nextY] = -1; // Backtrack
            }
        }
    }

    return false; // No solution found
}

int main() {
    int sol[N][N]; // Solution matrix

    // Initialize solution matrix
    for (int x = 0; x < N; x++) {
        for (int y = 0; y < N; y++) {
            sol[x][y] = -1; // Mark all squares as unvisited
        }
    }

    // Starting position
    int startX = 0;
    int startY = 0;
    sol[startX][startY] = 0; // Mark starting position as visited

    if (solveKnightTour(startX, startY, 1, sol)) {
        printf("Knight's Tour solution:\n");
        printSolution(sol);
    } else {
        printf("No solution found.\n");
    }

    return 0;
}