knight's tour solution

Knight's Tour Challenge

How to play.

This "game" is basically an implementation of Knight's Tour problem.

You have to produce the longest possible sequence of moves of a chess knight, while visiting squares on the board only once. This sequence is called "tour". If your tour visits every square, then you have achieved a full tour. If you have achieved a full tour and from your last position you could move to your initial square, then you have achieved a closed full tour.

Currently occupied square is highlighted in pale blue, while possible moves are shown with pale green. Click on the currently occupied square to undo.

• [email protected]

What’s New ?

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
• Backtracking Algorithm
• Introduction to Backtracking
• 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

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. Numbers in cells indicate move number of Knight.   

We have discussed Backtracking Algorithm for solution of Knight’s tour . In this post Warnsdorff’s heuristic is discussed.  Warnsdorff’s Rule:  

• We can start from any initial position of the knight on the board.
• We always move to an adjacent, unvisited square with minimal degree (minimum number of unvisited adjacent).

This algorithm may also more generally be applied to any graph. 

Some definitions:   

• A position Q is accessible from a position P if P can move to Q by a single Knight’s move, and Q has not yet been visited.
• The accessibility of a position P is the number of positions accessible from P.

Algorithm:   

• Set P to be a random initial position on the board
• Mark the board at P with the move number “1”
• let S be the set of positions accessible from P.
• Set P to be the position in S with minimum accessibility
• Mark the board at P with the current move number
• Return the marked board — each square will be marked with the move number on which it is visited.

Below is implementation of above algorithm.  

Output:  

Time complexity: O(N^3) Space complexity: O(N^2)

The Hamiltonian path problem is NP-hard in general. In practice, Warnsdorff’s heuristic successfully finds a solution in linear time.

Do you know?   “On an 8 × 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!”

If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to [email protected]. See your article appearing on the GeeksforGeeks main page and help other Geeks.  

Please Login to comment...

Similar reads.

• chessboard-problems
• Backtracking

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
• 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" >

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.

• 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

Search anything:

Knight’s Tour Problem

Algorithms backtracking.

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

The Knight's Tour Problem is one of the famous problem in which we have the knight on a chessboard. The knight is supposed to visit every square exactly once.

Following it we have two cases:

• Closed Tour : The knight ends on a square that is one move away from the beginning square. This means that if it continues to move, with the same path that it has followed till now, it will be able to traverse all squares again.
• Open Tour : The knight ends on any other square. This problem is solved on a n x n chessboard. "n" could have any value. This problem is derived from the Hamiltonian Path Problem in Graph Theory .

Hamiltonian Path Problem is focused on finding out if there is a path or route in undirected graph from the beginning to ending node. However, it can gain a lot of complexity even on little increase in its size. Hamiltonian Path is the one that visits each vertex of the graph only once. A grap h with Hamiltonian Path in it is called traceable graph.

However, there are ways to solve this problem in linear time. Consider the below image, let the diamond represent the "knight" and the tick marks represent its possible moves at given position. A "knight" can move two squares in cardinal direction then one square in orthogonal direction.

There are many variants possible for this problem like having two knights and so on. In this article we will explore the basic problem with one knight and how it can cover all squares without revisiting them.

One way to solve this problem is Naive Approach, to find all possible configurations and choose the correct one. Since, this would take much longer if the value of n in n x n board is large.

Backtracking

Other technique that can be used for this problem is Backtracking . It is optimized version of our naive technique. Backtracking is the technique in which we try all possible solutions or combinations till we find the one that is correct. In this each combination is tried only once.

It incrementally makes the solution using recursion. We consider on step at a time. If they do not satisfy the constraints then we remove those particular steps.

Time Complexity: O(n * n) for traversing the n x n squares. Implementation:

Explanation:

