knight's tour 4x4 solution

• 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

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 Login to comment...

Similar reads.

• Backtracking
• Mathematical
• chessboard-problems
• How to Strikethrough on Discord
• Discord Launches End-To-End Encryption For Audio & Video Chats
• iPadOS 18 is Now Available: Complete Features and How to Install
• Microsoft’s Latest 365 Copilot Updates: Enhanced AI Tools for Excel, PowerPoint, and Teams
• 10 Best PrimeWire Alternatives (2024)

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Chess videos, game analysis, chess theory and articles. Chess variants, sample games.

“Chess is the struggle against the error.” – Johannes Zukertort

Knight’s Tour: The famous mathematical problem

Chess is a game of strategy and foresight, demanding players to think several moves ahead to outmaneuver their opponents. Among the numerous puzzles and challenges that arise from the complexity of chess, the Knight’s Tour Problem stands out as a particularly fascinating conundrum. The Knight’s Tour is a puzzle that involves moving a knight on a chessboard in such a way that it visits each square exactly once.

The Knight’s Tour Problem is a mathematical challenge that revolves around finding a specific sequence of moves for a knight on a chessboard. It has become a popular problem assigned to computer science students, who are tasked with developing programs to solve it. The variations of the Knight’s Tour Problem go beyond the standard 8×8 chessboard, including different sizes and irregular, non-rectangular boards.

If you’re looking to find your own solution to the Knight’s Tour Problem, there is a straightforward approach known as Warnsdorff’s rule . Warnsdorff’s rule serves as a heuristic for discovering a single knight’s tour. The rule dictates that the knight should always move to the square from which it will have the fewest possible subsequent moves. In this calculation, any moves that would revisit a square already visited are not counted. By adhering to Warnsdorff’s rule, you can systematically guide the knight across the chessboard and ultimately find a knight’s tour.

Modern computers have significantly contributed to the exploration of the Knight’s Tour Problem. Through advanced algorithms and computational power, researchers have been able to tackle larger chessboards and refine existing solutions. However, finding a general solution that works for all chessboard sizes remains elusive.

In conclusion, the Knight’s Tour Problem continues to captivate mathematicians, chess players, and computer scientists alike. Its unique combination of chess strategy, mathematical intricacy, and computational challenges makes it a fascinating puzzle to explore. While the search for a comprehensive solution is ongoing, the journey towards unraveling the mysteries of the Knight’s Tour Problem offers valuable insights into the world of mathematics, algorithms, and the boundless potential of human intellect.

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Save my name, email, and website in this browser for the next time I comment.

News, Views & Insights

• Best of Blog (71)
• Astronomy (28)
• Computational Thinking (64)
• Current Events (36)
• Data Analysis and Visualization (138)
• Data Repository (11)
• Design (24)
• Developer Insights (76)
• Digital Humanities (7)
• Education (198)
• Events (44)
• Finance (24)
• Function Repository (12)
• Geosciences (12)
• High-Performance Computing (12)
• History (18)
• Image Processing (48)
• Life Sciences and Medicine (19)
• Machine Learning (16)
• Mathematica News (113)
• Mathematica Q&A (13)
• Mathematics (129)
• New Technology (42)
• Other Application Areas (138)
• Raspberry Pi (18)
• Recreational Computation (162)
• Software Development (35)
• System Modeler (50)
• Uncategorized (2)
• Wolfram Cloud (24)
• Wolfram Community (20)
• Wolfram Demonstrations Project (31)
• Wolfram Language (301)
• Wolfram News (279)
• Wolfram Notebooks (37)
• Wolfram U (31)
• Wolfram|Alpha (49)
• Wolfram|One (7)

The Student’s Guide to Wolfram

Yet more new ideas and new functions: launching version 14.1 of wolfram language & mathematica, from learning to leading: a chemist’s guide to wolfram technologies, solving the knight’s tour on and off the chess board.

I first came across the knight’s tour problem in the early ’80s when a performer on the BBC’s The Paul Daniels Magic Show demonstrated that he could find a route for a knight to visit every square on the chess board, once and only once, from a random start point chosen by the audience. Of course, the act was mostly showmanship, but it was a few years before I realized that he had simply memorized a closed (or reentrant) tour (one that ended back where he started), so whatever the audience chose, he could continue the same sequence from that point.

In college a few years later, I spent some hours trying, and failing, to find any knight’s tour, using pencil and paper in various systematic and haphazard ways. And for no particular reason, this memory came to me while I was driving to work today, along with the realization that the problem can be reduced to finding a Hamiltonian cycle —a closed path that visits every vertex—of the graph of possible knight moves. Something that is easy to do in Mathematica . Here is how.

The first thing that we have to do is construct the graph of knight moves. A knight can move to eight possible squares in the open, but as few as two in the corners. But if you ignore that and think of when you were taught chess, you were probably told that a knight could move along two and across one, or vice versa. This gives the knight the property that it always moves a EuclideanDistance of √ 5 . We can use this test to construct the edges of our graph from the list of all possible pairs of positions.

Sorting removes unhelpful multiple edges that just slow the computation down. Ignoring chess conventions, I choose x and y to both take values 1–8 (rather than x being from A to H).

Now that we have the graph, we can find a tour.

Which looks very nice visualized on a chess board.

I understand that this problem is often used as an exercise in computer science courses, and you can find some iterative solutions and specific solutions at demonstrations.wolfram.com . But at four lines, this graph theory solution isn’t too much of a challenge. Indeed, it seemed a little unsatisfying to stop here.

Giving FindHamiltonianCycle a second argument finds more than one tour. But scrolling through a notebook of the first 1,000 didn’t reveal anything interesting. And the properties of differently sized chess boards have been well studied. So I decided to extend the idea in a slightly more whimsical way.

Oddly, all the definitions of a knight’s tour that I found on the web assume a rectangular space. Indeed, Mathematica contains a built-in function KnightTourGraph , which does roughly the same as my knightGraph function, but assumes a rectangular grid. But if I bring in Mathematica ‘s image processing, it is easy to generate the knight’s tour graph over points in non-rectangular shapes, like this:

First I Binarize the pixels of some source image. The knight is allowed to visit the black pixels in the result, but not the white. Then I get the coordinates of the black pixels and map them to the coordinate space of my plotting function.

