Given a chess board, print all sequences of moves of a knight on a chessboard such that the knight visits every square only once.

For example, for standard 8 × 8 chessboard below is one such tour. We have started the tour from top-leftmost of the board (marked as 1) and consecutive moves of the knight are represented by the next number.

1 50 45 62 31 18 9 64

46 61 32 49 10 63 30 17

51 2 47 44 33 28 19 8

60 35 42 27 48 11 16 29

41 52 3 34 43 24 7 20

36 59 38 55 26 21 12 15

53 40 57 4 23 14 25 6

58 37 54 39 56 5 22 13

**Suggested Read:** Chess Knight Problem: Find Shortest path from source to destination

The Knight should search for a path from the starting position until it visits every square or until it exhausts all possibilities. We can easily achieve this with the help of backtracking. We start from given source square in the chessboard and recursively explore all eight paths possible to check if they leads to the solution or not. If current path doesn’t reach destination or we have explored all possible routes from the current square, we backtrack. To make sure that the path is simple and doesn’t contain any cycles, we keep track of squares involved in current path in an chessboard and before exploring any square, we ignore the square if it is already covered in current path.

We know that a knight can move in 8 possible directions from a given square as illustrated in below figure –

We can find all the possible locations the Knight can move to from the given location by using the array that stores the relative position of Knight movement from any location. For example, if the current location is (x, y), we can move to (x + row[k], y + col[k]) for 0 <= k <=7 using below array.

row[] = [ 2, 1, -1, -2, -2, -1, 1, 2, 2 ]

col[] = [ 1, 2, 2, 1, -1, -2, -2, -1, 1 ]

So, from a position (x, y) in the chessboard, the valid moves are:

(x + 2, y + 1)

(x + 1, y + 2)

(x – 1, y + 2)

(x – 2, y + 1)

(x – 2, y – 1)

(x – 1, y – 2)

(x + 1, y – 2)

(x + 2, y – 1)

