knight tour problem geeksforgeeks

Welcome.please sign up.

By signing up or logging in, you agree to our Terms of service and confirm that you have read our Privacy Policy .

Already a member? Go to Log In

Welcome.please login.

Forgot your password

Not registered yet? Go to Sign Up

Introduction
Analyze Your Algorithm
Growth of a Function
Analyze Iterative Algorithms
Recurrences
Let's Iterate
Now the Recursion
Master's Theorem
Sort It Out
Bubble Sort
Count and Sort
Divide and Conquer
Binary Search
Dynamic Programming
Knapsack Problem
Rod Cutting
Coin Change
Backtracking
Knight's Tour Problem
Greedy Algorithm
Activity Selection
Egyptian Fraction
Huffman Codes
Minimum Spanning Tree
Prim's Algorithm

Knight's Tour Problem | Backtracking

In the previous example of backtracking , you have seen that backtracking gave us a $O(n!)$ running time. Generally, backtracking is used when we need to check all the possibilities to find a solution and hence it is expensive. For the problems like N-Queen and Knight's tour, there are approaches which take lesser time than backtracking, but for a small size input like 4x4 chessboard, we can ignore the running time and the backtracking leads us to the solution.

Knight's tour is a problem in which we are provided with a NxN chessboard and a knight.

For a person who is not familiar with chess, the knight moves two squares horizontally and one square vertically, or two squares vertically and one square horizontally as shown in the picture given below.

Thus if a knight is at (3, 3), it can move to the (1, 2) ,(1, 4), (2, 1), (4, 1), (5, 2), (5, 4), (2, 5) and (4, 5) cells.

Thus, one complete movement of a knight looks like the letter "L", which is 2 cells long.

According to the problem, we have to make the knight cover all the cells of the board and it can move to a cell only once.

There can be two ways of finishing the knight move - the first in which the knight is one knight's move away from the cell from where it began, so it can go to the position from where it started and form a loop, this is called closed tour ; the second in which the knight finishes anywhere else, this is called open tour .

Approach to Knight's Tour Problem

Similar to the N-Queens problem, we start by moving the knight and if the knight reaches to a cell from where there is no further cell available to move and we have not reached to the solution yet (not all cells are covered), then we backtrack and change our decision and choose a different path.

So from a cell, we choose a move of the knight from all the moves available, and then recursively check if this will lead us to the solution or not. If not, then we choose a different path.

As you can see from the picture above, there is a maximum of 8 different moves which a knight can take from a cell. So if a knight is at the cell (i, j), then the moves it can take are - (i+2, j+1), (i+1, j+2), (i-2,j+1), (i-1, j+2), (i-1, j-2), (i-2, j-1), (i+1, j-2) and (i+2, j-1).

We keep the track of the moves in a matrix. This matrix stores the step number in which we visited a cell. For example, if we visit a cell in the second step, it will have a value of 2.

This matrix also helps us to know whether we have covered all the cells or not. If the last visited cell has a value of N*N, it means we have covered all the cells.

Thus, our approach includes starting from a cell and then choosing a move from all the available moves. Then we check if this move will lead us to the solution or not. If not, we choose a different move. Also, we store all the steps in which we are moving in a matrix.

Now, we know the basic approach we are going to follow. So, let's develop the code for the same.

Code for Knight's Tour

Let's start by making a function to check if a move to the cell (i, j) is valid or not - IS-VALID(i, j, sol) . As mentioned above, 'sol' is the matrix in which we are storing the steps we have taken.

A move is valid if it is inside the chessboard (i.e., i and j are between 1 to N) and if the cell is not already occupied (i.e., sol[i][j] == -1 ). We will make the value of all the unoccupied cells equal to -1.

As stated above, there is a maximum of 8 possible moves from a cell (i, j). Thus, we will make 2 arrays so that we can use them to check for the possible moves.

Thus if we are on a cell (i, j), we can iterate over these arrays to find the possible move i.e., (i+2, j+1), (i+1, j+2), etc.

Now, we will make a function to find the solution. This function will take the solution matrix, the cell where currently the knight is (initially, it will be at (1, 1)), the step count of that cell and the two arrays for the move as mentioned above - KNIGHT-TOUR(sol, i, j, step_count, x_move, y_move) .

We will start by checking if the solution is found. If the solution is found ( step_count == N*N ), then we will just return true.

KNIGHT-TOUR(sol, i, j, step_count, x_move, y_move) if step_count == N*N return TRUE

Our next task is to move to the next possible knight's move and check if this will lead us to the solution. If not, then we will select the different move and if none of the moves are leading us to the solution, then we will return false.

As mentioned above, to find the possible moves, we will iterate over the x_move and the y_move arrays.

KNIGHT-TOUR(sol, i, j, step_count, x_move, y_move) ... for k in 1 to 8 next_i = i+x_move[k] next_j = j+y_move[k]

Now, we have to check if the cell (i+x_move[k], j+y_move[k]) is valid or not. If it is valid then we will move to that cell - sol[i+x_move[k]][j+y_move[k]] = step_count and check if this path is leading us to the solution ot not - if KNIGHT-TOUR(sol, i+x_move[k], j+y_move[k], step_count+1, x_move, y_move) .