Now I just solve and plot that graph as before, but this time visualize with the black pixels, instead of a chess-board grid.

It turns out that most irregular shapes do not have a closed knight’s tour, but messing around with the image size can find exceptions. So a bit of search code is needed. This one takes a single character, rasterizes it at different font sizes, and returns the size for which a tour exists. The Monitor part lets you watch the progress; tour finding scales poorly and can get very slow if you let the font sizes grow too big.

Let’s start by searching simple filled circles.

So out of the 42 sizes tested, only these 5 have solutions. The smaller, more crowded font sizes produce more irregular tour paths.

But larger image sizes make the shape more recognizable.

Playing around with other characters is amusing for a while. Here is the letter “o” in 34 point:

An asterisk at 52 point:

And since chess puts us firmly in the “games” space, here are some playing card suits:

And finally my rendition of Pacman:

Feel free to share any interesting discoveries in the comments section.

Download this post as a Computable Document Format (CDF) file.

! Please enter your comment (at least 5 characters).

! Please enter your name.

! Please enter a valid email address.

10 comments

I think it should be pointed out that the tour computed for the club-shaped board is not strictly valid. One of the knight jumps requires it to move off the board and two squares are not visited.

Well spotted, I didn’t notice that!

I think this should be fixed by replacing “Graph[” line in knightGraph with “Graph[pts,”, which includes all vertices in the definition of a graph – which again makes it impossible knight’s tour to succeed as vertices without edges are impossible to visit.

While it was pointed out to me, during proof reading, that there would be objections about the knight jumping over a gap, I consider that a valid move. I have always though of the knight as a “flying” piece. It doesn’t care about pieces in the way, so shouldn’t care about gap.

However, we all missed my bug that you point out about the unvisited squares. The cause was correctly diagnosed by kirma in the next comment.

The fix is to change knightGraph to ensure that all the points are vertices of the output Graph even if they are not connected. I think just adding pts as the first argument for Graph will do it…

knightGraph[pts_] := Graph[pts, Union[Flatten[Table[If[EuclideanDistance[x, y] == Sqrt[5], Sort[UndirectedEdge[x, y]], {}], {x, pts}, {y, pts}]]]];

In the case of the ClubSuit it will now return an unconnected Graph which is unsolvable.

A small note: knightGraph constructs an incorrect graph for Hamiltonian cycle checking if one or more of the points involved have no neighbours at a distance of Sqrt[5]. This makes FindHamiltonianCycle find tours that actually don’t visit every specified square.

Additional checking for such squares is easy, though.

Interesting timing. I just posted about Knight’s Tour literally minutes ago (using a simple backtracking solution): https://blog.jverkamp.com/2014/09/04/chess-puzzles-knights-tour/

Generating arbitrary boards from images is a really cool idea though. I may have to borrow that. :)

Mike Dupuis and I, with the help of Mathematica, recently characterized all rectangular boards for which the knight graph is “laceable”: there is a Ham. path from any point to any other point (of opposite color).

For the 8×8 I have ALL the paths in a demo at http://demonstrations.wolfram.com/LaceableKnightGraphs/

The paper is at http://amc-journal.eu/index.php/amc/issue/view/22 (last item)

A very difficult magic trick is to ask someone to pick one white and one black square and make a Ham. path from one to the other!

A paper about similar things in the game of hex chess will appear soon in College Math Journal: lots of nice open questions.

Thanks for a great blog on a fascinating topic. Some similar work sits in the archives; use of shapes has been explored by Ryohei Miyadera, et al., http://library.wolfram.com/infocenter/MathSource/6714/ but the ability to use symbols to generate board shapes is neat. The work by Arnd Roth, http://library.wolfram.com/infocenter/MathSource/909/ is also interesting, but his use of symmetry and Euclidean distance in his algorithm leads to it being weak when there are asymmetric board shapes. The results of searching for suitable point sizes depends on the monitor settings; my dated equipment gives In[29]:=characterSizeFinder[“*”, 60] Out[29]= {13, 14} whereas the blog gives a result for point size of 52. Can the code be altered to give results independent of hardware?

The font used is the culprit giving different results for differing point size, so the monitor lives to display another session.

How would I calculate all the knight’s tours for a 6×28 matrix?

Related Posts

Can you Solve the Knight's Tour Math Problem?

Solving the "Knight's Tour" math problem involves moving the knight about the chessboard such that each square is visited exactly once. Visualizing the chessboard as 4 quadrants, memorizing a small group of patterns within each quadrant, and following a few simple principles while calculating the knight moves will allow you to find a solution to this fun mathematical problem. It's an intuitive puzzle to challenge a friend, math teacher, or even a math classroom with. ★ FACEBOOK http://facebook.com/ChessNetwork ★ TWITTER http://twitter.com/ChessNetwork ★ GOOGLE+ http://google.com/+ChessNetwork ★ LIVESTREAM http://twitch.tv/ChessNetwork

• A Knight’s Tour

The “ knight’s tour ” is a classic problem in graph theory, first posed over 1,000 years ago and pondered by legendary mathematicians including Leonhard Euler before finally being solved in 1823. We will use the knight’s tour problem to illustrate a second common graph algorithm called depth first search.

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 every square on the board exactly once, like so:

One such sequence is called a “tour.” The upper bound on the number of possible legal tours for an eight-by-eight chessboard is known to be 1 . 3 0 5 × 1 0 3 5 1.305 \times 10^{35} 1 . 3 0 5 × 1 0 ​ 3 5 ​ ​ ; however, there are even more possible dead ends. Clearly this is a problem that requires some real brains, some real computing power, or both.

Once again we will solve the problem using two main steps:

• Represent the legal moves of a knight on a chessboard as a graph.
• Use a graph algorithm to find a path where every vertex on the graph is visited exactly once.

Building the Knight’s Tour Graph

To represent the knight’s tour problem as a graph we will use the following two ideas: Each square on the chessboard can be represented as a node in the graph. Each legal move by the knight can be represented as an edge in the graph.

We will use a Python dictionary to hold our graph, with the keys being tuples of coordinates representing the squares of the board, and the values being sets representing the valid squares to which a knight can move from that square.

To build the full graph for an n-by-n board we can use the Python function shown below. The build_graph function makes one pass over the entire board. At each square on the board the build_graph function calls a helper generator, legal_moves_from , to generate a list of legal moves for that position on the board. All legal moves are then made into undirected edges of the graph by adding the vertices appropriately to one anothers sets of legal moves.

The legal_moves_from generator below takes the position of the knight on the board and yields any of the eight possible moves that are still on the board.

The illustration below shows the complete graph of possible moves on an eight-by-eight board. There are exactly 336 edges in the graph. Notice that the vertices corresponding to the edges of the board have fewer connections (legal moves) than the vertices in the middle of the board. Once again we can see how sparse the graph is. If the graph was fully connected there would be 4,096 edges. Since there are only 336 edges, the adjacency matrix would be only 8.2 percent full.

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.

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 find_solution_for function takes just two arguments: a board_size argument and a heuristic function, which you should ignore for now but to which we will return.

It then constructs a graph using the build_graph function described above, and for each vertex in the graph attempts to traverse depth first by way of the traverse function.

The traverse function is a little more interesting. It accepts a path, as a list of coordinates, as well as the vertex currently being considered. If the traversal has proceeded deep enough that we know that every square has been visited once, then we return the full path traversed.

Otherwise, we use our graph to look up the legal moves from the current vertex, and exclude the vertices that we know have already been visited, to determine the vertices that are yet_to_visit . At this point we recursively call traverse with each of the vertices to visit, along with the path to reach that vertex including the current vertex. If any of the recursive calls return a path, then that path is the return value of the outer call, otherwise we return None.

Let’s look at a simple example of an equivalent of this traverse function in action.

It is remarkable that our choice of data structure and algorithm has allowed us to straightforwardly solve a problem that remained impervious to thoughtful mathematical investigation for centuries.

With some modification, the algorithm can also be used to discover one of a number of “closed” (circular) tours, which can therefore be started at any square of the board:

Knight’s Tour Analysis

There is one last interesting topic regarding the knight’s tour problem, then we will move on to the general version of the depth first search. The topic is performance. In particular, our algorithm is very sensitive to the method you use to select the next vertex to visit. For example, on a five-by-five board you can produce a path in about 1.5 seconds on a reasonably fast computer. But what happens if you try an eight-by-eight board? In this case, depending on the speed of your computer, you may have to wait up to a half hour to get the results! The reason for this is that the knight’s tour problem as we have implemented it so far is an exponential algorithm of size O ( k N ) O(k^N) O ( k ​ N ​ ​ ) , where N is the number of squares on the chess board, and k is a small constant. The diagram below can help us visualize why this is so.

The root of the tree represents the starting point of the search. From there the algorithm generates and checks each of the possible moves the knight can make. As we have noted before the number of moves possible depends on the position of the knight on the board. In the corners there are only two legal moves, on the squares adjacent to the corners there are three and in the middle of the board there are eight. The diagram below shows the number of moves possible for each position on a board. At the next level of the tree there are once again between 2 and 8 possible next moves from the position we are currently exploring. The number of possible positions to examine corresponds to the number of nodes in the search tree.

We have already seen that the number of nodes in a binary tree of height N is 2 N + 1 − 1 2^{N+1}-1 2 ​ N + 1 ​ ​ − 1 . For a tree with nodes that may have up to eight children instead of two the number of nodes is much larger. Because the branching factor of each node is variable, we could estimate the number of nodes using an average branching factor. The important thing to note is that this algorithm is exponential: k N + 1 − 1 k^{N+1}-1 k ​ N + 1 ​ ​ − 1 , where k k k is the average branching factor for the board. Let’s look at how rapidly this grows! For a board that is 5x5 the tree will be 25 levels deep, or N = 24 counting the first level as level 0. The average branching factor is k = 3 . 8 k = 3.8 k = 3 . 8 So the number of nodes in the search tree is 3 . 8 2 5 − 1 3.8^{25}-1 3 . 8 ​ 2 5 ​ ​ − 1 or 3 . 1 2 × 1 0 1 4 3.12 \times 10^{14} 3 . 1 2 × 1 0 ​ 1 4 ​ ​ . For a 6x6 board, k = 4 . 4 k = 4.4 k = 4 . 4 , there are 1 . 5 × 1 0 2 3 1.5 \times 10^{23} 1 . 5 × 1 0 ​ 2 3 ​ ​ nodes, and for a regular 8x8 chess board, k = 5 . 2 5 k = 5.25 k = 5 . 2 5 , there are 1 . 3 × 1 0 4 6 1.3 \times 10^{46} 1 . 3 × 1 0 ​ 4 6 ​ ​ . Of course, since there are multiple solutions to the problem we won’t have to explore every single node, but the fractional part of the nodes we do have to explore is just a constant multiplier which does not change the exponential nature of the problem. We will leave it as an exercise for you to see if you can express k k k as a function of the board size.

Luckily there is a way to speed up the eight-by-eight case so that it runs in under one second. In the code sample below we show the code that speeds up the traverse . This function, called warnsdorffs_heuristic when passed as the heuristic function to find_solution_for above will cause the next_vertices to be sorted prioritizing those who which have the fewest subsequent legal moves.

This may seem counterintutitive; why not select the node that has the most available moves? The problem with using the vertex with the most available moves as your next vertex on the path is that it tends to have the knight visit the middle squares early on in the tour. When this happens it is easy for the knight to get stranded on one side of the board where it cannot reach unvisited squares on the other side of the board. On the other hand, visiting the squares with the fewest available moves first pushes the knight to visit the squares around the edges of the board first. This ensures that the knight will visit the hard-to- reach corners early and can use the middle squares to hop across the board only when necessary. Utilizing this kind of knowledge to speed up an algorithm is called a heuristic. Humans use heuristics every day to help make decisions, heuristic searches are often used in the field of artificial intelligence. This particular heuristic is called Warnsdorff’s heuristic, named after H. C. Warnsdorff who published his idea in 1823, becoming the first person to describe a procedure to complete the knight’s tour.

For fun, here is a very large ( 1 3 0 × 1 3 0 130 \times 130 1 3 0 × 1 3 0 ) open knight’s tour created using Warnsdorff’s heuristic:

• The Big Picture
• Big O Notation
• An Anagram Detection Example
• Performance of Python Types
• Introduction to Stacks
• A Stack Implementation
• Balanced Parentheses
• Converting Number Bases
• Infix, Prefix and Postfix Expressions
• Introduction to Queues
• A Queue Implementation
• Simulating Hot Potato
• Introduction to Deques
• A Deque Implementation
• Palindrome Checker
• Introduction to Lists
• Implementing an Unordered List
• Implementing an Ordered List
• Introduction to Recursion
• Calculating the Sum of a List of Numbers
• The Three Laws of Recursion
• Converting an Integer to Any Base
• Tower of Hanoi
• Dynamic Programming
• The Sequential Search
• The Binary Search
• Introduction to Trees
• Representing a Tree
• Parse Trees
• Tree Traversals
• Priority Queues with Binary Heaps
• Binary Search Trees
• Introduction to Graphs
• Representing a Graph
• Word Ladders
• General Depth First Search
• Topological Sorting
• Shortest Path with Dijkstra’s Algorithm
• Strongly Connected Components
• Prim’s Spanning Tree Algorithm

• Table of Contents
• Course Home
• 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
• 9.1 Objectives
• 9.2 Vocabulary and Definitions
• 9.3 The Graph Abstract Data Type
• 9.4 An Adjacency Matrix
• 9.5 An Adjacency List
• 9.6 Implementation
• 9.7 The Word Ladder Problem
• 9.8 Building the Word Ladder Graph
• 9.9 Implementing Breadth First Search
• 9.10 Breadth First Search Analysis
• 9.11 The Knight’s Tour Problem
• 9.12 Building the Knight’s Tour Graph
• 9.13 Implementing Knight’s Tour
• 9.14 Knight’s Tour Analysis
• 9.15 General Depth First Search
• 9.16 Depth First Search Analysis
• 9.17 Topological Sorting
• 9.18 Strongly Connected Components
• 9.19 Shortest Path Problems
• 9.20 Dijkstra’s Algorithm
• 9.21 Analysis of Dijkstra’s Algorithm
• 9.22 Prim’s Spanning Tree Algorithm
• 9.23 Summary
• 9.24 Discussion Questions
• 9.25 Programming Exercises
• 9.26 Glossary
• 9.13. Implementing Knight’s Tour" data-toggle="tooltip">
• 9.15. General Depth First Search' data-toggle="tooltip" >

Before you keep reading...

Runestone Academy can only continue if we get support from individuals like you. As a student you are well aware of the high cost of textbooks. Our mission is to provide great books to you for free, but we ask that you consider a $10 donation, more if you can or less if $10 is a burden.

Making great stuff takes time and $$. If you appreciate the book you are reading now and want to keep quality materials free for other students please consider a donation to Runestone Academy. We ask that you consider a $10 donation, but if you can give more thats great, if $10 is too much for your budget we would be happy with whatever you can afford as a show of support.

9.14. Knight’s Tour Analysis ¶

There is one last interesting topic regarding the knight’s tour problem, then we will move on to the general version of the depth first search. The topic is performance. In particular, knightTour is very sensitive to the method you use to select the next vertex to visit. For example, on a five-by-five board you can produce a path in about 1.5 seconds on a reasonably fast computer. But what happens if you try an eight-by-eight board? In this case, depending on the speed of your computer, you may have to wait up to a half hour to get the results! The reason for this is that the knight’s tour problem as we have implemented it so far is an exponential algorithm of size \(O(k^N)\) , where N is the number of squares on the chess board, and k is a small constant. Figure 12 can help us visualize why this is so. The root of the tree represents the starting point of the search. From there the algorithm generates and checks each of the possible moves the knight can make. As we have noted before the number of moves possible depends on the position of the knight on the board. In the corners there are only two legal moves, on the squares adjacent to the corners there are three and in the middle of the board there are eight. Figure 13 shows the number of moves possible for each position on a board. At the next level of the tree there are once again between 2 and 8 possible next moves from the position we are currently exploring. The number of possible positions to examine corresponds to the number of nodes in the search tree.

Figure 12: A Search Tree for the Knight’s Tour ¶

Figure 13: Number of Possible Moves for Each Square ¶

We have already seen that the number of nodes in a binary tree of height N is \(2^{N+1}-1\) . For a tree with nodes that may have up to eight children instead of two the number of nodes is much larger. Because the branching factor of each node is variable, we could estimate the number of nodes using an average branching factor. The important thing to note is that this algorithm is exponential: \(k^{N+1}-1\) , where \(k\) is the average branching factor for the board. Let’s look at how rapidly this grows! For a board that is 5x5 the tree will be 25 levels deep, or N = 24 counting the first level as level 0. The average branching factor is \(k = 3.8\) So the number of nodes in the search tree is \(3.8^{25}-1\) or \(3.12 \times 10^{14}\) . For a 6x6 board, \(k = 4.4\) , there are \(1.5 \times 10^{23}\) nodes, and for a regular 8x8 chess board, \(k = 5.25\) , there are \(1.3 \times 10^{46}\) . Of course, since there are multiple solutions to the problem we won’t have to explore every single node, but the fractional part of the nodes we do have to explore is just a constant multiplier which does not change the exponential nature of the problem. We will leave it as an exercise for you to see if you can express \(k\) as a function of the board size.

Luckily there is a way to speed up the eight-by-eight case so that it runs in under one second. In the listing below we show the code that speeds up the knightTour . This function (see Listing 4 ), called orderbyAvail will be used in place of the call to u.getConnections in the code previously shown above. The critical line in the orderByAvail function is line 10. This line ensures that we select the vertex to go next that has the fewest available moves. You might think this is really counter productive; why not select the node that has the most available moves? You can try that approach easily by running the program yourself and inserting the line resList.reverse() right after the sort.

The problem with using the vertex with the most available moves as your next vertex on the path is that it tends to have the knight visit the middle squares early on in the tour. When this happens it is easy for the knight to get stranded on one side of the board where it cannot reach unvisited squares on the other side of the board. On the other hand, visiting the squares with the fewest available moves first pushes the knight to visit the squares around the edges of the board first. This ensures that the knight will visit the hard-to-reach corners early and can use the middle squares to hop across the board only when necessary. Utilizing this kind of knowledge to speed up an algorithm is called a heuristic. Humans use heuristics every day to help make decisions, heuristic searches are often used in the field of artificial intelligence. This particular heuristic is called Warnsdorff’s algorithm, named after H. C. Warnsdorff who published his idea in 1823.

The visualization below depicts the full process of a Knight’s Tour solution. It portrays the visitation of every spot on the chess board and an analysis on all neighboring locations, and finishes by showing the final solution wherein all locations on the chess board have been visited. The Warnsdorff heuristic is used in this visualization, so all neighbors with less moves are prioritized over neighbors with more moves. The individual components of the visualization are indicated by color and shape, which is described below.

The currently focused point on the chess board is a black circle.

Neighbors of that point that are being examined are higlighted in blue hexagon.

Distant neighbors are orange or brown triangles.

Triangles are orange if the spot on the chess board has not been visited yet.

Triangles are brown if the spot on the chess board has already been visited.

Q-2: What is the big O of the Knight’s Tour function?

• You are correct! K is a small constant, and N is the total number of vertices (or spaces on a chessboard).
• No, the Knight's Tour is not linear.
• No, the Knight's Tour does not have a nested loop that iterates through all values twice.
• No, the input is not processed in a fashion indicative of a factorial.

Using the Knight's Tour to impress

It is the program of choice for anyone who loves the game and wants to know more about it. Start your personal success story with ChessBase and enjoy the game even more.

ONLINE SHOP

Najdorf: a dynamic grandmaster repertoire against 1.e4 vol.1 & 2.

In the first part of the video series, we will look at White’s four main moves: 6. Bg5, 6. Be3, 6. Be2 and 6. Bc4.

€69.90

How to exchange pieces

Learn to master the right exchange! Let the German WGM Elisabeth Pähtz show you how to gain a strategic winning position by exchanging pieces of equal value or to safely convert material advantage into a win.

How to play the Sicilian Defence!

The continuous stream of new ideas in the Sicilian makes 1..c5 the most popular answer to 1.e4. On this DVD I do give an introduction to the most important Sicilian systems.

User   Password  

Not registered yet? Register

ChessBase 17 and Opening Encyclopaedia 2024

It is the program of choice for anyone who loves the game and wants to know more about it.

€299.90

Revealing Modern Grandmaster Secrets Vol. 1 – Attacking the King, Opening Ideas and Initiative

This isn’t just another chess tutorial—it’s your all-access pass to the strategies, insights, and techniques that define modern grandmaster play.

€39.90

Revealing Modern Grandmaster Secrets Vol. 2 – Calculation, Countering & Defence, Positional Play and the King

Revealing Modern Grandmaster Secrets Vol. 1 & 2

ChessBase Magazine 221

Biel 2024 Chess Festival with analyses by Le Quang Liem, Donchenko, Bjerre and others. Sokolov, King and Zwirs show new opening ideas in the video. 10 repertoire articles from the Dutch to King's Indian and much more.

€21.90

Counter the Nimzo-Indian Defence with Kramnik's Winning Strategy

Former World Champion Vladimir Kramnik discovered a unique way to combat the Nimzo-Indian through an alternative move order: 1.Nf3 Nf6 2.c4 e6 3.Nc3 Bb4 4.g3/Qb3

Unlock the Power of the Old Benoni

This approach is perfect for players who thrive on deep planning and subtle tactics, especially when facing aggressive or impatient opponents.

Sicilian Paulsen Powerbase 2024

The Sicilian Paulsen Powerbase 2024 is a database and contains a total of 8020 games, 754 of which are annotated.

Pop-up for detailed settings

We use cookies and comparable technologies to provide certain functions, to improve the user experience and to offer interest-oriented content. Depending on their intended use, cookies may be used in addition to technically required cookies, analysis cookies and marketing cookies. You can decide which cookies to use by selecting the appropriate options below. Please note that your selection may affect the functionality of the service. Further information can be found in our privacy policy .

• Mission and Vision
• Annual Reports
• Complaints Procedures
• Delegates Information
• 2024 Delegates Call
• Executive Board
• Staff/Contact Us
• Requests for Proposals (RFP)
• Job Postings
• Guide to a Successful Chess Club
• The Ratings System
• New to National Events Guide
• Safe Play Policy
• How to Send an Email Blast
• Guide to Scholastic Chess
• Accessibility Guidelines
• Our Initiative
• Top 100 Lists
• Olympiad Campaign
• At-Risk Youth
• Correspondence Chess
• 2023-24 Scholastic Regulations
• Scholastic Council Members
• Chess Life Kids Online
• Faces of US Chess
• Our Heritage: Yearbook
• Upcoming Events
• Grants/Awards
• Spectator Policy at Scholastics
• Current Scholastic Regulations
• Event Bidding
• Official Rules
• Plan Ahead Calendar
• Grand Prix Information
• Pan American Youth Championships
• Pan Am Youth Champ
• Irwin: Seniors (50+)
• Denker: HS (9-12)
• Haring: Girls (K-12)
• Barber: MS (6-8)
• Rockefeller: ES (K-5)
• Weeramantry: Blitz
• Opening and Closing Ceremony Program
• Player/Ratings Look-Up
• Past Event Crosstables
• Events Rated List
• TD/Affiliate Support
• Club/Affiliate Search
• Rating System Algorithm
• MSA/Ratings FAQ
• Become a Member
• Become an Affiliate
• Redeem a Voucher
• Benefactor Members
• Membership Form PDF
• Info for Members/Affiliates
• Donor Bill of Rights
• Giving Tuesday
• Donate Online
• Case for Support
• At-Risk-Youth

Chess and Math: A Closer Look at the Knight's Tour

• September 2024 (17)
• August 2024 (27)
• July 2024 (44)
• June 2024 (27)
• May 2024 (32)
• April 2024 (51)
• March 2024 (34)
• February 2024 (25)
• January 2024 (26)
• December 2023 (29)
• November 2023 (26)
• October 2023 (37)
• September 2023 (27)
• August 2023 (37)
• July 2023 (47)
• June 2023 (33)
• May 2023 (37)
• April 2023 (45)
• March 2023 (37)
• February 2023 (28)
• January 2023 (31)
• December 2022 (23)
• November 2022 (32)
• October 2022 (31)
• September 2022 (19)
• August 2022 (39)
• July 2022 (32)
• June 2022 (35)
• May 2022 (21)
• April 2022 (31)
• March 2022 (33)
• February 2022 (21)
• January 2022 (27)
• December 2021 (36)
• November 2021 (34)
• October 2021 (25)
• September 2021 (25)
• August 2021 (41)
• July 2021 (36)
• June 2021 (29)
• May 2021 (29)
• April 2021 (31)
• March 2021 (33)
• February 2021 (28)
• January 2021 (29)
• December 2020 (38)
• November 2020 (40)
• October 2020 (41)
• September 2020 (35)
• August 2020 (38)
• July 2020 (36)
• June 2020 (46)
• May 2020 (42)
• April 2020 (37)
• March 2020 (60)
• February 2020 (39)
• January 2020 (45)
• December 2019 (35)
• November 2019 (35)
• October 2019 (42)
• September 2019 (45)
• August 2019 (56)
• July 2019 (44)
• June 2019 (35)
• May 2019 (40)
• April 2019 (48)
• March 2019 (61)
• February 2019 (39)
• January 2019 (30)
• December 2018 (29)
• November 2018 (51)
• October 2018 (45)
• September 2018 (29)
• August 2018 (49)
• July 2018 (35)
• June 2018 (31)
• May 2018 (39)
• April 2018 (31)
• March 2018 (26)
• February 2018 (33)
• January 2018 (30)
• December 2017 (26)
• November 2017 (24)
• October 2017 (30)
• September 2017 (30)
• August 2017 (32)
• July 2017 (27)
• June 2017 (32)
• May 2017 (26)
• April 2017 (37)
• March 2017 (28)
• February 2017 (30)
• January 2017 (27)
• December 2016 (29)
• November 2016 (24)
• October 2016 (32)
• September 2016 (31)
• August 2016 (27)
• July 2016 (24)
• June 2016 (26)
• May 2016 (19)
• April 2016 (30)
• March 2016 (37)
• February 2016 (27)
• January 2016 (33)
• December 2015 (25)
• November 2015 (23)
• October 2015 (16)
• September 2015 (28)
• August 2015 (28)
• July 2015 (6)
• June 2015 (1)
• May 2015 (2)
• April 2015 (1)
• February 2015 (3)
• January 2015 (1)
• December 2014 (1)
• July 2010 (1)
• October 1991 (1)
• August 1989 (1)
• January 1988 (1)
• December 1983 (1)

Announcements

• Information Regarding Required Annual SafeSport Refresher Course »
• US Chess Seeking HOD and Trainers for 2024 International Youth Events »
• National Chess Week To Be Held October 5-12: What To Know »
• US Chess Offices Closed Monday, September 2, For Labor Day »

US CHESS PRESS

The Knight’s Tour

The  knight’s tour problem  is the mathematical problem of finding a knight’s tour, and probably making knight the most interesting piece on the chess board. The knight visits every square exactly 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.

The knight’s tour problem is an instance of the more general Hamiltonian path problem in graph theory. The problem of finding a closed knight’s tour is similarly an instance of the Hamiltonian cycle problem. Unlike the general Hamiltonian path problem, the knight’s tour problem can be solved in linear time.

Hamiltonian Path Problem

In Graph Theory, a graph is usually defined to be a collection of nodes or vertices and the set of edges which define which nodes are connected with each other. So we use a well known notation of representing a graph G = (V,E) where  V = { v 1 , v 2 , v 3 , … , v n }  and E = {(i, j)|i ∈ V and j ∈ V and i and j is connected}.

Hamiltonian Path is defined to be a single path that visits every node in the given graph, or a permutation of nodes in such a way that for every adjacent node in the permutation there is an edge defined in the graph. Notice that it does not make much sense in repeating the same paths. In order to avoid this repetition, we permute with |V| C 2 combinations of starting and ending vertices.

Simple way of solving the Hamiltonian Path problem would be to permutate all possible paths and see if edges exist on all the adjacent nodes in the permutation. If the graph is a complete graph, then naturally all generated permutations would quality as a Hamiltonian path.

For example. let us find a Hamiltonian path in graph G = (V,E) where V = {1,2,3,4} and E = {(1,2),(2,3),(3,4)}. Just by inspection, we can easily see that the Hamiltonian path exists in permutation 1234. The given algorithm will first generate the following permutations based on the combinations: 1342 1432 1243 1423 1234 1324 2143 2413 2134 2314 3124 3214

The number that has to be generated is ( |V| C 2 ) (|V| – 2)!

Schwenk proved that for any  m  ×  n  board with  m  ≤  n , a closed knight’s tour is always possible  unless  one or more of these three conditions are met:

• m  and  n  are both odd
• m  = 1, 2, or 4
• m  = 3 and  n  = 4, 6, or 8.

Cull and Conrad proved that on any rectangular board whose smaller dimension is at least 5, there is a (possibly open) knight’s tour.

Neural network solutions

The neural network is designed such that each legal knight’s move on the chessboard is represented by a neuron. Therefore, the network basically takes the shape of the  knight’s graph  over an n×n chess board. (A knight’s graph is simply the set of all knight moves on the board)

Each neuron can be either “active” or “inactive” (output of 1 or 0). If a neuron is active, it is considered part of the solution to the knight’s tour. Once the network is started, each active neuron is configured so that it reaches a “stable” state if and only if it has exactly two neighboring neurons that are also active (otherwise, the state of the neuron changes). When the entire network is stable, a solution is obtained. The complete transition rules are as follows:

where t represents time (incrementing in discrete intervals), U(N i,j ) is the state of the neuron connecting square i to square j, V(N i,j ) is the output of the neuron from i to j, and G(N i,j ) is the set of “neighbors” of the neuron (all neurons that share a vertex with N i,j ).

Code For Knight’s Tour

You May Also Like

QUANTUM YANG–MILLS THEORY

Fascinating quaternions.

Gödel’s Incompleteness Theorems

Leave a reply cancel reply.

• Contract bridge
• Connection games
• Cards classifier
• List of dice games
• Rummy games
• Chess World Cup
• FIDE Grand Prix
• World Championship
• List of strong tournaments
• List of world championships
• Checkmate patterns
• Chess openings
• Chess strategy
• Chess tactics
• Chess theory
• Pawn structure
• Problems/Compositions
• Computer chess
• Chess engines
• Chess software
• Cheating in chess
• Chess prodigy
• List of Grandmasters
• Grandmasters by country
• Top player comparison
• World rankings
• Chess titles
• Rating systems
• Correspondence chess
• List of chess variants
• Rules of chess
• Chess notation
• Outline of chess
• Timeline of chess

Knight's tour

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 .

The knight's tour problem is the mathematical problem of finding a knight's tour. Creating a program to find a knight's tour is a common problem given to computer science students. Variations of the knight's tour problem involve chessboards of different sizes than the usual 8 x 8, as well as irregular (non-rectangular) boards.

The knight's tour problem is an instance of the more general Hamiltonian path problem in graph theory. The problem of finding a closed knight's tour is similarly an instance of the Hamiltonian cycle problem. Unlike the general Hamiltonian path problem, the knight's tour problem can be solved in linear time.

The earliest known reference to the knight's tour problem dates back to the 9th century AD. In Rudraṭa's Kavyalankara (5.15), a Sanskrit work on Poetics, the pattern of a knight's tour on a half-board has been presented as an elaborate poetic figure ("citra-alaṅkāra") called the "turagapadabandha" or 'arrangement in the steps of a horse.' The same verse in four lines of eight syllables each can be read from left to right or by following the path of the knight on tour. Since the Indic writing systems used for Sanskrit are syllabic, each syllable can be thought of as representing a square on a chess board. Rudrata's example is as follows:

से ना ली ली ली ना ना ना ली

ली ना ना ना ना ली ली ली ली

न ली ना ली ली ले ना ली ना

ली ली ली ना ना ना ना ना ली

se nā lī lī lī nā nā lī

lī nā nā nā nā lī lī lī

na lī nā lī le nā lī nā

lī lī lī nā nā nā nā lī

For example, the first line can be read from left to right or by moving from the first square to second line, third syllable (2.3) and then to 1.5 to 2.7 to 4.8 to 3.6 to 4.4 to 3.2.

One of the first mathematicians to investigate the knight's tour was Leonhard Euler. The first procedure for completing the Knight's Tour was Warnsdorf's rule, first described in 1823 by H. C. von Warnsdorf.

In the 20th century, the Oulipo group of writers used it among many others. The most notable example is the 10 x 10 Knight's Tour which sets the order of the chapters in Georges Perec's novel Life: A User's Manual . The sixth game of the 2010 World Chess Championship between Viswanathan Anand and Veselin Topalov saw Anand making 13 consecutive knight moves (albeit using both knights); online commentors jested that Anand was trying to solve the Knight's Tour problem during the game.

Schwenk proved that for any m x n board with m ≤ n , a closed knight's tour is always possible unless one or more of these three conditions are met:

• m and n are both odd
• m = 1, 2, or 4
• m = 3 and n = 4, 6, or 8.

Cull et al. and Conrad et al. proved that on any rectangular board whose smaller dimension is at least 5, there is a (possibly open) knight's tour.

Number of tours

On an 8 x 8 board, there are exactly 26,534,728,821,064 directed closed tours (i.e. two tours along the same path that travel in opposite directions are counted separately, as are rotations and reflections). The number of undirected closed tours is half this number, since every tour can be traced in reverse. There are 9,862 undirected closed tours on a 6 x 6 board.

Finding tours with computers

There are quite a number of ways to find a knight's tour on a given board with a computer. Some of these methods are algorithms while others are heuristics.

Brute force algorithms

A brute-force search for a knight's tour is impractical on all but the smallest boards; for example, on an 8x8 board there are approximately 4x10 51 possible move sequences, and it is well beyond the capacity of modern computers (or networks of computers) to perform operations on such a large set. However the size of this number gives a misleading impression of the difficulty of the problem, which can be solved "by using human insight and ingenuity ... without much difficulty."

Divide and conquer algorithms

By dividing the board into smaller pieces, constructing tours on each piece, and patching the pieces together, one can construct tours on most rectangular boards in polynomial time.

Neural network solutions

The Knight's Tour problem also lends itself to being solved by a neural network implementation. The network is set up such that every legal knight's move is represented by a neuron, and each neuron is initialized randomly to be either "active" or "inactive" (output of 1 or 0), with 1 implying that the neuron is part of the final solution. Each neuron also has a state function (described below) which is initialized to 0.

When the network is allowed to run, each neuron can change its state and output based on the states and outputs of its neighbors (those exactly one knight's move away) according to the following transition rules:

Warnsdorff's rule

Warnsdorff's rule is a heuristic for finding a knight's tour. We move the knight so that we always proceed to the square from which the knight will have the fewest onward moves. When calculating the number of onward moves for each candidate square, we do not count moves that revisit any square already visited. It is, of course, possible to have two or more choices for which the number of onward moves is equal; there are various methods for breaking such ties, including one devised by Pohl and another by Squirrel and Cull.

This rule may also more generally be applied to any graph. In graph-theoretic terms, each move is made to the adjacent vertex with the least degree. Although the Hamiltonian path problem is NP-hard in general, on many graphs that occur in practice this heuristic is able to successfully locate a solution in linear time. The knight's tour is a special case.

The heuristic was first described in "Des Rösselsprungs einfachste und allgemeinste Lösung" by H. C. von Warnsdorff in 1823. A computer program that finds a Knight's Tour for any starting position using Warnsdorff's rule can be found in the book 'Century/Acorn User Book of Computer Puzzles' edited by Simon Dally (ISBN 071260541X).

• Abu-Bakr Muhammad ben Yahya as-Suli
• George Koltanowski
• Longest uncrossed knight's path
• Eight queens puzzle

Plus.Maths.org

The knight's tour

This article is part of Five of Euler's best . Click here to read the other four problems featured in this series, which is based on a talk given by the mathematician Günter M. Ziegler at the European Congress of Mathematics 2016.

The second question in this series is also about finding a path, but this time on a chess board. To phrase it in Euler's own words,

"I found myself one day in a company where, on the occasion of a game of chess, someone proposed this question: To move with a knight through all the squares of a chess board, without ever moving two times to the same square, and beginning with a given square."

A knight's tour as it appears in Euler's paper. Euler just numbered the squares in the order in which they're traversed, but we have traced the tour in blue. From paper E309 on the Euler archive .

Euler called this a "curious problem that does not submit to any kind of analysis". But analyse it he did, and he was the first person to do so methodically. He came up with a method for constructing knight's tours which, as he claimed, allows you to discover as many tours as you like. Because "although their number isn't infinite, it is so great that we will never exhaust it."

These statements are contradictory by modern mathematical standards. If you can discover as many tours as you like, then surely their number is infinite. But we know what Euler means: the number of tours is so huge, it might as well be infinite. To really try and count them you need to use a computer. In 1996 the mathematicians Martin Löbbing and Ingo Wegener did just this. They counted only those tours for which the end square is just one knight's hop away from the starting square, that is, tours that can be turned into a loop. They claimed that there were 33,439,123,484,294 of them (in fact, their aim wasn't so much to count the number of tours, but to demonstrate the usefulness of a particular enumeration method).

It was soon pointed out to them , however, that the result can't be right: the number of knight's tours must be divisible by 4 which 33,439,123,484,294 isn't. The apparently correct result is 13,267,364,410,532. That's more than the diameter of the solar system measured in kilometres. As for knight's tours that can't be turned into a loop, a number computed by Alexander Chernov in 2014 is 19,591,828,170,979,904. People don't seem to be entirely certain as to whether it's correct though.

If you read French then you can read Euler's original article on the Euler archive (article E309) . For an easier ride, read about Euler's methods for constructing knight's tours in this MAA online article . There's more about variations of the classical knight's tour problem on the MacTutor History of Mathematics archive .

About this article

Günter M. Ziegler is professor of Mathematics at Freie Universität Berlin, where he also directs the Mathematics Media Office of the German Mathematical Society DMV . His books include Proofs from THE BOOK (with Martin Aigner) and Do I count? Stories from Mathematics. .

Marianne Freiberger is Editor of Plus . She really enjoyed Ziegler's talk about Euler at the European Congress of Mathematics in Berlin in July 2016, on which this article is based.

• Add new comment

IB Maths Resources from Intermathematics

IB Maths Resources: 300 IB Maths Exploration ideas, video tutorials and Exploration Guides

Knight’s Tour

The Knight’s Tour is a mathematical puzzle that has endured over 1000 years.  The question is simple enough – a knight (which can move as illustrated above) wants to visit all the squares on a chess board only once.  What paths can it take?  You can vary the problem by requiring that the knight starts and finishes on the same square (a closed tour) and change the dimensions of the board.

The first recorded solution (as explained in this excellent pdf exploration of the Knight’s Tour by Ben Hill and Kevin Tostado) is shown below:

The numbers refer to the sequence of moves that the knight takes.  So, in this case the knight will start in the top right hand corner (01), before hopping to number 02.  Following the numbers around produces the pattern on the right.  This particular knight’s tour is closed as it starts and finishes at the same square and incredibly can be dated back to the chess enthusiast al-Adli ar-Rumi circa 840 AD.

Despite this puzzle being well over 1000 years old, and despite modern computational power it is still unknown as to how many distinct knight’s tours there are for an 8×8 chess board.  The number of distinct paths are as follows:

1×1 grid: 1, 2×2 grid: 0, 3×3 grid: 0, 4×4 grid: 0, 5×5 grid: 1728, 6×6 grid: 6,637,920, 7×7 grid: 165,575,218,320 8×8 grid: unknown

We can see just how rapidly this sequence grows by going from 6×6 to 7×7 – so the answer for the 8×8 grid must be huge.  Below is one of the 1728 solutions to the 5×5 knight’s tour:

You might be wondering if this has any applications beyond being a diverting puzzle, well Euler – one of the world’s true great mathematicians – used knight’s tours in his study of graph theory.  Graph theory is an entire branch of mathematics which models connections between objects.

Knight’s tours have also been used for cryptography:

This code is from the 1870s and exploits the huge number of possible knight’s tours for an 8×8 chess board.  You would require that the recipient of your code knew the tour solution (bottom left) in advance.  With this solution key you can read the words in order – first by finding where 1 is in the puzzle (row 6 column 3) – and seeing that this equates to the word “the”.  Next we see that 2 equates to “man” and so on.  Without the solution key you would be faced with an unimaginably large number of possible combinations – making cracking the code virtually impossible.

If you are interested in looking at some more of the maths behind the knight’s tour problem then the paper by Ben Hill and Kevin Tostado referenced above go into some more details.  In particular we have the following rules:

An m x n chessboard with m less than or equal to n has a knight’s tour unless one or more of these three conditions hold:

1) m and n are both odd 2) m = 1, 2 or 4 3) m = 3 and n = 4,6,8