• The function called in main() would be ans().
• It declares a sol array representing the chess board of n x n size.
• Then we initialise it with -1 values. Then we define the next values of x and y coordinates in array x and array y.
• Now, we call function aux and explore all tours and check if the solution exists.
• If it exists then we print the solution. The aux function:
• This is the recursive function to find the final solution.
• In this we try all possible moves from x and y. We also call function range to check if the squares are in n x n configuration.
• We essentially use backtracking to solve this problem.

We can have much better approaches as well to solve this problem:

Warnsdorff’s algorithm:

In this approach we can start from any initial square on the chess board. Then, we will move to an adjacent, unvisited square with minimum unvisited adjacent squares.

• Set a square as the initial position to start from.
• Mark it with current move number starting with "1".
• Make a set of all positions that can be visited from initial position.
• Mark the square out of the set of possible positions that can be visited with minimum accessibility from initial position as next move number.
• Following the above steps, return the marked board with move numbers with which it has been visited.

In the above code, in find function, we initialized an array of size n x n with values -1.

Then, we initialized x1 and y1 with random values.

Then we copied those values in variables x and y. Now, current positions are same as initial positions.

Then, we mark our first move at location y * n + x.

In the next for loop, we pick next points for our Warnsdorff’s algorithm. We call next function:

• We will try all adjacent squares starting from a random adjacent value with minimum degree.
• We initialize start with a random value
• If now next cell is found then we return false.
• Then, we store coordinates in x and y of next point in variables nx and ny.
• Then, we mark our next move on the array at location ny * n + nx and update next points.

Now, we come back into function find and then neighbor function is called.

• We will check the neighboring squares. If the last square is one move away from the initial location of square then its a closed tour else open tour.

The degree function returns the number of empty squares adjacent to x,y

The range function keeps us within the board and isempty function checks if the square is valid and empty or not.

Now, we again come back to out find function and call print function to print all moves of the knight.

This way,we can implement this algorithm and find our best possible solution.

Neural Networks:

We can even use neural networks to solve this problem. It will be much helpful in the cases where n has much larger value. Each and every possible knight's move is represented by a neuron. Each neuron can have two values : "active" or "inactive". If it is "active" then it is part of our solution else not. This way, we can use machine learning to find solutions to much more complex variants of this problem including large values for "n" and multiple knights.

Using all the above approaches we can find out the best possible solution for our Knight's Tour Problem . Happy Coding!

Java Tutorial

Control statements, java object class, java inheritance, java polymorphism, java abstraction, java encapsulation, java oops misc.

Approach: Using Backtracking

In this approach, we start with an empty chessboard and try to place the Knight on each square in turn, backtracking when we reach a point where no further moves are possible. The Backtracking approach is a common algorithmic technique used to solve optimization problems, where we are searching for the best solution among many possible solutions.

• Define a static integer variable N representing the chessboard size (8).
• Define a Method isSafe(x, y, sol) to check if a knight can be placed at position (x, y) on the chessboard. The Method checks if (x, y) is within the board limits and if a knight does not already occupy the position.
• Define a Method print solution (sol) to print the final knight tour solution.
• Define a Method to solve KT () to solve the Knight's tour problem. a. Initialize an empty 2D array (sol) of size NxN, where -1 represents an empty cell. b. Define two arrays (xMove, yMove) to represent all possible knight moves. c. Set the starting position to (0,0) and mark it as visited by setting sol[0][0] to 0. d. Call the recursive Method solveKTUtil() with the starting position, movei=1, and the arrays xMove and yMove. e. If solveKTUtil() returns false, the Knight's tour solution does not exist. If it returns true, print the solution using printSolution() and return true.
• Define a recursive Method solveKTUtil(x, y, movie, sol, xMove, yMove) to solve the Knight's tour problem. a. If movie = N*N, the Knight's tour solution has been found, return true. b. Loop through all possible knight moves (k) using xMove and yMove arrays. c. Calculate the next position (next_x, next_y) using the current position (x, y) and the current knight move (k). d. If the next position is safe (i.e., isSafe(next_x, next_y, sol) returns true), mark it as visited by setting sol[next_x][next_y] = movei, and recursively call solveKTUtil() with the next position (next_x, next_y) and movei+1. e. If solveKTUtil() returns true, the Knight's tour solution has been found, return true. If it returns false, mark the next position as unvisited by setting sol[next_x][next_y] = -1 and continue to the next possible knight move. f. If no move leads to a solution, return false.
• The main method, called solveKT(), is to solve the Knight's tour problem. If a solution exists, it will be printed to the console.

