Knight's Tour Puzzle

To solve this puzzle, you place a knight on one of the squares of a chess board e.g.white's QR1. You then move it around the board visiting each square once and once only before returning to your chosen starting point.

I wrote a program to do this around 1995 using a DOS based version of Borland Turbo C++.
The method I used is called Natural-order Tree Searching and is described in Chapter 6 of Computer Science, A First Course, Second Edition by Forsythe, Keenan, Organick and Stenberg (ISBN 0-471-26681-7).

Points to note about my solution: 

It does not use recursion. 

It only uses subscripts >= 1 although arrays in C start with a subscript of zero.

It assumes that 8 moves are possible from every square and then discards any which would send the knight off the board.

It keeps QB2 or QN3 clear until the very end so the knight has a way to get back to the starting point. 

During testing, I found that around move 20, white's KR1 was left empty but the squares which could get to it had already been visited. The knight then went backwards and forwards around move 50 but had no hope of ever finding a solution until it had back-tracked to move 20 again, which would not have happened for a very long time. The program was then amended to look for inaccessible squares each time a move was being considered. Once this had been done it was able to calculate a solution in less than a second.

This is the first version of my program. It calculates one answer then stops. Although it originally ran under DOS, the run below took place on a Linux machine. You can copy and paste it then compile it with a modern C compiler to run it yourself if you wish.

I also made a graphical version of this with a delay loop so that I could watch the knight moving around the board but that has been lost:

/* Non recursive solution to knight's tour.
   This version (asrkt01) finds one solution then stops. */

/* Function declarations. */

void find_next_move (void);
void try_moves (void);
void display_board (void);

/* Global variables. */

int board [9] [9];
/* (Board [0] [0] to board [0] [9] and board [0] [0] to board [9] [0]
are not used.) */

int position [65] [4];
/* (Position [0] [0] to position [0] [4] and position [0] [0] to
position [65] [0] are not used.) */

int level;
int x;
int y;
int move_found;

int main ()
{
/* Start of run processing. */

int a;
int b;

for (a = 1; a < 65; a++)
  for (b = 1; b < 4; b++)
    position [a] [b] = 0;

position [1] [1] = position [1] [2] = 1;

for (a = 1; a < 9; a++)
  for (b = 1; b < 9; b++)
    board [a] [b] = 0;

board [1] [1] = 1;

level = 1;

/* Continue processing until either:
(1) All combinations have been tested but no solution has been found and the
program tries to move the knight from QR1.
OR
(2) A solution is found. */

while ((level > 0) && (level < 64)) find_next_move ();

/* End of run processing. */

if (level == 0) printf("\nNo solution found");

if (level == 64)
  {
  printf("\nThis is an answer");
  display_board();
  }
return 0;
}
void find_next_move (void)
{
/* Look for next available move from that position. */

move_found = 0;

while ((position [level] [3] < 8) && (move_found == 0)) try_moves ();

if (move_found == 0)
  {
  /* Move_found is zero so no move has been found.
  Remove the knight concerned from the board and go back down a level. */

  x = position [level] [1];
  y = position [level] [2];
  board [x] [y] = 0;
  position [level] [1] = position [level] [2] = position [level] [3] = 0;
  level--;
  }
else
  {
  /* Move has been found.
  Go up a level and place knight on relevant square. */

  level++;
  position [level] [1] = x;
  position [level] [2] = y;
  board [x] [y] = level;
  }
}
void try_moves (void)
{
int accessibility;
int inaccessible_squares;
int i; int j; int k; int l; int m;

/* Try the next move from that position. */

position [level] [3] ++;
x = position [level] [1]; y = position [level] [2];

switch (position [level] [3])
  {
  /* Calculate x and y coordinates of next position from move chosen. */

  case 1: x = x + 1; y = y + 2; break;
  case 2: x = x + 2; y = y + 1; break;
  case 3: x = x + 2; y = y - 1; break;
  case 4: x = x + 1; y = y - 2; break;
  case 5: x = x - 1; y = y - 2; break;
  case 6: x = x - 2; y = y - 1; break;
  case 7: x = x - 2; y = y + 1; break;
  case 8: x = x - 1; y = y + 2; break;
  }
/* Check if the move would send the knight off the board. */

if ((x < 1) || (x > 8) || (y < 1) || (y > 8)) return;

/* Check whether the square is occupied. */

if (board [x] [y] != 0) return;

/* A legal move has been found to an unoccupied square.
Check board to see whether there any inaccessible squares. */

/* It should only be possible to fill both QN3 and QB2 at level 63.
Otherwise there would be no way of returning to QR1 at the end. */

if ((x == 2) && (y == 3) && (board [3] [2] != 0) && (level != 63)) return;
if ((x == 3) && (y == 2) && (board [2] [3] != 0) && (level != 63)) return;

/* Inaccessible_squares is a switch to check whether there any inaccessible squares. */

inaccessible_squares = 0;

for (i = 1; i < 9; i++)
  {
  if (inaccessible_squares == 1) break;
  for (j = 1; j < 9; j++)
    {
    /* If the square has been occupied then it does not need to be accessible. */

    if (board [i] [j] != 0) continue;

    /* If the square is currently being considered as the next location then
    it does not need to be checked as this will happen on the next move
    anyway. */

    if ((i == x) && (j == y)) continue;

    /* Accessibility counts the number of empty squares which are one move
    away from the square being checked. */

    accessibility = 0;

    for (k = 1; k < 9; k++)
      {
      switch (k)
{
case 1: l = i + 1; m = j + 2; break;
case 2: l = i + 2; m = j + 1; break;
case 3: l = i + 2; m = j - 1; break;
case 4: l = i + 1; m = j - 2; break;
case 5: l = i - 1; m = j - 2; break;
case 6: l = i - 2; m = j - 1; break;
case 7: l = i - 2; m = j + 1; break;
case 8: l = i - 1; m = j + 2; break;
}
      /* Check to see whether the square would be off the board. */

      if ((l < 1) || (l > 8) || (m < 1) || (m > 8)) continue;

      /* Check to see whether the square has been occupied.
      QR1 counts as an accessible square even though it has already been
      used. */

      if ((board [l] [m] == 0) || ((l == 1) && (m == 1))) accessibility++;

      /* Jump out of the loop as soon as 2 accessible squares are found. */

      if (accessibility > 1) break;
      }
    /* Each empty square needs to be accessible from at least two other
    squares, one to get to it and one to leave it. */

    if (accessibility < 2)
      {
      inaccessible_squares = 1; break;
      }
    }
  }
/* If there are no inaccessible squares then the move is OK. */

if (inaccessible_squares == 0) move_found = 1;
}
void display_board (void)
{
int a;
int b;

for (b = 8; b > 0; b--)
  {
  printf("\n");
  for (a = 1; a < 9; a++)
    if (board [a] [b] < 10)
      printf("0%d ", board [a] [b]);
    else
      printf("%d ", board [a] [b]);
  }
printf("\n");
}

Once I had created this post, I copied and pasted the code from it (as suggested above) onto a machine running
Red Hat Linux release 6.2 (Zoot)
Kernel 2.2.14-5.0.
Then I compiled and ran it as follows:

Linux > cc kt01.c
Linux > mv a.out kt01
Linux > ./kt01

This is an answer
46 53 50 39 48 05 28 13
51 40 47 04 29 14 25 06
54 45 52 49 38 27 12 15
41 36 03 30 59 24 07 26
44 55 42 37 32 11 16 61
35 02 31 58 23 60 19 08
56 43 64 33 10 21 62 17
01 34 57 22 63 18 09 20
Linux >