Investigate why this is!

If you enjoyed this post you might also like:

e’s are good – He’s Leonard Euler. A discussion about the amazing number e and Euler’s use of graph theory.

Sierpinski Triangles and Spirolateral Investigation Lesson Plan. A lesson to introduce the mathematics in art and fractals.

Essential resources for IB students:

1) Exploration Guides  and Paper 3 Resources

I’ve put together four comprehensive pdf guides to help students prepare for their exploration coursework and Paper 3 investigations. The exploration guides talk through the marking criteria, common student mistakes, excellent ideas for explorations, technology advice, modeling methods and a variety of statistical techniques with detailed explanations. I’ve also made 17 full investigation questions which are also excellent starting points for explorations.  The Exploration Guides can be downloaded here  and the Paper 3 Questions can be downloaded here .

Share this:

Leave a reply cancel reply.

Powered by WordPress.com .

Discover more from IB Maths Resources from Intermathematics

Subscribe now to keep reading and get access to the full archive.

Type your email…

Continue reading

Knight's Tour

Knight Graph

Knight's Tour Visualization

Tip: An n * n chessboard has a closed knight's tour iff n ≥ 6 is even.

Note: The pieces of chess are placed inside a square, while the pieces of Chinese chess are placed on the intersections of the lines.

Board size: (Board size should be an even number).

Time of a stroke (ms):