KNIGHT-TOUR(sol, i, j, step_count, x_move, y_move) ... for k in 1 to 8 ... if IS-VALID(i+x_move[k], j+y_move[k]) sol[i+x_move[k]][j+y_move[k]] = step_count if KNIGHT-TOUR(sol, i+x_move[k], j+y_move[k], step_count+1, x_move, y_move) return TRUE

If the move (i+x_move[k], j+y_move[k]) is leading us to the solution - if KNIGHT-TOUR(sol, i+x_move[k], j+y_move[k], step_count+1, x_move, y_move) , then we are returning true.

If this move is not leading us to the solution, then we will choose a different move (loop will iterate to a different move). Also, we will again make the cell (i+x_move[k], j+y_move[k]) of solution matrix -1 as we have checked this path and it is not leading us to the solution, so leave it and thus it is backtracking.

KNIGHT-TOUR(sol, i, j, step_count, x_move, y_move) ... for k in 1 to 8 ... sol[i+x_move[k], j+y_move[k]] = -1

At last, if none the possible move returns us false, then we will just return false.

We have to start the KNIGHT-TOUR function by passing the solution, x_move and y_move matrices. So, let's do this.

As stated earlier, we will initialize the solution matrix by making all its element -1.

for i in 1 to N for j in 1 to N sol[i][j] = -1

The next task is to make x_move and y_move arrays.

x_move = [2, 1, -1, -2, -2, -1, 1, 2] y_move = [1, 2, 2, 1, -1, -2, -2, -1]

We will start the tour of the knight from the cell (1, 1) as its first step. So, we will make the value of the cell(1, 1) 0 and then call KNIGHT-TOUR(sol, 1, 1, 1, x_move, y_move) .

Analysis of Code

We are not going into the full time complexity of the algorithm. Instead, we are going to see how bad the algorithm is.

There are N*N i.e., N 2 cells in the board and we have a maximum of 8 choices to make from a cell, so we can write the worst case running time as $O(8^{N^2})$.

But we don't have 8 choices for each cell. For example, from the first cell, we only have two choices.

Even considering this, our running time will be reduced by a factor and will become $O(k^{N^2})$ instead of $O(8^{N^2})$. This is also indeed an extremely bad running time.

So, this chapter was to make you familiar with the backtracking algorithm and not about the optimization. You can look for more examples on the backtracking algorithm with the backtracking tag of the BlogsDope .