Implementation

Filename: KnightTour.java

Complexity Analysis: The time complexity of the Knight's tour problem using backtracking is O(8^(N^2)), where N is the size of the chessboard. It is because at each move, the Knight has 8 possible moves to choose from, and the total number of moves the Knight can make is N^2.

The space complexity of the program is O(N^2).

• Send your Feedback to [email protected]

Help Others, Please Share

Learn Latest Tutorials

Transact-SQL

Reinforcement Learning

R Programming

React Native

Python Design Patterns

Python Pillow

Python Turtle

Preparation

Verbal Ability

Interview Questions

Company Questions

Trending Technologies

Artificial Intelligence

Cloud Computing

Data Science

Machine Learning

B.Tech / MCA

Data Structures

Operating System

Computer Network

Compiler Design

Computer Organization

Discrete Mathematics

Ethical Hacking

Computer Graphics

Software Engineering

Web Technology

Cyber Security

C Programming

Control System

Data Mining

Data Warehouse

Knight's Tour

Knight Graph

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

“The human element, the human flaw and the human nobility – those are the reasons that chess matches are won or lost.” – Viktor Korchnoi

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.

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

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

Banach–tarski paradox.

Hilbert’s Grand Hotel Paradox

The soul theorem, leave a reply cancel reply.

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

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

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

A repertoire against the queen's gambit declined with 4.bg5.

This repertoire provides White with ideas against any of the Black options after the moves 1.d4 d5 2.c4 e6 3.Nc3.

€36.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

Fritz 19 & Opening Encyclopaedia 2024

The best combination for opening training: The big ChessBase opening encyclopaedia with thousands of opening articles plus Fritz19 at a special price!

€199.90

ChessBase Magazine 220

2024 Candidates Tournament with analyses by Gukesh, Pragg, Vidit, Firouzja and Giri. Kasimdzhanov, Engel and Marin show opening trends from Toronto in the video. 10 repertoire articles from English to Queen's Indian and much more!

€21.90

Master Class Vol.17 - Boris Spassky

In this video course, experts including Dorian Rogozenco, Mihail Marin, Karsten Müller and Oliver Reeh, examine the games of Boris Spassky. Let them show you which openings Spassky chose to play, where his strength in middlegames were and much more.

€34.90

Middlegame Secrets Vol.4 - The Secrets Lives of Knights

Knights add irrational content to any position. However, in this video tutorial you will learn how to tame them.

The surprising 3.d3 against the Caro-Kann

We boldly confront the Caro-Kann Defense with the upcoming move 1.e4 c6 2.Nf3 d5 3.d3!? With this highly strategic choice, we disrupt Black’s typical patterns and comfort zones and enter an early endgame full of chances for you.

€32.90

How to play the Open Sicilian

On this all-new ChessBase video course, IM Andrew Martin introduces you to this exciting world, so that you can begin playing the Sicilian in your own games. The main themes and ideas of the Open Sicilian are discussed.

ChessBase Magazine Extra 219

Videos by Felix Blohberger: A new sacrifice idea against the French and “Mikhalchishin’s Miniatures” (Part 3). “Lucky bag” with 44 analyses by Emanuel Berg, Romain Edouard, Alexandr Fier, Michal Krasenkow, Yago Santiago, Vaibhav Suri and many others.

€14.90

Openings #1 The Open Games

In 23 video lessons you will learn everything you need to know about the King's Gambit, the Vienna Game, the Italian, the Evans Gambit, the two-knight game, the Scottish, the Steinitz and Berlin defences, the Open Spanish or the exchange variation, Marsha

€29.90

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 .