**Important Note** – Please avoid changing sequence of above arrays. The order in which the Knight will move is circular and will be optimum. Using above order, we will get to a vacant position in few moves. Also, it is always better to start backtracking from any corner of chessboard. If we start from somewhere middle, the Knight can go to 8 different directions. If we start from corner, the knight can go to only two points from there. Since the algorithm is exponential, optimized input to it can make huge difference.

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include <bits/stdc++.h> using namespace std; // N x N chessboard #define N 5 // Below arrays details all 8 possible movements for a knight. // It is important to avoid changing sequence of below arrays int row[] = { 2, 1, -1, -2, -2, -1, 1, 2 , 2 }; int col[] = { 1, 2, 2, 1, -1, -2, -2, -1, 1 }; // Check if (x, y) is valid chess board coordinates // Note that a knight cannot go out of the chessboard bool isValid(int x, int y) { if (x < 0 || y < 0 || x >= N || y >= N) return false; return true; } // Recursive function to perform the Knight's tour using backtracking void KnightTour(int visited[N][N], int x, int y, int pos) { // mark current square as visited visited[x][y] = pos; // if all squares are visited, print the solution if (pos >= N*N) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) cout << visited[i][j] << " "; cout << endl; } cout << endl; // backtrack before returning visited[x][y] = 0; return; } // check for all 8 possible movements for a knight // and recurse for each valid movement for (int k = 0; k < 8; k++) { // Get the new position of Knight from current // position on chessboard int newX = x + row[k]; int newY = y + col[k]; // if new position is a valid and not visited yet if (isValid(newX, newY) && !visited[newX][newY]) KnightTour(visited, newX, newY, pos + 1); } // backtrack from current square and remove it from current path visited[x][y] = 0; } // Print all Possible Knight's Tours in a chessboard int main() { // visited[][] serves two purpose - // 1. It keep track of squares involved the Knight's tour. // 2. It stores the order in which the squares are visited int visited[N][N]; // initialize visited[][] by 0 (unvisited) memset(visited, 0, sizeof visited); int pos = 1; // start knight tour from corner square (0, 0) KnightTour(visited, 0, 0, pos); return 0; } |

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
class KnightTour { // N x N chessboard public static final int N = 5; // Below arrays details all 8 possible movements for a knight. // Don't change the sequence of below arrays public static final int row[] = { 2, 1, -1, -2, -2, -1, 1, 2 , 2 }; public static final int col[] = { 1, 2, 2, 1, -1, -2, -2, -1, 1 }; // Check if (x, y) is valid chess board coordinates // Note that a knight cannot go out of the chessboard private static boolean isValid(int x, int y) { if (x < 0 || y < 0 || x >= N || y >= N) return false; return true; } private static void print(int[][] visited) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { System.out.print(visited[i][j] + " "); } System.out.println(); } System.out.println(); } // Recursive function to perform the Knight's tour using backtracking public static void knightTour(int visited[][], int x, int y, int pos) { // mark current square as visited visited[x][y] = pos; // if all squares are visited, print the solution if (pos >= N*N) { print(visited); // backtrack before returning visited[x][y] = 0; return; } // check for all 8 possible movements for a knight // and recurse for each valid movement for (int k = 0; k < 8; k++) { // Get the new position of Knight from current // position on chessboard int newX = x + row[k]; int newY = y + col[k]; // if new position is a valid and not visited yet if (isValid(newX, newY) && visited[newX][newY] == 0) knightTour(visited, newX, newY, pos + 1); } // backtrack from current square and remove it from current path visited[x][y] = 0; } public static void main(String[] args) { // visited[][] serves two purpose - // 1. It keep track of squares involved the Knight's tour. // 2. It stores the order in which the squares are visited int visited[][] = new int[N][N]; int pos = 1; // start knight tour from corner square (0, 0) knightTour(visited, 0, 0, pos); } } |

`Output:`

1 6 15 10 21

14 9 20 5 16

19 2 7 22 11

8 13 24 17 4

25 18 3 12 23

1 6 11 18 21

12 17 20 5 10

7 2 15 22 19

16 13 24 9 4

25 8 3 14 23

1 6 11 16 21

12 15 20 5 10

7 2 13 22 17

14 19 24 9 4

25 8 3 18 23

1 6 17 12 21

16 11 20 5 18

7 2 9 22 13

10 15 24 19 4

25 8 3 14 23

.. and 300 other knight’s tour

The above backtracking solution for a knight’s tour is impractical on larger boards. For larger values of N, it is well beyond the capacity of modern computers (or networks of computers) to perform operations on such a large set.

**References:** https://en.wikipedia.org/wiki/Knight%27s_tour

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

wow thank you very much!!!

How about this algorithm:

`Initialize a queue with source node and mark it visited.`

Do while queue is not empty:

poll from the queue

getAllPossibleMovesFromSource which are not already visited - mark them visited and add to the queue.

return.

you are using bfs which is good for finding the shortest path but here you are required to find all paths.

What is the maximum value of n to find a solution for this using backtracking?

I developed, in some year, a quite complex algorithm in C (using brute forse with backtrack), able to find all and only the solutions for knight’s tour on squared tables from 5×5 to 10×10 order. Its use is relatively simple, its explanation would require much more time.

If you are interested, I could share with you the executable program first (a Windows-DOS or Linux-Terminal application), then the documentation (quite complete in its ideas) and finally the source code.

Today, on an Intel i5-6400 2.7GHz CPU the algorithm (compiled using gcc under Ubuntu 16.04) is able to find approximately 10000 solution per second per CPU-core, for a 8×8 table. The performance are a little bit worse on Windows.

I think that the real problem is not to print the solutions, but first accept the idea that the number of the solutions is embarrassingly huge, as easily seen in web literature (see, as an example OEIS sequence A165134).

Up today I confirmed (and you should too) the results find in OEIS up to the 7×7 order.

The 8×8 order confirmation will require, I suppose, a couple of centuries… 🙂

Sure Antonio. We would love to see your work. Just drop your email id using contact us form below and we will get back to you.

You can also write an article about your work and we will publish it. Let us know.