Knight’s Tour Problem Simply Explained

Introduction

This post is a continuation of the back tracking series. You can refer to other similar posts here. In this post we will be discussing the Knight’s Tour Problem. The problem states that, given a N * M chessboard, a Knight’s Tour is defined as the sequence of moves of a Knight, such that the Knight visits every square only once.

Does this sound similar?

Yes it is similar to finding the Hamiltonian Path as defined in this post.

Approach for solving the Knight’s Tour problem

Here I define the backtracking approach to solve this problem. Let the Knight start from any location (without the loss of generality, we can assume the start point to be 0,0)

For a Knight positioned on any cell of the board, there can be at most eight valid moves, which can be defined by the relative positions ({ { 2, 1 }, { 2, -1 }, { 1, 2 }, { 1, -2 }, { -2, 1 }, { -2, -1 },
{ -1, 2 }, { -1, -2 } }

Defining Safe Move

So let us define, which is a safe cell to move for the Knight. There are primarily three conditions:

  • The target cell must be within the boundaries of the board
  • It must not be visited already
  • It must be reachable from the current cell position y applying any of the above moves.

Defining the Strategy

Let us say that the Knight is at a position (r,c) and he has already covered k-1 cells and we have to choose the cell for the kth move. Then, the idea is to try out all the possible safe moves, and upon finding a safe move, just place the Knight at the newly identified cell and try the (k+1)th move.

But wait! What if somewhere down the line, we find that there are no safe moves and there are cells still remaining.

  • In such a case, we reject the partial solution and empty the previous cell after which this failure happened.
  • We continue to try the remaining moves for the cell again.
  • We repeat the process until we are able to cover all the cells as per the guidelines.

Source Code for the Knight’s Tour Problem

It might seem complicated, so let me put in a small piece of code and walk you through it:

Explanation

Let me try to explain the code.

This method is invoked after placing the Knight at cell (r, c). This is the first cell to be visited, in our case (0,0). Let us number it 0. There are four arguments to the method

  • the board itself
  • the row and column where the Knight is currently present
  • the number of the next move (this starts from zero)

Hence the argument to this method is (board, 0, 0, 1).

MAX_MOVES for a board is N*M, where N is the number of rows and M is the number of columns. For a 8 * 8 board MAX_MOVES will be 64. Line number 2 checks if we already covered all the cells. In that case, we simply print the complete board and this marks the end of one such Knight’s Tour.

The next line is a loop, which will allow us to try all the eight possible moves from the current Knight position.

  • It derives the next prospective row and column
  • Checks if it is safe to place a Knight their according to our safety rules
  • If found safe, places the Knight at the new row and column and invokes the method with new position and the next move in sequence.

This means, if the Knight is at (5,4) and it has already covered 10 cells, then the method would be invoked with (board, 5, 4, 11)

Now what happens if somewhere down the line, there is no more safe cells left, due to some decision wrongly made in the past?

In such a case, a false value is returned and it goes into the else part, where the previous cell is cleared off and it is believed that the choice made was incorrect, so try out a new choice. if this fails, then the process of clearing off cells propagates up the stack and other possibilities are examined.

Addition Code

Analysis

Here, the auxiliary space used is only due to the recursion stack, which at most can be of depth M*N, because at each invocation, we are reducing the problem size by 1 , initially the problem size is M*N, as we need to visit M*N cells.

The recurrence relation can be written as below. Where T(N) is the running time of a problem of size N.

T(N) = K * T(N-1) + O(1)

Here, K is the length of the MOVES array. The recursion tree branches by a factor of K in each level and there are N levels because the problem size reduces by 1 at each level. Following this argument, the number of nodes at level 2 would  be K^2 and similarly at level N it would be K^N.

Hence the running time would be proportional to K^N. Hence we can write T(N) = O(K^N).

Well the above is not a very accurate statement, because the tree might not always branch to a factor of K. For a 5*5 board, here is the possible number of valid moves at each position.

  • If the Knight is at a corner of the board, then there are only 2 possible moves, hence the branching factor there would be 2.
  • If the Knight is in the middle at cell (0,3) then there can be 4 possible moves, hence the branching factor would be 4.
  • For a Knight piece which is at the center of the board, there are 8 valid moves.
  • The branching factor very much depends on the position of the Knight.

Knight's Tour Problem

Hence, the running time should ideally be (K^N) where K is the average of all the branching factors.

Summary

To know more about the Knight’s Tour Problem, you can visit Wikipedia and read about various ideas and solutions. There are various other ways of solving this problem using Neural Networks and various other heuristics.

Please comment below, in case parts of this post are not clear. I would try to add a recursion tree and some more explanation.

  • Letícia P

    thanks, it’s the best explanation I ever seen.