Backtracking | Set 1 (The Knight's tour problem) | GeeksforGeeks

public class HorseStep {
static final int [] dx = { - 1 , - 2 , - 2 , - 1 , 1 , 2 , 2 , 1 }; // x方向的增量
static final int [] dy = { 2 , 1 , - 1 , - 2 , - 2 , - 1 , 1 , 2 }; // y方向的增量
static final int N = 8 ;
static int [][] board = new int [N][N]; // 棋盘
// 计算结点出口
int waysOut( int x, int y) {
int tx, ty;
int count = 0 ;
// 结点位置非法或已踏过，返回-1
if (x < 0 || y < 0 || x >= N || y >= N || board[x][y] > 0 ) {
return - 1 ;
}
for ( int i = 0 ; i < N; ++i) {
tx = x + dx[i];
ty = y + dy[i];
if (tx < 0 || ty < 0 || tx >= N || ty >= N) {
continue ;
}
if (board[tx][ty] == 0 ) {
count++;
return count;
}
// 按结点出口数，从小到大排序
void sortnode(HorseNode[] hn, int n) // 采用简单排序法，因为子结点数最多只有8
{
int i, j, t;
HorseNode temp;
for (i = 0 ; i < n; ++i) {
for (t = i, j = i + 1 ; j < n; ++j)
if (hn[j].waysOutNum < hn[t].waysOutNum)
t = j;
if (t > i) {
temp = hn[i];
hn[i] = hn[t];
hn[t] = temp;
// 搜索函数,count代表当前第几步
void dfs( int x, int y, int count) {
int i, tx, ty;
HorseNode[] tExit = new HorseNode[N]; // 记录出口结点的出口数
if (count > N * N) {
output();
return ;
// 计算[x,y]的出口结点和出口结点的出口数
for (i = 0 ; i < N; i++) {
HorseNode h = new HorseNode();
tExit[i] = h;
tExit[i].x = tx;
tExit[i].y = ty;
tExit[i].waysOutNum = waysOut(tx, ty);
sortnode(tExit, N);
for (i = 0 ; tExit[i].waysOutNum < 0 ; ++i)
;
for (; i < N; ++i){
tx = tExit[i].x;
ty = tExit[i].y;
board[tx][ty] = count;
dfs(tx, ty, count + 1 );
board[tx][ty] = 0 ;
public static void main(String[] args) {
int x = 1 ;
int y = 3 ;
HorseStep test = new HorseStep();
board[x][y] = 1 ;
test.dfs(x, y, 2 );
//打印结果
void output(){
for ( int i = N - 1 ; i >= 0 ; --i){
for ( int j = 0 ; j < N; ++j){
System.out.printf( "%2d " , board[i][j]);
System.out.println();
System.exit( 0 );
}
class HorseNode {
int x;
int y;
int waysOutNum;

The Top 10 favtutor Features You Might Have Overlooked

Don’t have an account Yet? Sign Up

Remember me Forgot your password?

Already have an Account? Sign In

Lost your password? Please enter your email address. You will receive a link to create a new password.

Back to log-in

By Signing up for Favtutor, you agree to our Terms of Service & Privacy Policy.

The Knight's Tour Problem (using Backtracking Algorithm)

Jun 30, 2023
6 Minute Read
Why Trust Us We uphold a strict editorial policy that emphasizes factual accuracy, relevance, and impartiality. Our content is crafted by top technical writers with deep knowledge in the fields of computer science and data science, ensuring each piece is meticulously reviewed by a team of seasoned editors to guarantee compliance with the highest standards in educational content creation and publishing.
By Vedanti Kshirsagar

Ever wondered how a computer playing as a chess player improves its algorithm to defeat you in the game? In this article, we will learn about the Knight's Tour Problem, the various ways to solve it along with their time and space complexities. So, let's get started!

What is Knight's Tour Problem?

Just for a reminder, the knight is a piece in chess that usually looks like a horse and moves in an L-shaped pattern. This means it will first move two squares in one direction and then one square in a perpendicular direction.

The Knight's Tour problem is about finding a sequence of moves for the knight on a chessboard such that it visits every square on the board exactly one time. It is a type of Hamiltonian path problem in graph theory, where the squares represent the vertices and the knight's moves represent the edges of the graph.

This problem has fascinated many mathematicians for centuries, but the solutions they found were very difficult. The simple solution will be to find every conceivable configuration and selecting the best one is one technique to solve this problem. But that will take a load of time.

One popular solution to solve the Knight's tour problem is Warnsdorff's rule, which involves choosing the next move that leads to a square with the fewest available moves. There is also a backtracking approach.

But first moving to all that, let's take a quick understanding of the Hamiltonian path problem.

Hamiltonian Path Problem

The Hamiltonian path problem is a well-known problem in graph theory that asks whether a given graph contains a path that visits every vertex exactly once.

A path that visits every vertex exactly once is called a Hamiltonian path, and a graph that contains a Hamiltonian path is called a Hamiltonian graph.

Let's take an example of the Hamiltonian path problem. Suppose we have a graph with five vertices and the following edges:

This graph can be represented as:

Knight's Tour Backtracking Algorithm

The backtracking algorithm works by exploring all possible moves for the knight, starting from a given square, and backtracking to try different moves if it reaches a dead end.

Here's the basic outline of the backtracking algorithm to solve the Knight's tour problem:

Choose a starting square for the knight on the chessboard.
Mark the starting square as visited.
For each valid move from the current square, make the move and recursively repeat the process for the new square.
If all squares on the chessboard have been visited, we have found a solution. Otherwise, undo the last move and try a different move.
If all moves have been tried from the current square and we have not found a solution, backtrack to the previous square and try a different move from there.
If we have backtracked to the starting square and tried all possible moves without finding a solution, there is no solution to the problem.

We have given the full C++ program for Backtracking Algorithm to solve Knight's Tour Problem below:

Check the image below before we explain the code:

In this implementation, we first define a function validMoves which takes the current row and column of the knight as input and returns a vector of pairs representing all the valid moves that the knight can make from that position.

The solve function is a recursive function that takes the current row and column of the knight, as well as the current move number, as input. We mark the current square as visited by setting board[row][column] it to the current move number, and then we recursively try all possible moves from the current position.

If we reach the last move, then we found a solution and return true. If no valid move is found from the current position, we backtrack by setting the current square to 0 and returning false.

In the main function, we start the solve function at a specified starting position and then output the number of moves it took to find a solution and print the final chessboard with the solution.

Time & Space Complexity for Backtracking

The backtracking algorithm used to solve the Knight's Tour problem has an exponential time complexity. The number of possible paths for the knight grows very quickly as the size of the chessboard increases, which means that the time taken to explore all possible paths grows exponentially.

The exact time complexity of the Knight's Tour Backtracking algorithm is O(8^(n^2)), where n is the size of the chessboard. This is because each move has a maximum of 8 possible directions, and we have to explore all possible moves until we find a solution.

The space complexity of the backtracking algorithm is O(n^2), where n is the size of the chessboard. So, we can say that the backtracking algorithm is efficient for smaller chessboards.

Warnsdorff's Rule

Warndorff's rule is a heuristic greedy algorithm used to solve this problem. It tries to move the knight to the square with the fewest valid moves, hoping that this will lead to a solution.

Here's an overview of how Warndorff's rule algorithm works:

Start with a random square on the chessboard.
From the current square, consider all possible moves and count the number of valid moves from each adjacent square.
Move to the square with the lowest number of valid moves. In case of a tie, move to the square with the lowest number of valid moves from its adjacent squares.
Repeat steps 2 and 3 until all squares on the chessboard have been visited.

Here is the pseudocode for Warndorff's rule algorithm:

The time complexity of Warndorff's rule algorithm is O(n^2 log n), where n is the size of the chessboard. This is because we have to visit each square once, and for each square, we have to compute the number of valid moves from each adjacent square. The space complexity of the algorithm is O(n^2) since we need to store the chessboard and the current position of the knight.

Overall, The Knight's Tour problem is related to chess, and solving it can help chess players improve their strategy and become better at the game. In the real world, you can also use it to design efficient algorithms for finding the shortest path between two points in a network.

Now we know The Knight's Tour Problem and its solutions using Backtracking and Warnsdorff's Rule. It has several applications in various fields such as Game theory, Network Routing etc, making it an important problem to study in computer science and mathematics.

FavTutor - 24x7 Live Coding Help from Expert Tutors!

About The Author

Vedanti Kshirsagar

More by favtutor blogs, monte carlo simulations in r (with examples), aarthi juryala.

The unlist() Function in R (with Examples)

Paired Sample T-Test using R (with Examples)

Practice Backtracking
Interview Problems on Backtracking
MCQs on Backtracking
Tutorial on Backtracking
Backtracking vs Recursion
Backtracking vs Branch & Bound
Print Permutations
Subset Sum Problem
N-Queen Problem
Knight's Tour
Sudoku Solver
Rat in Maze
Hamiltonian Cycle
Graph Coloring
Double Savings Offer on Courses
Share Your Experience
Backtracking Algorithm
Introduction to Backtracking - Data Structure and Algorithm Tutorials
Difference between Backtracking and Branch-N-Bound technique
What is the difference between Backtracking and Recursion?

Standard problems on backtracking

The Knight's tour problem
Rat in a Maze
N Queen Problem
Subset Sum Problem using Backtracking
M-Coloring Problem
Algorithm to Solve Sudoku | Sudoku Solver
Magnet Puzzle
Remove Invalid Parentheses
A backtracking approach to generate n bit Gray Codes
Permutations of given String

Easy Problems on Backtracking

Print all subsets of a given Set or Array
Check if a given string is sum-string
Count all possible Paths between two Vertices
Find all distinct subsets of a given set using BitMasking Approach
Find if there is a path of more than k length from a source
Print all paths from a given source to a destination
Print all possible strings that can be made by placing spaces

Medium prblems on Backtracking

8 queen problem
Combinational Sum
Warnsdorff's algorithm for Knight’s tour problem
Find paths from corner cell to middle cell in maze
Find Maximum number possible by doing at-most K swaps
Rat in a Maze with multiple steps or jump allowed
N Queen in O(n) space

Hard problems on Backtracking

Power Set in Lexicographic order
Word Break Problem using Backtracking
Partition of a set into K subsets with equal sum
Longest Possible Route in a Matrix with Hurdles
Find shortest safe route in a path with landmines
Printing all solutions in N-Queen Problem
Print all longest common sub-sequences in lexicographical order
Top 20 Backtracking Algorithm Interview Questions
DSA to Development Course

The Knight’s tour problem

Backtracking is an algorithmic paradigm that tries different solutions until finds a solution that “works”. Problems that are typically solved using the backtracking technique have the following property in common. These problems can only be solved by trying every possible configuration and each configuration is tried only once. A Naive solution for these problems is to try all configurations and output a configuration that follows given problem constraints. Backtracking works incrementally and is an optimization over the Naive solution where all possible configurations are generated and tried. For example, consider the following Knight’s Tour problem.

Problem Statement: Given a N*N board with the Knight placed on the first block of an empty board. Moving according to the rules of chess knight must visit each square exactly once. Print the order of each cell in which they are visited.

The path followed by Knight to cover all the cells Following is a chessboard with 8 x 8 cells. Numbers in cells indicate the move number of Knight.

Let us first discuss the Naive algorithm for this problem and then the Backtracking algorithm.

Naive Algorithm for Knight’s tour The Naive Algorithm is to generate all tours one by one and check if the generated tour satisfies the constraints.

Backtracking works in an incremental way to attack problems. Typically, we start from an empty solution vector and one by one add items (Meaning of item varies from problem to problem. In the context of Knight’s tour problem, an item is a Knight’s move). When we add an item, we check if adding the current item violates the problem constraint, if it does then we remove the item and try other alternatives. If none of the alternatives works out then we go to the previous stage and remove the item added in the previous stage. If we reach the initial stage back then we say that no solution exists. If adding an item doesn’t violate constraints then we recursively add items one by one. If the solution vector becomes complete then we print the solution.

Backtracking Algorithm for Knight’s tour

Following is the Backtracking algorithm for Knight’s tour problem.

Following are implementations for Knight’s tour problem. It prints one of the possible solutions in 2D matrix form. Basically, the output is a 2D 8*8 matrix with numbers from 0 to 63 and these numbers show steps made by Knight.

Time Complexity : There are N 2 Cells and for each, we have a maximum of 8 possible moves to choose from, so the worst running time is O(8 N^2 ).

Auxiliary Space: O(N 2 )

Important Note: No order of the xMove, yMove is wrong, but they will affect the running time of the algorithm drastically. For example, think of the case where the 8th choice of the move is the correct one, and before that our code ran 7 different wrong paths. It’s always a good idea a have a heuristic than to try backtracking randomly. Like, in this case, we know the next step would probably be in the south or east direction, then checking the paths which lead their first is a better strategy.

Note that Backtracking is not the best solution for the Knight’s tour problem. See the below article for other better solutions. The purpose of this post is to explain Backtracking with an example. Warnsdorff’s algorithm for Knight’s tour problem

References: http://see.stanford.edu/materials/icspacs106b/H19-RecBacktrackExamples.pdf http://www.cis.upenn.edu/~matuszek/cit594-2009/Lectures/35-backtracking.ppt http://mathworld.wolfram.com/KnightsTour.html http://en.wikipedia.org/wiki/Knight%27s_tour Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Please Login to comment...

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Data Structures & Algorithms
DSA - Overview
DSA - Environment Setup
DSA - Algorithms Basics
DSA - Asymptotic Analysis
Data Structures
DSA - Data Structure Basics
DSA - Data Structures and Types
DSA - Array Data Structure
Linked Lists
DSA - Linked List Data Structure
DSA - Doubly Linked List Data Structure
DSA - Circular Linked List Data Structure
Stack & Queue
DSA - Stack Data Structure
DSA - Expression Parsing
DSA - Queue Data Structure
Searching Algorithms
DSA - Searching Algorithms
DSA - Linear Search Algorithm
DSA - Binary Search Algorithm
DSA - Interpolation Search
DSA - Jump Search Algorithm
DSA - Exponential Search
DSA - Fibonacci Search
DSA - Sublist Search
DSA - Hash Table
Sorting Algorithms
DSA - Sorting Algorithms
DSA - Bubble Sort Algorithm
DSA - Insertion Sort Algorithm
DSA - Selection Sort Algorithm
DSA - Merge Sort Algorithm
DSA - Shell Sort Algorithm
DSA - Heap Sort
DSA - Bucket Sort Algorithm
DSA - Counting Sort Algorithm
DSA - Radix Sort Algorithm
DSA - Quick Sort Algorithm
Graph Data Structure
DSA - Graph Data Structure
DSA - Depth First Traversal
DSA - Breadth First Traversal
DSA - Spanning Tree
Tree Data Structure
DSA - Tree Data Structure
DSA - Tree Traversal
DSA - Binary Search Tree
DSA - AVL Tree
DSA - Red Black Trees
DSA - B Trees
DSA - B+ Trees
DSA - Splay Trees
DSA - Tries
DSA - Heap Data Structure
DSA - Recursion Algorithms
DSA - Tower of Hanoi Using Recursion
DSA - Fibonacci Series Using Recursion
Divide and Conquer
DSA - Divide and Conquer
DSA - Max-Min Problem
DSA - Strassen's Matrix Multiplication
DSA - Karatsuba Algorithm
Greedy Algorithms
DSA - Greedy Algorithms
DSA - Travelling Salesman Problem (Greedy Approach)
DSA - Prim's Minimal Spanning Tree
DSA - Kruskal's Minimal Spanning Tree
DSA - Dijkstra's Shortest Path Algorithm
DSA - Map Colouring Algorithm
DSA - Fractional Knapsack Problem
DSA - Job Sequencing with Deadline
DSA - Optimal Merge Pattern Algorithm
Dynamic Programming
DSA - Dynamic Programming
DSA - Matrix Chain Multiplication
DSA - Floyd Warshall Algorithm
DSA - 0-1 Knapsack Problem
DSA - Longest Common Subsequence Algorithm
DSA - Travelling Salesman Problem (Dynamic Approach)
Approximation Algorithms
DSA - Approximation Algorithms
DSA - Vertex Cover Algorithm
DSA - Set Cover Problem
DSA - Travelling Salesman Problem (Approximation Approach)
Randomized Algorithms
DSA - Randomized Algorithms
DSA - Randomized Quick Sort Algorithm
DSA - Karger’s Minimum Cut Algorithm
DSA - Fisher-Yates Shuffle Algorithm
DSA Useful Resources
DSA - Questions and Answers
DSA - Quick Guide
DSA - Useful Resources
DSA - Discussion
Selected Reading
UPSC IAS Exams Notes
Developer's Best Practices
Questions and Answers
Effective Resume Writing
HR Interview Questions
Computer Glossary

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 −

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.

In the following example, we will practically demonstrate how to solve the knight's tour problem.

Table of Contents
Scratch ActiveCode
Navigation Help
Help for Instructors
About Runestone
Report A Problem
1. Introduction
2. Analysis
3. Basic Data Structures
4. Recursion
5. Sorting and Searching
6. Trees and Tree Algorithms
7. Graphs and Graph Algorithms

7.13. Implementing Knight’s Tour ¶

The search algorithm we will use to solve the knight’s tour problem is called depth first search ( DFS ). Whereas the breadth first search algorithm discussed in the previous section builds a search tree one level at a time, a depth first search creates a search tree by exploring one branch of the tree as deeply as possible. In this section we will look at two algorithms that implement a depth first search. The first algorithm we will look at directly solves the knight’s tour problem by explicitly forbidding a node to be visited more than once. The second implementation is more general, but allows nodes to be visited more than once as the tree is constructed. The second version is used in subsequent sections to develop additional graph algorithms.

The depth first exploration of the graph is exactly what we need in order to find a path that has exactly 63 edges. We will see that when the depth first search algorithm finds a dead end (a place in the graph where there are no more moves possible) it backs up the tree to the next deepest vertex that allows it to make a legal move.

The knightTour function takes four parameters: n , the current depth in the search tree; path , a list of vertices visited up to this point; u , the vertex in the graph we wish to explore; and limit the number of nodes in the path. The knightTour function is recursive. When the knightTour function is called, it first checks the base case condition. If we have a path that contains 64 vertices, we return from knightTour with a status of True , indicating that we have found a successful tour. If the path is not long enough we continue to explore one level deeper by choosing a new vertex to explore and calling knightTour recursively for that vertex.

DFS also uses colors to keep track of which vertices in the graph have been visited. Unvisited vertices are colored white, and visited vertices are colored gray. If all neighbors of a particular vertex have been explored and we have not yet reached our goal length of 64 vertices, we have reached a dead end. When we reach a dead end we must backtrack. Backtracking happens when we return from knightTour with a status of False . In the breadth first search we used a queue to keep track of which vertex to visit next. Since depth first search is recursive, we are implicitly using a stack to help us with our backtracking. When we return from a call to knightTour with a status of False , in line 11, we remain inside the while loop and look at the next vertex in nbrList .

Let’s look at a simple example of knightTour in action. You can refer to the figures below to follow the steps of the search. For this example we will assume that the call to the getConnections method on line 6 orders the nodes in alphabetical order. We begin by calling knightTour(0,path,A,6)

knightTour starts with node A Figure 3 . The nodes adjacent to A are B and D. Since B is before D alphabetically, DFS selects B to expand next as shown in Figure 4 . Exploring B happens when knightTour is called recursively. B is adjacent to C and D, so knightTour elects to explore C next. However, as you can see in Figure 5 node C is a dead end with no adjacent white nodes. At this point we change the color of node C back to white. The call to knightTour returns a value of False . The return from the recursive call effectively backtracks the search to vertex B (see Figure 6 ). The next vertex on the list to explore is vertex D, so knightTour makes a recursive call moving to node D (see Figure 7 ). From vertex D on, knightTour can continue to make recursive calls until we get to node C again (see Figure 8 , Figure 9 , and Figure 10 ). However, this time when we get to node C the test n < limit fails so we know that we have exhausted all the nodes in the graph. At this point we can return True to indicate that we have made a successful tour of the graph. When we return the list, path has the values [A,B,D,E,F,C] , which is the the order we need to traverse the graph to visit each node exactly once.

Figure 3: Start with node A

Figure 4: Explore B

Figure 5: Node C is a dead end

Figure 6: Backtrack to B

Figure 7: Explore D

Figure 8: Explore E

Figure 9: Explore F

Figure 10: Finish

Figure 11 shows you what a complete tour around an eight-by-eight board looks like. There are many possible tours; some are symmetric. With some modification you can make circular tours that start and end at the same square.

Figure 11: A Complete Tour of the Board

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

Notifications

A recursive and backtracking algorithm implemented in Java for solving the Knight's Tour problem.

mahdiva/KnightsTour

Folders and files, repository files navigation, knights tour solver.

A recursive and backtracking algorithm implemented in Java for solving the Knight's Tour problem. This program will find all of the possible solutions to a Knight's Tour for any given m x n Chess board.

This project is licensed under the MIT License - see the LICENSE file for details.

Java 100.0%

Runestone in social media: Follow @iRunestone Our Facebook Page
Table of Contents
Assignments
Peer Instruction (Instructor)
Peer Instruction (Student)
Change Course
Instructor's Page
Progress Page
Edit Profile
Change Password
Scratch ActiveCode
Scratch Activecode
Instructors Guide
About Runestone
Report A Problem
8.1 Objectives
8.2 Vocabulary and Definitions
8.3 The Graph Abstract Data Type
8.4 An Adjacency Matrix
8.5 An Adjacency List
8.6 Implementation
8.7 The Word Ladder Problem
8.8 Building the Word Ladder Graph
8.9 Implementing Breadth First Search
8.10 Breadth First Search Analysis
8.11 The Knight’s Tour Problem
8.12 Building the Knight’s Tour Graph
8.13 Implementing Knight’s Tour
8.14 Knight’s Tour Analysis
8.15 General Depth First Search
8.16 Depth First Search Analysis
8.17 Topological Sorting
8.18 Strongly Connected Components
8.19 Shortest Path Problems
8.20 Dijkstra’s Algorithm
8.21 Analysis of Dijkstra’s Algorithm
8.22 Prim’s Spanning Tree Algorithm
8.23 Summary
8.24 Key Terms
8.25 Discussion Questions
8.26 Programming Exercises
8.12. Building the Knight’s Tour Graph" data-toggle="tooltip">
8.14. Knight’s Tour Analysis' data-toggle="tooltip" >

8.13. Implementing Knight’s Tour ¶

knightTour starts with node A Figure 3 . The nodes adjacent to A are B and D. Since B is before D alphabetically, DFS selects B to expand next as shown in Figure 4 . Exploring B happens when knightTour is called recursively. B is adjacent to C and D, so knightTour elects to explore C next. However, as you can see in Figure 5 node C is a dead end with no adjacent white nodes. At this point we change the color of node C back to white. The call to knightTour returns a value of False . The return from the recursive call effectively backtracks the search to vertex B (see Figure 6 ). The next vertex on the list to explore is vertex D, so knightTour makes a recursive call moving to node D (see Figure 7 ). From vertex D on, knightTour can continue to make recursive calls until we get to node C again (see Figure 8 , Figure 9 , and Figure 10 ). However, this time when we get to node C the test n < limit fails so we know that we have exhausted all the nodes in the graph. At this point we can return True to indicate that we have made a successful tour of the graph. When we return the list, path has the values [A,B,D,E,F,C] , which is the order we need to traverse the graph to visit each node exactly once.

Figure 3: Start with node A ¶

Figure 4: Explore B ¶

Figure 5: Node C is a dead end ¶

Figure 6: Backtrack to B ¶

Figure 7: Explore D ¶

Figure 8: Explore E ¶

Figure 9: Explore F ¶

Figure 10: Finish ¶

Figure 11: A Complete Tour of the Board ¶

Trending Now
Foundational Courses
Data Science
Practice Problem
Machine Learning
System Design
DevOps Tutorial

Embark on an exhilarating journey of exploration and optimization as we delve into the fascinating problem of finding a tour that visits all stations. In this comprehensive tutorial, we'll unravel the complexities of tour planning and guide you through the process of finding the optimal route to visit every station on your itinerary.

Join us as we navigate through the intricacies of tour optimization algorithms and discover efficient solutions to the tour problem. You'll learn about the importance of fuel management, station selection strategies, and route planning techniques to ensure a seamless and efficient tour experience.

Through detailed explanations, illustrative examples, and algorithmic insights, you'll gain a deep understanding of how to approach the tour problem and find the optimal solution. We'll explore various algorithms, including the greedy approach and its variations, to identify the most efficient tour route that covers all stations.

Whether you're a budding mathematician, a seasoned traveler, or a curious problem solver, this tutorial will equip you with the knowledge and skills to tackle the tour problem with confidence and precision. You'll learn valuable techniques for optimizing tour routes, minimizing fuel consumption, and maximizing efficiency.

Ready to embark on a journey of discovery and optimization? Dive into our tutorial now and unlock the secrets of finding the perfect tour that visits all stations. For further exploration and detailed insights, don't forget to check out the accompanying article on GeeksforGeeks: https://www.geeksforgeeks.org/find-a-tour-that-visits-all-stations/

Don't miss out on the opportunity to enhance your problem-solving skills and explore the fascinating world of tour optimization. Like, share, and subscribe for more tutorials and insights into computational thinking. Let's embark on the ultimate tour together. Happy exploring!

IMAGES

Knight Walk Problem explained💥
Knight Tour Problem Backtracking (Data Structures and Algorithms #8)(Recursion #5)(Backtracking #4)
The Knight's Tour Problem (using Backtracking Algorithm)
[Solved] Knight tour problem??
The Knight's Tour Problem (using Backtracking Algorithm)
Knight Tour Problem and Its Graph Analysis

VIDEO

Mã Đi Tuần
A closed Knight's Tour
The Knight's Tour Problem #graphs #chess
Constraints for movement of knight in system verilog
Learn to Code with Me: Kattis "Knight-Packing" Problem in Python, C++, and Java
Heuristic Solution to the Knight's Tour problem on a 14x14 board

COMMENTS

The Knight's tour problem
The Knight's tour problem. Backtracking is an algorithmic paradigm that tries different solutions until finds a solution that "works". Problems that are typically solved using the backtracking technique have the following property in common. These problems can only be solved by trying every possible configuration and each configuration is ...
Warnsdorff's algorithm for Knight's tour problem
Warnsdorff's algorithm for Knight's tour problem. Problem : A knight is placed on the first block of an empty board and, moving according to the rules of chess, must visit each square exactly once. Following is an example path followed by Knight to cover all the cells. The below grid represents a chessboard with 8 x 8 cells.
Print all Knight's tour possible from a starting ...
Approach: The problem can be solved with the help of Recursion and Backtracking by generating all the possible tours one by one and checking if it satisfies the given conditions. A more thorough explanation of the similar approach is discussed in the Knight's Tour Problem.Below are the steps to follow: Create a Recursive function to iterate over all possible paths that the Knight can follow.
Knight's tour problem using backtracking and its analysis
For the problems like N-Queen and Knight's tour, there are approaches which take lesser time than backtracking, but for a small size input like 4x4 chessboard, we can ignore the running time and the backtracking leads us to the solution. Knight's tour is a problem in which we are provided with a NxN chessboard and a knight.
Backtracking
A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once. If the knight ends on a square that is one knight's move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is closed, otherwise it is open.
Backtracking
Backtracking works in an incremental way to attack problems. Typically, we start from an empty solution vector and one by one add items (Meaning of item varies from problem to problem. In context of Knight's tour problem, an item is a Knight's move). When we add an item, we check if adding the current item violates the problem constraint ...
The Knight's Tour Problem (using Backtracking Algorithm)
The backtracking algorithm used to solve the Knight's Tour problem has an exponential time complexity. The number of possible paths for the knight grows very quickly as the size of the chessboard increases, which means that the time taken to explore all possible paths grows exponentially. The exact time complexity of the Knight's Tour ...
Lecture 24 Knight's Tour Problem
In this lecture, we will study about the knight tour problem, which is one of the standard problems of backtracking.Ultimate Recursion Series Playlist:https:...
Knight Tour Problem Backtracking (Data Structures and ...
This video explains how to solve famous knight tour problem from backtracking in recursion. Many variations of this problem are being asked in Microsoft, Goo...
Check Knight Tour Configuration
Check Knight Tour Configuration - There is a knight on an n x n chessboard. In a valid configuration, the knight starts at the top-left cell of the board and visits every cell on the board exactly once. You are given an n x n integer matrix grid consisting of distinct integers from the range [0, n * n - 1] where grid [row] [col] indicates that ...
7.11. The Knight's Tour Problem
7.11. The Knight's Tour Problem ¶. Another classic problem that we can use to illustrate a second common graph algorithm is called the "knight's tour.". The knight's tour puzzle is played on a chess board with a single chess piece, the knight. The object of the puzzle is to find a sequence of moves that allow the knight to visit ...
The Knight's tour problem
Typically, we start from an empty solution vector and one by one add items (Meaning of item varies from problem to problem. In the context of Knight's tour problem, an item is a Knight's move). When we add an item, we check if adding the current item violates the problem constraint, if it does then we remove the item and try other alternatives.
Knight's tour problem
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 ...
Knight's tour for maximum points
Output: 1. Explanation: minimum knight have to take 1 steps to gain maximum points. Initially, the knight has 0 coins, he will take 1 step to collect 1 point (sum of cells denoted in red color). Now in the second step, he can collect points from all the cells colored green i.e. 64 points. But with his magical power, at the 1st step, he can ...
7.13. Implementing Knight's Tour
7.13. Implementing Knight's Tour¶. The search algorithm we will use to solve the knight's tour problem is called depth first search (DFS).Whereas the breadth first search algorithm discussed in the previous section builds a search tree one level at a time, a depth first search creates a search tree by exploring one branch of the tree as deeply as possible.
PDF An efficient algorithm for the Knight's tour problem
The formal study of the knight's tour problem is said to have begun with Euler [lo] in 1759, who considered the standard 8 x 8 chessboard. Rouse Ball and Coxeter [l] give an interesting bibliography of the history of the problem from this point. Dudeney [8, 91 contains a description of exactly which rectangular chessboards have knight's ...
9.13. Implementing Knight's Tour
9.13. Implementing Knight's Tour¶. The search algorithm we will use to solve the knight's tour problem is called depth first search (DFS).Whereas the breadth first search algorithm discussed in the previous section builds a search tree one level at a time, a depth first search creates a search tree by exploring one branch of the tree as deeply as possible.
Minimum steps to reach target by a Knight
Given a square chessboard of N x N size, the position of the Knight and the position of a target are given. We need to find out the minimum steps a Knight will take to reach the target position. Examples: Input: Knight. knightPosition: (1, 3) , targetPosition: (5, 0) Output: 3. Explanation: In above diagram Knight takes 3 step to reach.
c++
The Knight's Tour problem can be stated as follows: Given a chess board with n × n squares, find a path for the knight that visits every square exactly once. Here is my code: #include <iostream>. #include <iomanip>. using namespace std; int counter = 1;
GitHub
A recursive and backtracking algorithm implemented in Java for solving the Knight's Tour problem. Topics. java recursion backtracking knights-tour Resources. Readme License. MIT license Activity. Stars. 0 stars Watchers. 0 watching Forks. 0 forks Report repository Releases No releases published. Packages 0. No packages published .
8.13. Implementing Knight's Tour
8.13. Implementing Knight's Tour¶. The search algorithm we will use to solve the knight's tour problem is called depth first search (DFS).Whereas the breadth first search algorithm discussed in the previous section builds a search tree one level at a time, a depth first search creates a search tree by exploring one branch of the tree as deeply as possible.
Newest 'knights-tour' Questions
Questions tagged [knights-tour] A knight's tour is a sequence of moves of a knight on a chessboard. Watch tag. Ignore tag. Learn more…. Top users. Synonyms.
Knight Walk
Interview Preparation. Menu. Back to Explore Page. Given a square chessboard, the initial position of Knight and position of a target. Find out the minimum steps a Knight will take to reach the target position.If it cannot reach the target position return -1.Note:The initial and the target position.
Finding first circular tour
Whether you're a budding mathematician, a seasoned traveler, or a curious problem solver, this tutorial will equip you with the knowledge and skills to tackle the tour problem with confidence and precision. You'll learn valuable techniques for optimizing tour routes, minimizing fuel consumption, and maximizing efficiency.