Knight's tour problem
What is Knight's tour problem?
In the knight's tour problem, we are given with an empty chess board of size NxN, and a knight. In chess, the knight is a piece that looks exactly like a horse. Assume, it can start from any location on the board. Now, our task is to check whether the knight can visit all of the squares on the board or not. When it can visit all of the squares, then print the number of jumps needed to reach that location from the starting point.
There can be two ways in which a knight can finish its tour. In the first way, the knight moves one step and returns back to the starting position forming a loop which is called a closed tour. In the second way i.e. the open tour, it finishes anywhere in the board.
For a person who is not familiar with chess, note that the knight moves in a special manner. It can move either two squares horizontally and one square vertically or two squares vertically and one square horizontally in each direction. So, the complete movement looks like English letter 'L'.
Suppose the size of given chess board is 8 and the knight is at the top-left position on the board. The next possible moves are shown below −
Each cell in the above chess board holds a number, that indicates where to start and in how many moves the knight will reach a cell. The final values of the cell will be represented by the below matrix −
0 59 38 33 30 17 8 63 37 34 31 60 9 62 29 16 58 1 36 39 32 27 18 7 35 48 41 26 61 10 15 28 42 57 2 49 40 23 6 19 47 50 45 54 25 20 11 14 56 43 52 3 22 13 24 5 51 46 55 44 53 4 21 12
Remember, this problem can have multiple solutions, the above matrix is one possible solution.
One way to solve the knight's tour problem is by generating all the tours one by one and then checking if they satisfy the specified constraint or not. However, it is time consuming and not an efficient way.
Backtracking Approach to Solve Knight's tour problem
The other way to solve this problem is to use backtracking. It is a technique that tries different possibilities until a solution is found or all options are tried. It involves choosing a move, making it, and then recursively trying to solve the rest of the problem. If the current move leads to a dead end, we backtrack and undo the move, then try another one.
To solve the knight's tour problem using the backtracking approach, follow the steps given below −
Start from any cell on the board and mark it as visited by the knight.
Move the knight to a valid unvisited cell and mark it visited. From any cell, a knight can take a maximum of 8 moves.
If the current cell is not valid or not taking to the solution, then backtrack and try other possible moves that may lead to a solution.
Repeat this process until the moves of knight are equal to 8 x 8 = 64.
Example
In the following example, we will practically demonstrate how to solve the knight's tour problem.
#include <stdio.h>
#define N 8
int sol[N][N];
//check place is in range and not assigned yet
int isValid(int x, int y) {
return ( x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
}
void displaySolution() {
printf("The possible solution:
");
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++)
printf("%3d ", sol[x][y]);
printf("
");
}
}
int knightTour(int x, int y, int move, int xMove[N], int yMove[N]) {
int xNext, yNext;
//when the total board is covered
if (move == N*N)
return 1;
for (int k = 0; k < 8; k++) {
xNext = x + xMove[k];
yNext = y + yMove[k];
//check room is preoccupied or not
if (isValid(xNext, yNext)) {
sol[xNext][yNext] = move;
if (knightTour(xNext, yNext, move+1, xMove, yMove) == 1)
return 1;
else
// backtracking
sol[xNext][yNext] = -1;
}
}
return 0;
}
int findKnightTourSol() {
//initially set all values to -1 of solution matrix
for (int x = 0; x < N; x++)
for (int y = 0; y < N; y++)
sol[x][y] = -1;
//all possible moves for knight
int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
//starting from room (0, 0)
sol[0][0] = 0;
if (knightTour(0, 0, 1, xMove, yMove) == 0) {
printf("Solution does not exist");
return 0;
} else
displaySolution();
return 1;
}
int main() {
findKnightTourSol();
return 0;
}
#include <iostream>
#include <iomanip>
#define N 8
using namespace std;
int sol[N][N];
//check place is in range and not assigned yet
bool isValid(int x, int y, int sol[N][N]) {
return ( x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
}
void displaySolution() {
cout << "The possible solution: " << endl;
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++)
cout << setw(3) << sol[x][y] << " ";
cout << endl;
}
}
int knightTour(int x, int y, int move, int sol[N][N], int xMove[N], int yMove[N]) {
int xNext, yNext;
//when the total board is covered
if (move == N*N)
return true;
for (int k = 0; k < 8; k++) {
xNext = x + xMove[k];
yNext = y + yMove[k];
//check room is preoccupied or not
if (isValid(xNext, yNext, sol)) {
sol[xNext][yNext] = move;
if (knightTour(xNext, yNext, move+1, sol, xMove, yMove) == true)
return true;
else
// backtracking
sol[xNext][yNext] = -1;
}
}
return false;
}
bool findKnightTourSol() {
//initially set all values to -1 of solution matrix
for (int x = 0; x < N; x++)
for (int y = 0; y < N; y++)
sol[x][y] = -1;
//all possible moves for knight
int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
//starting from room (0, 0)
sol[0][0] = 0;
if (knightTour(0, 0, 1, sol, xMove, yMove) == false) {
cout << "Solution does not exist";
return false;
} else
displaySolution();
return true;
}
int main() {
findKnightTourSol();
}
import java.util.Arrays;
public class Main {
static final int N = 8;
static int[][] sol = new int[N][N];
//check place is in range and not assigned yet
static boolean isValid(int x, int y) {
return (x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
}
static void displaySolution() {
System.out.println("The possible solution: ");
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++)
System.out.printf("%3d ", sol[x][y]);
System.out.println();
}
}
static boolean knightTour(int x, int y, int move, int[] xMove, int[] yMove) {
int xNext, yNext;
//when the total board is covered
if (move == N*N)
return true;
for (int k = 0; k < 8; k++) {
xNext = x + xMove[k];
yNext = y + yMove[k];
//check room is preoccupied or not
if (isValid(xNext, yNext)) {
sol[xNext][yNext] = move;
if (knightTour(xNext, yNext, move+1, xMove, yMove))
return true;
else
// backtracking
sol[xNext][yNext] = -1;
}
}
return false;
}
static boolean findKnightTourSol() {
//initially set all values to -1 of solution matrix
for (int[] row : sol)
Arrays.fill(row, -1);
//all possible moves for knight
int[] xMove = {2, 1, -1, -2, -2, -1, 1, 2};
int[] yMove = {1, 2, 2, 1, -1, -2, -2, -1};
//starting from room (0, 0)
sol[0][0] = 0;
if (!knightTour(0, 0, 1, xMove, yMove)) {
System.out.println("Solution does not exist");
return false;
} else
displaySolution();
return true;
}
public static void main(String[] args) {
findKnightTourSol();
}
}
N = 8
# The solution matrix
sol = [[-1 for _ in range(N)] for _ in range(N)]
# Check if place is in range and not assigned yet
def isValid(x, y):
return (x >= 0 and x < N and y >= 0 and y < N and sol[x][y] == -1)
# Function to print the solution
def displaySolution():
print("The possible solution: ")
for x in range(N):
for y in range(N):
print(f"{sol[x][y]:3}", end=" ")
print()
# Recursive function to solve the problem
def knightTour(x, y, move, xMove, yMove):
if move == N*N:
return True
for k in range(8):
xNext = x + xMove[k]
yNext = y + yMove[k]
if isValid(xNext, yNext):
sol[xNext][yNext] = move
if knightTour(xNext, yNext, move+1, xMove, yMove):
return True
else:
# Backtracking
sol[xNext][yNext] = -1
return False
def findKnightTourSol():
# All possible moves for knight
xMove = [2, 1, -1, -2, -2, -1, 1, 2]
yMove = [1, 2, 2, 1, -1, -2, -2, -1]
# Starting from room (0, 0)
sol[0][0] = 0
if not knightTour(0, 0, 1, xMove, yMove):
print("Solution does not exist")
return False
else:
displaySolution()
return True
if __name__ == "__main__":
findKnightTourSol()
Output
The possible solution: 0 59 38 33 30 17 8 63 37 34 31 60 9 62 29 16 58 1 36 39 32 27 18 7 35 48 41 26 61 10 15 28 42 57 2 49 40 23 6 19 47 50 45 54 25 20 11 14 56 43 52 3 22 13 24 5 51 46 55 44 53 4 21 12
