ç Knight's Tour Notes Index

Closed Knight's Tours of the 6 by 6 Board

Enumeration, quaternary symmetry, binary symmetry, catalogue of all asymmetric closed knight's tours of the 6×6 board, methods of construction and enumeration, cell coding method, border method, straights and slants method, central angles method, combining the methods.

  • 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

Related Articles

  • Solve Coding Problems
  • Backtracking Algorithms
  • Introduction to Backtracking - Data Structure and Algorithm Tutorials
  • Difference between Backtracking and Branch-N-Bound technique
  • What is the difference between Backtracking and Recursion?

Standard problems on backtracking

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

Easy Problems on Backtracking

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

Medium prblems on Backtracking

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

Hard problems on Backtracking

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

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. 

knight-tour-problem

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

  • chessboard-problems
  • Backtracking
  • Mathematical
  • Mithun Kumar
  • ChetanGoyal1
  • shubhamsingh84100
  • khushboogoyal499
  • yadavgaurav251
  • subhammahato348
  • pujasingg43
  • ChatGPT Gets a Voice: Introducing the New Read Aloud Feature
  • Meta Quest+ is Now Like Game Pass For Your VR Headset
  • MLB World Series Champions - Major League Baseball Winners List
  • IIT Madras E-Cell to Host 100 Innovative Startups at E-Summit 2024 Startup Expo
  • Dev Scripter 2024 - Biggest Technical Writing Event By GeeksforGeeks

Improve your Coding Skills with Practice

 alt=

What kind of Experience do you want to share?

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

All legal moves for a knight on an 8x8 chessboard

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.

Start with vertex A

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:

A closed tour

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.

A search tree for the knight’s tour

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.

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 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:

130x130 open tour

  • 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

knight's tour 6x6 solution

A Python solution for a classic chess puzzle

Knight's tour.

© Lead Image © Dima Sobko, 123RF.com

© Lead Image © Dima Sobko, 123RF.com

If you're looking for a head start on solving the classic Knight's Tour chess challenge, try this homegrown Python script.

A chess knight can travel around a chessboard using the knight's move and visit every square once, and only once. This is known as the Knight's Tour. The Knight's Tour is usually played with numbered counters on a conventional chessboard ( Figure 1 ), but you can play it on any rectangular board with five or more rows and columns.

knight's tour 6x6 solution

The Knight's Tour is an example of a classic mathematical problem that lends itself to easy and creative expression through computer programming. I created a Python program to help users practice solving the Knight's Tour. The Knight's Tour program is a good example of the simple yet powerful applications you can build with the Pygame Python library for computer gamers.

Solving the Knight's Tour

At first, solving the Knight's Tour seems to be a daunting challenge, but quite a few strategies exist that will help you solve the puzzle [1] . I'll consider just two of them. The first strategy is usually known as the Diamonds and Squares method, and it's a simple party trick that anyone can learn in minutes.

Solving the Knight's Tour using the Diamonds and Squares technique doesn't require any mathematical talent or much logical skill; it merely requires the player to recognize two simple geometric shapes in the patterns of knight's moves. This approach can produce a relatively small number of apparently unique tours from every starting square, but the symmetry of the chessboard means that many of these solutions are transformations of other tours by rotation, reflection, or inversion, and this simple technique can only produce 46 truly unique Knight's Tours on a chessboard. Most of the Knight's Tour solution videos you watch on YouTube and elsewhere demonstrate the Diamonds and Squares method.

The second approach is known as Warnsdorff's rule. This strategy takes a bit more effort to master. On an 8x8 chessboard, it can produce thousands of different Knight's Tours from any starting square, but, again, the symmetry of the chessboard means that not all of these solutions are truly unique and many of them are transformations of other Warnsdorff's rule tours. As you'll see in a moment, Warnsdorff's rule can sometimes lead to an impasse, but it still produces far more solutions than the Diamonds and Squares method.

If you want to impress your friends by showing them how to solve the Knight's Tour, then using Warnsdorff's rule will not expose you as a chess puzzle pretender, but using the simple Diamonds and Squares technique might put your reputation as a chess puzzle genius in jeopardy.

Diamonds and Squares

The Diamonds and Squares technique was first described by C. R. R. von Schinnern in 1826 [1] . It only works on boards that have at least 8x8 squares. Larger boards must have a number of rows and columns that are a multiple of four (i.e., 12x12, 8x16, and so on). Unlike Warnsdorff's rule, the Diamonds and Squares technique cannot be used to solve the Knight's Tour on a 6x6 or a 10x10 board.

To employ the Diamonds and Squares strategy on a conventional 8x8 chessboard, you need to divide the chessboard into four quadrants and understand how four knights can be placed on a quadrant in four distinct patterns. The first of these patterns is described as a right-hand (RH) diamond ( Figure 2a ). The second is a left-hand (LH) diamond ( Figure 2b ), the third is a RH square ( Figure 2c ), and the last one is a LH square ( Figure 2d ). When these four shapes are joined together on one quadrant of the chessboard, all 16 squares in that quadrant will have a knight on them.

knight's tour 6x6 solution

In order to use the diamond and square shapes to solve the Knight's Tour, you need to know whether the first knight placed on the board is on a diamond (either RH or LH) or on a square (either RH or LH). For example, a knight at b3 is on a RH diamond ( Figure 3a ), one at c4 is on a RH square ( Figure 3b ), a knight at d1 is on a LH diamond ( Figure 3c ), and one at d3 is on a LH square ( Figure 3d ).

knight's tour 6x6 solution

If you place the first knight on, for example, b3, then you can complete a four-knight partial tour in the lower left-hand quadrant with four knights on a RH diamond shape ( Figure 3a ). You then move onto an adjacent quadrant and use a RH diamond shape to complete another four-knight partial tour on that quadrant. Then you can move on to a third quadrant and then the fourth so that all four quadrants have a four-knight, RH diamond-shaped partial tour on them, and there are 16 knights on the board ( Figure 3a ). After completing the RH diamond-shaped partial tour, you move on to a square-shaped partial tour, in this example, a RH square-shaped partial tour starting at c4 and ending at d6 ( Figure 3b ). Then you can complete a LH diamond-shaped partial tour starting at e8 and ending at b6 ( Figure 3c ) and finally a LH square-shaped partial tour starting at d7 and ending at g5 to complete the Knight's Tour ( Figure 3d ).

The Knight's Tour can always be solved by combining two, 16-knight, diamond-shaped, LH and RH partial tours and two, 16-knight, square-shaped, LH and RH partial tours in the order diamond-square-diamond-square or square-diamond-square-diamond. You will need to make sure that the fourth knight placed in each quadrant leads to an empty square on an adjacent quadrant. With a bit of practice, it's quite easy to solve the Knight's Tour from any starting square using this method.

You can find variations of the Diamonds and Squares technique that will allow you to choose the starting and ending square, but be warned, nearly everyone who knows about the Knight's Tour knows about the Diamonds and Squares method, and you can only impress naive chess puzzlers by demonstrating this technique.

Warnsdorff's Rule

The second strategy is known as Warnsdorff's rule [1, 2] and it is named after H. C. von Warnsdorff, who first described it in 1823. Warnsdorff's rule is a heuristic or rule-of-thumb method for finding a Knight's Tour from any starting square on any sized board with at least 5x5 squares. I'll look at it on a conventional chessboard.

Warnsdorff's rule is summarized as follows:

1. With each move, you have to look ahead to see which of the possible next moves has the least number of exits that can be taken using the knight's move ( Figure 4 ). An exit is a legal move to a square that the knight hasn't inhabited yet.

knight's tour 6x6 solution

2. The square with the least number of valid exits is chosen for the next move.

3. If there is a tie between two or more squares, the next square is chosen at random from all the squares with the least number of exits.

Unfortunately, if a Monte Carlo test [3] is done when Warnsdorff's rule is applied to a conventional chessboard, about three percent of the attempts to find a complete tour will lead to an impasse. If you want to find a Knight's Tour every time using Warnsdorff's rule, you need to modify the original rule to overcome any impasse that might occur. Do this by replacing the random choice of a tiebreaker with a systematic choice.

The easiest variant of Warnsdorff's rule to implement in a computer program requires very little coding. It modifies the third element of Warnsdorff's rule so that, if there is a tie for the next move between two or more squares, the next square is chosen systematically – any systematic way of choosing the tiebreaker will do as long as it prioritizes the way in which the tied moves are selected to break the tie. If breaking a tie systematically leads to an impasse, the calculation can just start again using a different way of making a systematic choice. This is quite a good option for a computer program, because a computer can find a complete tour using an alternative way of choosing a tiebreaker in milliseconds. The program overcomes any impasse that might occur using this simple plan – if the way you're choosing a tiebreaker doesn't work, then stop using it, start again, and choose your tiebreaker in a different way.

Another variant of Warnsdorff's rule is better if you're trying to find a way out of an impasse by hand, because it usually involves less work than starting again. If systematic tie breaking leads to an impasse, you can backtrack to the last tiebreaker and take the second-priority move. If that doesn't work, you can backtrack again and choose the third-priority move, and so on until all the tiebreakers have been tried. If that doesn't overcome the impasse, backtrack to the last-but-one tiebreaker, select the second priority tiebreaker, and keep doing this until the impasse is overcome. The computer program will enable you to backtrack in this way if you're using Warnsdorff's rule (or any other strategy) to solve the puzzle by hand and you get stuck in an impasse. The program doesn't use backtracking when it's finding a solution for you, but if you'd like to see how a program can use backtracking to find a way out of an impasse, there's a backtracking algorithm used in a Knight's Tour program I wrote when I first became interested in chess puzzles many years ago. This program was published in The Century/Acorn User Book of Computer Puzzles [4] .

Any systematic way of choosing can be used as a tiebreaker for either of the alternative versions of Warnsdorff's rule described above, but remember, it must be a systematic choice rather than a random one. There are eight factorial ( 8! = 40320 ) ways in which you can make a systematic choice, but two of the easiest ones to remember when finding a Knight's Tour by hand are to select the tiebreaker in either a clockwise or counterclockwise direction starting at the 12 o'clock position (i.e., start looking from the top of the board and work your way around the tied moves to the right or to the left).

A very handy shortcut version of Warnsdorff's rule can be used to place the first 30 or so knights on the board. This technique works because, in the first half of solving the puzzle, selecting the square with the least number of exits is usually the same as moving the knight as far away from the center of the board as possible – but beware, this shortcut will occasionally disappoint you.

The shortcut requires you to stay as close to the edge of the board as possible and to prioritize the corner squares and their adjacent perimeter squares. This will usually result in two circuits of the board's perimeter during the first half of the tour, after which it's better to stop using the shortcut and start calculating the best way around the empty squares on the board using systematic tie breaking. An insight into what's needed to solve the puzzle is also very useful during the second half of the tour, and you will develop the necessary insight with practice. The fewer knights that are placed on the board using this shortcut, the better it works. The shortcut becomes less reliable as more knights are placed on the board, and the chance that it will let you down increases noticeably when there are more than half of the knights on the board. The Knight's Tour shown in Figure 5 was found using this shortcut combined with backtracking and insight. With practice, it takes only a couple of minutes to find a complete Warnsdorff's tour by hand.

knight's tour 6x6 solution

1 2 Next »

Buy this article as PDF

Buy linux magazine.

knight's tour 6x6 solution

US / Canada

UK / Australia

Related content

In the absence of an IBM supercomputer at his data center in Germany's Lower Rhine region, Charly has to make do with a Linux desktop, Stockfish, and chs in order to follow in the footsteps of chess grandmaster Garry Kasparov.

Some regard Sudoku as the 21st

century Rubik’s Cube. We’ll

show you how to get started

with Sudoku in Linux.

Shredder 9 promises world championship chess on your home computer. We took a look at the new Linux version of the famous Shredder chess tool.

In part 3 of our gamers recommandations we present more strategy games, puzzles, card games, language skill training and more. To be continued.

Seven-city tour presents strategies and best practices for building open clouds.

Subscribe to our Linux Newsletters Find Linux and Open Source Jobs Subscribe to our ADMIN Newsletters

Support our work.

Linux Magazine content is made possible with support from readers like you. Please consider contributing when you’ve found an article to be beneficial.

Learn More

ZorinOS 17.1 Released, Includes Improved Windows App Support

If you need or desire to run Windows applications on Linux, there's one distribution intent on making that easier for you and its new release further improves that feature.

Linux Market Share Surpasses 4% for the First Time

Look out Windows and macOS, Linux is on the rise and has even topped ChromeOS to become the fourth most widely used OS around the globe.

KDE’s Plasma 6 Officially Available

KDE’s Plasma 6.0 "Megarelease" has happened, and it's brimming with new features, polish, and performance.

Latest Version of Tails Unleashed

Tails 6.0 is based on Debian 12 and includes GNOME 43.

KDE Announces New Slimbook V with Plenty of Power and KDE’s Plasma 6

If you're a fan of KDE Plasma, you'll be thrilled to hear they've announced a new Slimbook with an AMD CPU and the latest version of KDE Plasma desktop.

Monthly Sponsorship Includes Early Access to elementary OS 8

If you want to get a glimpse of what's in the pipeline for elementary OS 8, just set up a monthly sponsorship to help fund its continued existence.

DebConf24 to be Held in South Korea

Busan will be the location of the latest DebConf running July 28 through August 4

Fedora Unleashes Atomic Desktops

Fedora has combined its solid distribution with rpm-ostree system to make it possible to deliver a new family of Fedora spins, called Fedora Atomic Desktops.

Bootloader Vulnerability Affects Nearly All Linux Distributions

The developers of shim have released a version to fix numerous security flaws, including one that could enable remote control execution of malicious code under certain circumstances.

Microsoft Says VS Code Will Work with Ubuntu 18.04

If you're a user of Microsoft's VS Code and you're still using Ubuntu 18.04, you can breathe a sigh of release that the IDE will continue working… for a while.

knight's tour 6x6 solution

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

8.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.

../_images/8arrayTree.png

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

../_images/moveCount.png

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.

Verification of the research described in arXiv:2001.06044 [cs.DM] .

Minimum Requirements

Visual Studio 2019 under Windows or g++ under UNIX.

Description

Three types of task can be specified at run-time.

  • Generation of tourneys, which are saved in SVG and text format.
  • Timing (elapsed and CPU time) on multiple samples for a range of board sizes.
  • Measurement of single-move and double-move frequencies on multiple samples for a single board size.

The code is multi-threaded and is currently set to use one less than the maximum number of concurrent threads on the hardware on which it is executed (to ensure that there is a thread left for the user on long runs). It is written in C++ using the C++ standard library. There are about 5,300 lines of source code, 3,400 lines not counting comment blocks, and 2,200 lines not counting comment blocks and blank lines.

Recommended Background

It is assumed that the reader of this code knows how a knight moves in the game of chess and is familiar with the concepts typically taught in an undergraduate class on algorithms and data structures such as queues, graphs and spanning trees. It is also highly recommended that you read the paper mentioned above before attempting to use this code.

Compiling the Code

Windows and visual studio.

A Visual Studio solution file Generate.sln has been provided in the root folder. It has been tested with Visual Studio 2019 Community under Windows 10.

UNIX and g++

A make file has been placed in the Code directory. Type "make generator" to create the executable file Generate.exe . It has been tested with g++ 7.4 on the Ubuntu 18.04.1 subsystem under Windows 10.

Running the Code

You will be prompted for various parameters. At the first prompt you may enter 'q' to quit. At subsequent text prompts you may type 'h' for help on the possible responses or 'r' to restart. The first prompt requires you to enter your task type, 'g' for generate , 't' for time , or 'm' for measure . You will then proceed as follows.

A knight's tour or tourney will be saved in SVG format (a vector graphics image file that can be viewed in a browser) and as a text file listing the knight's move 0-7 from each cell of a square chessboard. You will be prompted for the generation algorithm, the tourney type, whether or not the board is to be blurred, and the board size. The name of the file will consist of substrings specifying the generation method, tourney type, and board size.

run.png

The time required to generate a number of knight's tours or tourneys of a range of sizes will be saved in a text file. You will be prompted for the generation algorithm, the tourney type, whether or not the board is to be blurred, the number of samples (number of boards generated of each size) and a lower and upper size range. The name of the text file will have the prefix Time followed by substrings specifying the generation method, tourney type, and number of samples. The output will consist of three tab-separated columns for board size, CPU seconds, and elapsed seconds.

output-time.png

Statistics on the frequency of single and double moves for a number of knight's tours or tourneys will be measured and saved in a text file. You will be prompted for the number of samples (number of boards generated of each size) and the board size. The name of the text file will have the prefix Stats followed by substrings specifying the generation method, tourney type, board size, and number of samples. The output will consist of tab-separated columns as follows. The first column contains row headers. The remaining eight columns will list the observed mean and standard deviation for the frequency of moves 0-7 over all samples.

output-stats.png

Code Organization

The source code can be divided into five categories: General, Services, Multithreading, Generators, and the implementation of the Shatter, Join, and Blur algorithms from the paper. Each of these categories is described in a separate section below. If your time is limited, I recommend you start by skimming CBaseBoard , then proceeding directly to CRail and CBoard . If you are interested in generators for knight's tours and tourneys, then proceed to the Generators section below. The rest of the code is fairly straightforward and may be omitted unless you enjoy reading that sort of thing.

General support code.

Some standard services including pseudorandomness and time measurement.

Multithreading

Support for multi-threading of time-consuming things like randomized tourney generators and the gathering of run-time and move frequency statistics.

Knight's Tours

Implementation of the main contributions of the paper.

Some standard knight's tour generators and the obvious tourney generators derived from them. Using Warnsdorff's algorithm for tourneys requires a little thought. Braided concentric tourneys and Four-cover tourneys are new but quite simple to understand.

doxygen

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.

knight's tour 6x6 solution

Using the Knight's Tour to impress

knight's tour 6x6 solution

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.

knight's tour 6x6 solution

ONLINE SHOP

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

knight's tour 6x6 solution

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

knight's tour 6x6 solution

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!

knight's tour 6x6 solution

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.

knight's tour 6x6 solution

User   Password  

Not registered yet? Register

knight's tour 6x6 solution

Attacker, coward, swindler or endgame wizard

€89.90

Najdorf: A dynamic grandmaster repertoire against 1.e4 Vol.1 to 3

knight's tour 6x6 solution

€99.90

Uncovering the Anti-Sicilians! A dynamic grandmaster repertoire against 1.e4 Vol.3

knight's tour 6x6 solution

This Fritztrainer offers you the perfect addition to any Sicilian or Najdorf repertoire, and covers all the minor variations that White has tried to avoid the open Sicilian.

€39.90

The evergreen Philidor

knight's tour 6x6 solution

This video course deals with the different move-orders leading to the main positions of the Philidor defence, as well as White’s relevant deviations.

Philidor Defence Powerbook 2024

knight's tour 6x6 solution

The Powerbook Philidor Defence 2024 is based on 33,000 computer games from the engine room of Schach.de as well as 21,000 games from Mega and correspondence chess.

Philidor Defence Powerbase 2024

knight's tour 6x6 solution

Philidor Defence Powerbase 2024 is a database and contains a total of 4561 games from the Mega 2024 and the Correspondence Database 2024, 269 of which are annotated.

Fritz 19 & Fritz Powerbook 2024

knight's tour 6x6 solution

€179.80 €139.90

ChessBase Magazine 218

knight's tour 6x6 solution

Tata Steel 2024 with analyses by Wei Yi, Firouzja, Giri, Pragg, Vidit and many more. Opening videos by Jan Werle, Daniel King and Mihail Marin. 11 repertoire articles from Alekhine to the King's Indian and much more.

€21.90

Fritztrainer in App Store

knight's tour 6x6 solution

for iPads and iPhones

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 .

On 26 August 1735, Leonard Euler presented a talk to the Imperial Science Academy that was the basis for his paper, "The solution of a problem relating to the geometry of position." In this work Euler addressed an age-old problem that had for years bewildered the populace of the city of K�nigsberg in East Prussia. The city, as it was in Euler’s time was situated around the River Pregel which divided the city into 4 separate areas all linked together by a system of bridges as shown in the picture below. The problem the people used to ponder was whether or not it was possible to walk around the city crossing each of the seven bridges only once. Of course nobody had ever succeeded but it wasn’t until Euler approached the problem from the viewpoint of a mathematician that it was actually proved. It was from this proof that Euler managed to discover some general rules to apply to other problems of this type. Euler began by producing a topological map or graph of the bridges and their landfall such that the four parts of the city are labelled A, B, C and D, and the bridges are labelled a, b, c, d, e, f and g.

Euler Graph1

Each of the parts of the city is called a vertex and is connected by the bridges to be called edges . Euler proved that it was not possible to use all the edges once no matter where one begins because in order to do so one must exit each vertex every time it is entered and therefore each vertex requires an even number of edges. As can be seen this is not the case in K�nigsberg, and in fact all the vertices have odd degree or valency . If we were to add just one extra edge ‘h’ between the two vertices B and D it would then be possible to traverse each edge once and once only but we would find ourselves finishing our walk at a vertex other than the one where we began.

Euler Graph2

We now have vertex C with degree 3 and vertex A with degree 5 but B and D are now both even having degree 4. Because we must always have an entry and an exit edge to find a path through the graph this means that the vertices of odd degree must be the start and finish of the path that exists in this connected graph. If we begin our walk at vertex C and finish at vertex A then our path traverses the edges as follows: - a,g,c,d,b,e,h,f. We have fulfilled the criteria required in that we have travelled each edge once and only once but we have not returned to our starting point. These results give us Euler’s statements from the translation in Graph Theory 1736 - 1936 [2] .

"If there are more than two areas (vertices) to which an odd number of bridges (edges) lead, then such a journey (Eulerian path) is not possible. If, however, the number of bridges (edges) is odd for exactly two areas (vertices), then the journey (Eulerian path) is possible if it starts in either of these areas (vertices). If, finally, there are no areas (vertices) to which an odd number of bridges (edges) lead, then the required journey (Eulerian path) can be accomplished starting from any area (vertex)." (My brackets.)

In this particular paper the definition of an Eulerian path is to be one that covers each edge once and only once but does not necessarily finish on the vertex it began. I’m not sure though how the burghers of K�nigsberg would have felt about not returning home for supper after such a long walk! Euler was a man who loved puzzles and, although I cannot find his original discourse and systematic approach to the Knight’s tour, I am aware through the work of other mathematicians that he did look at the problem. Another mathematician of the time, A. -T. Vandermonde took up the challenge.

Graph Theory (Section II) Back to top

Alexandre - Theophile Vandermonde was a French mathematician who became interested in the problem of, "the twists and turns of a system of threads in space ... and the manner in which the threads are interlaced." How one might annotate the path of the threads in a braid, knot or net and therefore fix for all time a method for recreating these objects was what Vandermonde sought. He considered, "a well-known problem, which belongs to this category, that of the knight’s tour in chess , solved by Euler in 1759." Vandermonde’s "Remarques sur les Problemes de Situation" (Remarks on problems of position), which I shall paraphrase here, begins by outlining his system of notation for the division of space. His method is to first establish a plane of parallel lines that is then cut by a further plane of parallel lines running perpendicular to the first set such that both sets constitute a grid.

We can now see that the shaded square in the above diagram is in the, "fourth strip of the first division and the third in the second division" of the plane. If we compare this system of notation to that of Cartesian co-ordinates then the ‘first division’ produces values of ‘x’ and the second, values of ‘y’. The shaded square can be represented by (4,3) in Cartesian notation. Vandermonde then goes on to cut the plane into a third dimension so that the grid above becomes the face of a cube resting on a table, that one is viewing from above. Thus our shaded square now has co-ordinates 1 and the one below it co-ordinates 2 and so on. The large number at the front of the notation being the depth of each level from our viewpoint. Again using Cartesian co-ordinates we could say that the level is ‘z’ and the shaded square on a cube becomes (z, x, y). Once this method is established the possibility of realising a path through the plane that passes through a series of designated points can now be fixed and Vandermonde goes on to describe the sequence of points for a plait and a stocking-stitch. Having now established the notation for three dimensions we will revert to our original two-dimensional model and look at the knight’s tour on the chessboard. The problem is to find a formula or rule that allows us to satisfy the criteria of the tour and so complete it. The method Vandermonde used was to pick an arbitrary starting point and ‘reflect’ that move in three other positions on the board so as to try and simplify the solution by creating some kind of symmetry. He achieved this by: - First list all possible squares on the board and their corresponding co-ordinates. I.e. 64 sets of co-ordinates.

Choose an arbitrary starting point and remove it from the list of all possible squares. Vandermonde chose . This square becomes the beginning of path list ‘one’. Using successive rotational symmetry of 90 o about the centre of the board create three further path lists of co-ordinates that begin with each of the three rotations’ co-ordinates i.e. , and (see diagram below). Then delete these sets of co-ordinates from the list of all possible squares leaving 60 squares. From the starting point in path list ‘one’ pick an arbitrary knight’s move from this square (such that it is in the remainder of the list of all possible squares) and note this as move 2 in path list ‘one’. Remove it from the list of all possible squares that will now be left with 59 sets of co-ordinates. Repeat the three rotations for move 2 and add them to their respective path lists remembering to delete them from the list of all possible squares leaving 56 sets of co-ordinates. Continue with this process until all squares are used up and there will be four paths lists each of 16 sets of co-ordinates. Vandermonde called these four paths lists his ‘symmetric’ lists of moves.

See diagram below showing the first four moves (in colours) and their ‘symmetries’.

By continuing in this way Vandermonde generated the four sequences of moves as follows: -

From these four sequences of moves Vandermonde noticed that the end of the first sequence was a knight’s move away from the beginning of the fourth and the end of the second a knight’s move away from the start of the third creating two ‘symmetric’ sequences thus: -

In order for the path to be re-entrant, and so become a circuit, he had to find a way to link these two sequences together and destroy his so called ‘symmetry’ a little. By placing the entire second sequence between the third and fourth terms of the first (blue to blue and red to red are knight’s moves apart) he completed his re-entrant tour that can begin at any one of the squares of the sequence. The path generated by this sequence is shown below.

Vandermonde's complete Tour

This sequence of moves is just one of many possible circuits for the knight’s tour and also represents a new way of looking at graphs i.e. how is it possible to find a path through a given graph that passes through every vertex once and once only? Of course we know this is possible for the knight’s tour because there are many solutions for the 8 x 8 board but the task of finding an Eulerian path might not be so easy. Here is the graph representing a 4 x 4 chessboard with all-possible vertices and edges.

All edge possibilities for 4 X 4

An Eulerian path must, as we have seen, pass through every edge of a graph once and once only. If one were to look at all possible edges on the 8 x 8 chessboard, we would find that there are eight vertices with odd degree and therefore, according to his rules, no Euler path (See diagram).

This diagram above shows the vertex degree of each square on the chessboard in relation to the knight’s move.

There are 8 vertices with odd degree and therefore no Euler path.

We now have a different class of problems that are commonly known as traveller problems. In Graph Theory [2] (the brackets are mine), "the explorer examines all possible routes (edges), whereas the traveller simply wishes to visit each place of interest (vertex) once." The most common expressions for these two varieties of problems are "The Postman" and "The Travelling Salesman". The Postman needs to minimise the distance he travels while at the same time making sure he delivers mail to all the streets (edges) and he doesn’t want to travel down any streets more than once. The Travelling Salesman needs to visit specific addresses (vertices) each once and only once and again minimise the distance he travels but of course he won’t need to use all the streets in order to do it. The latter is the essence of the knight’s tour although our knight must finish its journey one move away from its starting point in order to make a cycle, or re-entrant tour. When T. P. Kirkman first considered circuits in his 1855 paper, "On the Representation of Polyhedra", he discovered a class of graphs that could not contain circuits and it is this result that we shall move onto next.

Graph Theory (Section III) Back to top

Thomas Penyngton Kirkman was a rector and mathematician who explored the possibility of finding a circuit that passes through each vertex of graph once and only once. His rather complex and ultimately unprovable ideas were later picked up and refined successfully by Sir William Rowan Hamilton but not before Kirkman had managed to provide a general proof for the fact that, "if a polyhedron has an odd number of vertices and each face has an even number of edges, then there is no circuit which passes through all the vertices." [2] . This introduces the concept of a graph being bipartite i.e. if a graph can divided into two separate sets of vertices such that every edge in one set joins a vertex in the other then it is called bipartite. If therefore we require a circuit, which passes through each vertex once and only once, and return to the initial vertex then a graph with an odd number of vertices will have no such circuit. When Euler discussed this question in relation to a chessboard with n x n squares he discovered that if n is odd then there will be an odd number of squares. Since any chessboard is bipartite with two sets of squares black and white, no complete reentrant tour can exist for these boards.

Bipartite/Handshaking Lemma

First looking at the path p of the circuit that may exist can prove if the number of vertices n is odd in a bipartite connected graph then no circuit exists. If a graph has n vertices then let the initial vertex be V 0 and the final vertex V n-1 . The path for a circuit through this graph must start at the initial vertex V 0 and pass through all other vertices before reaching the final vertex V n-1 . Because the last vertex must connect to the first V 0 = V n . If the graph is bipartite then the total number of vertices will be V A + V B If we assume that V 0 is in vertex group A so that V 1 is in vertex group B, V 2 is in vertex group A and so on, then all vertices in group A will be even and all in group B will be odd. Because V n must be equal to V 0 if the graph has a circuit it holds that V n must be part of group A and therefore even. By contradiction if a possible circuit exists for even values of n then none can exist if n is odd. At the time Kirkman was looking at polyhedra there was another mathematician, William Rowan Hamilton, who was also working on a similar problem that he published in 1857 as "The Icosian Game." Hamilton’s game consisted of the net for a dodecahedron that had a pin at each of the 20 vertices representing important cities around the world. The problem was to find a route around the shape that passed through each city once and only once. The pins were provided so that a thread could be wound round them and make the path visible.

The Icosian Game

It was directly due to the concepts involved in this game that a circuit in a graph visiting every vertex once and only once became know as a Hamiltonian Line. The problem that Euler had was using each edge once and only once and really just a case of examining the vertices in a graph to see if they are even but the Hamiltonian problem has no such simple solution and indeed still today has no general criteria.

The Knight’s Tour (Section IV) Back to top

I began looking at this problem from the original question that is, can I find a path through the chessboard, using only the moves of the knight, that uses every square once and only once and finishes one knight’s move away from the starting square. As I sought solutions to the problem I came across many reference sources and literature referring to previous attempts at the problem, that had looked at more general criteria concerning the finding of Hamiltonian circuits within ‘chessboard graphs’ of varying sizes. After discovering programs have been written to look at and solve this question I found they were beyond my understanding at this point and so decided to approach it from the traditional perspective - by hand! I began by finding circuits in the 8 x 8 board using various algorithms that seemed at first most logical to me. The first of which was, "start in the corner, where there are only two possible moves (one to square 1 and the other from square 63) and work one’s way around the board sticking as close to the edge as possible bearing in mind access to square 63." This method produced the following results.

It is worth looking at this basic algorithm more closely to see where it might be improved so as to guarantee success on the first try. The algorithm, as it is, leaves the user with a few choices that could easily result in an unsuccessful solution to the problem. Specifically I first draw your attention to move 2, which originates at square 1 and moves to square 2. The choices at square 1 are two-fold i.e. to move to what actually becomes square 48 or to square 2. In this case the reasoning behind the move is to stay as close to the corner as possible if you have choices. This decision occurs again at square 45, where both options for square 46 are on the edge of the board. However, this time both choices are equidistant from a corner. As it happens either square will do to secure the tour if we stick to the original algorithm of staying as close to the edge as possible. So, apart from the second move, which must stay close to the corner, the algorithm holds. The greatest inadequacy with this algorithm is that it only works if we start in the corner and specify square 63 as our end point. What happens if I apply this algorithm to any starting square? If I arbitrarily use (3, 4) as the initial vertex then... hey presto, it works!

Unfortunately this is just a lucky second choice but does throw up a very interesting question. When using this original algorithm I have not managed to succeed every time, although if I look forward from approximately move 51 and think carefully about each of the options open to me I do succeed every time. The last quarter of the tour does seem to need refining in order to ensure a complete re-entrant tour without having to think. It certainly seems so because lengthy tours by hand using the original algorithm, resulted in many failures. Before considering what this additional statement might say I refer to an algorithm that already exists for non-re-entrant tours called the Warnsdorff algorithm. Warnsdorff’s algorithm involves looking at the valency of each of the next possible vertices (knight’s moves) and choosing that square which has the least degree so that any square likely to be isolated will be used up before isolation occurs. This is all the more logical because no vertex has less than degree 2. The only other stipulation is that if the choices of move all have the same degree then the algorithm will look further down each of the possible avenues of moves applying the least degree rule until a successful successor is found. This algorithm has proved to be very slow for large boards and fails at 76 x 76 squares.In "Solution of the Knight's Hamiltonian Path Problem on Chessboards" [5] , Ingo Wegener and his fellow researchers tried to refine the Warnsdorff system by the addition of a further rule that initially broke the larger board down into smaller sections for which there were already known tours. This is an approach that they were ultimately able to prove but is different to the Warnsdorff method. It is possible to refine the Warnsdorff algorithm so that it fails less often and this was suggested by Arnd Roth in his "Mathematica notebook"  [6]

"To amend this (the choices of move all have the same degree), I add the rule that in this case, the successor with largest Euclidean distance to the centre of the chessboard is chosen. The introduction of this global criterion substantially reduces the number of blind alleys: now it first occurs on a 428 times 428 chessboard, and the "probability" to run into one (a blind alley) is less than one percent for all chessboards smaller than 2000 times 2000 squares. (All this assumes that the starting point is in a corner of the board.)"

So, even the power of Mathematica, that was used to implement Roth’s improved algorithm, has its limitations and with it's starting point restrictions I still feel that I have made a great deal of headway with my simple algorithm. The refined version is now, "Pick an arbitrary starting square and, using the move of the knight choose your next square such that it is as close to the edge of the board as possible making sure that access to the starting square is not blocked. Where there is a choice of squares equidistant from the edge of the board one must consider the subsequent moves from each of those squares such that they must follow the previous rules." This is really about as tight as I can make it for a 8 x 8 board but is also the method I have used to approach other size boards starting with 3 x 3, the smallest board I have looked at. With this 3 x 3 board it is clear to see that no Hamiltonian circuit exists because if we start at the centre square ‘*’ we have no moves to make and if we start in any of the other squares it is impossible to reach the centre.

The 3 x 3 square was not a complete waste of time though because if we add just one extra column then we can start ‘outside’ our 3 x 3 section at ’0’. Then we complete the 3 x 3 line that again moves outside to ‘9’ back to ‘10’ (our previously unreachable square) and finishes at ‘11’. Although this doesn’t satisfy the rules for a re-entrant tour it does still use every vertex once and only once.

I note at this stage that the 3 x 3 square has 1 vertex with degree 0 and 8 vertices with degree 2 and no path or circuit exists. The sum of degrees is 16 and we know that in order for a circuit to exist every vertex must have two edges leading to a sum of 18 for a nine-vertex graph and therefore a circuit cannot exist in this graph. In the 3 x 4 rectangle however there are 8 vertices of degree 2 and 4 of degree 3 giving a total of 28. I now know there are enough edges to fulfil requirements for a circuit but none exist in this graph. I still take note of these results. For a 3 x 5 rectangle there are 8 vertices of degree 2, 4 of degree 3 and 3 of degree 4 giving a total of 40 edges. As there are 15 vertices one would expect a complete tour to have 30 edges and so it may be possible to at least find a path but I could not find one. The vertex degrees are as follows.

The path for a 3 x 6 has eluded me as well and the vertex degrees are: -

The path in the 3 x 7 board is seen to be the incomplete graph of the 3 x 3 board joined to the path of the 3 x 4 board.

Finally in this section the 3 x 8 board has a path constructed from two 3 x 4 paths linked together (see dotted line in diagram below).

I have tabulated the results below to try and uncover a rule for whether or not a path can exist. So far the table looks like this: -

I haven’t managed to formulate a proof for my assumptions but a path does exist in the 3 x 4 board and successfully links to the incomplete path in the 3 x 3 board to provide a path in the 3 x 7 board. If I continue with this hypothesis I can only find paths in boards for which the value of 3 x n can be subdivided into previously successful paths or that provide links to unsuccessful ones.

Squares Only Back to top

If I were to consider just those boards that are n x n then 3 x 3 is my starting point for which, as we have already seen, no path or tour exists. The next square to consider is that of 4 x 4. No path exists for this square and the valency for each vertex is as follows: -

The reason no path can exist for this board is that at least two of the degree 2 squares must have two edges attached and they cannot be in opposite corners or a closed circuit of four vertices would end the game. Therefore if the two start and finish squares are in corners on the same row or column all the degree 4 squares will be unable to take any further edges leaving the insoluble problem of negotiating a path around all the vertex degree 3 squares.

If we now look at the square 5 x 5 : -

As can be seen there is a path for this square, above, though there is no re-entrant tour. However, there is something interesting about this square in that it is the first to have a vertex with degree 8 that occurs in the centre square. Euler proved that in the knight’s tour problem if n is greater than or equal to 5 then a path (not necessarily a re-entrant tour) does exist, however time and workload have made it impossible for me to find it at the time of going to press. I will endeavour to find it at a later date. The circuit I found in the 6 x 6 board was the only one I could find after much searching although I can’t believe at this stage that there is only one. Of course this particular tour can start at any of its 36 squares although I choose to count this as only one knight’s tour.

The 7 x 7 board is, as I have referred to before, bipartite and therefore unable to have a tour though one of the many paths it has is shown below.

I have already looked at 8 x 8 circuits and the information I have discovered about all the n x n squares to this point is consolidated in the table below. There are many obvious patterns in the data though none seems to direct me to any conclusive proof about a general statement regarding the existence of a re-entrant tour in any given n x n board. I am sure that so long as n is even there will be a re-entrant tour however I cannot prove it and without the benefit of a computer I would hate to have to find one for large values of n.

Finally I would like to look at the possibility of extending the knight’s tour problem to finding re-entrant tours in cubes. The first fact to consider is the 3 x3 x 3 cube that has a centre vertex that cannot be reached from any other vertex of the cube, therefore a re-entrant tour cannot exist. The next cube to consider is the 4 x 4 x 4 that does have a re-entrant tour I found by hand. The problem I have is writing an algorithm to ensure success every time and I will have to leave that to a further paper. After I describe the tour using a version of Vandermonde’s original system I will attempt to describe the method I used although I don’t believe it will work every time. I have already described Vandermonde’s system of notation in 3-dimensional objects in section II and how it can be simulated in Cartesian terms, (z, x, y). I will use this altered Cartesian system to describe a re-entrant tour in a 4 x 4 x 4 cube. The notation for the bottom left hand cube in the diagram below is (1, 1, 1) and the top back right cube is (4, 2, 3).

I am currently working on a drawing of this tour in 3-dimensional space but for now it will have to wait. The reader should note at this point that the knight can now move freely in space but must still only move by a factor of (� 2, � 1) or (� 1, � 2) in any direction in 3-dimensional space as long as it stays within the volume of the designated cube. A move from (1, 1, 3) to (3, 2, 3) is an example where values of (z, x, y) satisfy these criteria. The co-ordinate tour starts at VERTEX 0 being (4, 4, 1) with vertex 63 being (2, 4, 2), one knight’s move from the initial vertex.

Of course, in respect of previous discoveries in this paper I know that to look for a tour in a 5 cube would be fruitless because it has an odd number of vertices. However I know that a path exists because it is possible to stack up five 5 x 5 squares to make a cube and therefore just a small matter of locating the link edges between each of the ‘levels.’ This method can also be successfully used to capture the ultimate in 3-dimensional chessboards, the 512-vertex polyhedron that is the 8 x 8 x 8 cube. We already know that the vertices 0 and 64 are one and the same in a re-entrant tour of the regular chessboard and we can use this information to combine the eight levels of the 8 cube into one tour by listing the ‘bridging ‘ vertices thus: -

And (3, 1, 3) is a knight’s move from (1, 1, 4) completing the tour.

Conclusions and Reflections on the Knight’s Tour Back to top

I have had an immense amount of fun and an intensely thought provoking experience in compiling these pages and there are still so many questions. Can I adapt Warnsdorff’s algorithm to find paths and re-entrant tours in cubes for given values of n cubes or (p x q x r) rectangles? Where can I find Euler’s proof for paths in squares of n is greater than or equal to  5? What is the significance of the patterns I found when tabulating some of my data and how can I use this information to draw some definite conclusions? There are so many more questions to ask that I don’t have the space here to go into them but I do realise from my research that I have at least lit upon an area of mathematics that is still unsettled in some areas. There is still today no general criteria for the finding of Hamiltonian circuits in a given graph and maybe my explorations might be of help in that department but as yet I can’t see it. I will try to produce a written English algorithm for my tours in a cube but for the meantime I will add some of my findings to my website because the many people out there who have also been looking at this problem might find it useful. There is a list of references in the Bibliography that I have used in addition to those quoted in the body of this document and I would like to bring special attention to the historical use of knight’s tours in the field of cryptography. As I mentioned before, one of the French mathematicians’ de Moivre’s tours is the favourite to have been used as an encoding device in the ‘The Second Parchment at Rennes-le-Chateau’ that is fascinating reading for any budding Sherlock Holmes’ out there. And finally as a student teacher I would like to point out that the knight’s tour is a great exercise to try in the classroom both for simple educative fun and more extended work as required.

Bibliography and References Back to top

[1] Cranshaw Ted The Second Parchment at Rennes-le-Chateau ( http://www.fiu.edu/~mizrachs/parchmen.htm ) [2] N. L. Biggs, E. K. Lloyd, R. J. Wilson Graph Theory 1736 - 1936 (1976) Oxford, Oxford University Press Beineke & Wilson Graph Connections (1997) London, Clarenden Press [5] A. Conrad, T. Hindrichs, H. Morsy & I. Wegener: Solution of the Knight's Hamiltonian Path Problem on Chessboards . Discr. Appl. Math. 50, 125-134 (1994). John Clark and Derek Allan Holton A first Look at Graph Theory (1991) Singapore, World Scientific [3] Oystein Ore Graphs and their uses (1963) Stanford, California, USA, Random House W. T. Tutte Graph Theory as I have known it (1998) London, Clarenden Press Robin J. Wilson Introduction to Graph Theory (1972) Harlow, Longman Scientific & Technical [6] Arnd Roth's Homepage - Studying physics in Heidelberg he spends a lot of time doing electrophysiologyalthough his main scientific interests are computational physics, computational neuroscience, and software environments for scientific computation, such as Mathematica and NEURON . Other Graph Theory and Related Pages by Stephen C. Locke - This site covers all aspects of Graph Theory in general and is a valuable starting point if you are looking for plenty of link suggestions. Combinatoric Object Server - Not much more I'm afraid but still useful. Paul E. Black - A computer scientist from Maryland, USA who has some great research and links that are an absolute necessity for anyone interested in algorithms and graph theory. Gunno T�rnberg - Thoughts and research on the Travelling Salesman's Problem with other very useful links. A top chap who helped me greatly with the accuracy of these pages of mine. Gunno also has a great Knight's Tour page that is well worth a visit at this address . All material, produced by whatever means in these pages, Copyright � Mark Richard Keen 2000 Please feel free to sign the visitor's book. My Guestbook Back to top

Knight's Tour

knight's tour 6x6 solution

  • Eight Queens
  • Uncrossed Knight's Path
  • Queen Domination
  • Three Kings

knight's tour 6x6 solution

  • About Plays.org
  • Alessandro Pezzetti Interview
  • Interview of Maximiliano Demonte
  • Juega a Nuestros Juegos en Línea Gratuitos Basados ​​en Navegador
  • Mainkan Game Video Online Gratis Yang Menyenangka
  • No App Downloads Required! Play Thousands of Free Browser-Based Online Games
  • Online Video Jogos Gratis
  • Password Reset
  • Play Free Online Games
  • Play Our Free Browser-Based Online Games
  • Register Your Free Account
  • Your Saved Games

knight's tour 6x6 solution

Free Play + No Downloads = Win

Play This Game Now

Play Canvas Knights Tour as a stand alone web app.

Canvas Knight’s Tour: Open & Closed Knights Tour Chess Board

Favorite

This Canvas Knights Tour is a Chess training puzzle to help you memorize the chess board and the possible moves for a knight. A knight starts at any square of the board and moves to the remaining 63 squares without ever jumping to the same square more than once.

A default chess board contains 64 squares in an 8×8 grid. On this game you could set the grid size to as small as 4×4 or as big as over 100×100, though you’ll have to do a lot of scrolling if you make the board 10,000 plus squares. 🙂

knight's tour 6x6 solution

Canvas Knight’s Tour Game Online

Chess players can start this chess inspired game by clicking in the window below.

Alternatively you can play this chess game for free as a web application here .

Canvas Knights Tour Chess Puzzle Play Instructions

knight's tour 6x6 solution

How to Play

Move the knight around the board remaining 63 squares without ever jumping to the same square more than once.

  • The game is presented as a 10×10 grid of squares. Select the 8×8 grid to simulate a chess board. The squares can be changed using the control at the top of the screen.
  • Click in a blank square to make the first move.
  • Moves can be undone using the reverse undo button at the top of the screen.
  • A knight moves to a square that is two squares horizontally and one square vertically, or two squares vertically and one square horizontally. Visit every square once only until you complete the entire board..
  • The Closed Knight’s Tour are those in which the knight’s last move is one knight’s move away from the initial position. The knight’s path forms a loop whereby the knight can always go through the same path. There are 26,534,728,821,064 possible closed tours on a standard 8 by 8 playing board.
  • There are 19,591,828,170,979,904 possible Knight’s Tours in total.
  • The Open Knight’s tour is when the knight can’t reach its starting square from its final position. The knight can’t go through the same path.
  • Getting stuck? See the images below for a solution.
  • Brute force: only works on small boards
  • Divide-and-conquer: break boards into smaller component boards to solve
  • Warnsdorff’s rule: heuristic which moves each forward move to whichever square has the fewest remaining forward moves without revisiting an already visited square
  • Neural network solutions: each legal move is treated as a neuron
  • For more detail on the Knight’s Tour, checkout the Wikipedia entry or check out this GeeksforGeeks backtracking article ..

Possible Knight’s Tour Solutions Based on Board Side

Like this game review this knight’s tour chessboard puzzle.

Be the first to leave a review.

This review has no replies yet.

  • Originality
  • Replayability

Free Knights Tour Puzzle For Chess Players Screenshot

Knight Tour Gameplay Screenshot.

Mobile Friendly Cross Browser Support

This game is rendered in mobile-friendly HTML5, so it offers cross-device gameplay. You can play it on mobile devices like Apple iPhones, Google Android powered cell phones from manufactures like Samsung, tablets like the iPad or Kindle Fire, laptops, and Windows-powered desktop computers. All game files are stored locally in your web browser cache. This game works in Apple Safari, Google Chrome, Microsoft Edge, Mozilla Firefox, Opera and other modern web browsers.

Play More Fun Games

Want to play more fun games? Players who enjoyed this game also played the following games.

Junior Chess Game.

Plays.org published this Chess on July 1, 2021 / 0 Comments -->

Where To? What Next?

This game was published in these categories: Chess . You can visit any of them to select other fun games to play.

Our site hosts thousands of free online games. Check out the newest additions to our library or play a random game!

knight's tour 6x6 solution

This game was published using our teamwide Plays.org account. If you have any comments, questions, concerns, or others (are there others even???) you can use the comments below to send along your 2 cents and help us improve the site further :) Your 2 cents plus 3 cents will buy you a nickel, but if your comments are genuinely useful and/or helpful and/or funny and/or memorable in a good way, we will probably say thanks :D

Leave a Reply Cancel reply

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

Exclusive Games

Vehicle Factory.

Vehicle Factory

Farm Rescue game.

Farm Rescue

Tyrian Purple.

Tyrian Purple

Karen Woke in San Francisco game.

Karen Woke in San Francisco

knight's tour 6x6 solution

Search And Find And Plays.org Your Free Online Games :)

Explore our entire game catalog.

  • Adventure Time
  • Apple & Onion
  • B&W Mahjong
  • Base Defense
  • Board Games
  • Brick Breaker
  • Bubble Shooter
  • Cat in the Hat
  • Chain Reaction
  • Chhota Bheem
  • Connect the Dots
  • Cooperative
  • Craig of the Creek
  • Crash & Bernstein
  • Cross the Road
  • Daniel Tiger
  • Dennis & Gnasher
  • Descendants
  • Design Squad
  • Destruction
  • Dinosaur Train
  • Donkey Hodie
  • Environmental
  • Fairly OddParents
  • Find Differences
  • Flappy Bird
  • Freecell Solitaire
  • Gamer's Guide
  • Golf Solitaire
  • Grabber Mahjong
  • Grizzy & the Lemmings
  • Henry Danger
  • Hero Elementary
  • Hidden Object
  • Inspector Gadget
  • Jigsaw Puzzles
  • Kindergarten
  • Klondike Solitaire
  • Knife Throwing
  • Let's Go Luna
  • Looney Tunes
  • Mahjong Connect
  • Mahjong Sequence
  • Mahjong Slide
  • Mahjong Solitaire
  • Master Moley
  • Maze Attack
  • Mighty MagiSwords
  • Minesweeper
  • Molly of Denali
  • Multiplication
  • Path Making
  • Powerpuff Girls
  • Pyramid Solitaire
  • Regular Show
  • Rusty Rivets
  • Sanjay & Craig
  • Sesame Street
  • Slide Puzzles
  • Sofia the First
  • Spider Solitaire
  • Splash and Bubbles
  • Steven Universe
  • Subtraction
  • Team Hamster
  • Teen Titans Go
  • Thanksgiving
  • Tom & Jerry
  • Tower Mahjong
  • Traffic Management
  • Transformers
  • Tripeaks Solitaire
  • Triple Mahjong
  • Uncle Grandpa
  • Valentine's Day
  • Victor & Valentino
  • Wacky Races
  • We Bare Bears
  • Wizard of Oz
  • Word Search

© 2024 Plays.org | About Us | Privacy | Facebook | Instagram | Twitter | Pinterest

Horse Knight game.

Horse Knight

Slime Climb.

Slime Climb

Solar Arbiter.

Solar Arbiter

Restart game.

New & Cool

Leaftek and Elemental Power.

Leaftek and Elemental Power

Foam Party.

Set Up Your Free Account Today

Want to keep a list of your favorite games? Create your free account today so you can collect and share your favorite games & play our new exclusive games first.

We offer thousands of free online games from developers like RavalMatic , QKY Games , Havana24 & Untitled Inc.

Search And Find And Plays.org Your Free Online Games 🙂

IMAGES

  1. Knights tour solved for 6x6 chessboard

    knight's tour 6x6 solution

  2. knight's tour problem 6x6 chessboard

    knight's tour 6x6 solution

  3. Knight's Tour Problem

    knight's tour 6x6 solution

  4. hamiltonian path

    knight's tour 6x6 solution

  5. python

    knight's tour 6x6 solution

  6. Chessboard Puzzles Part 3

    knight's tour 6x6 solution

VIDEO

  1. THE KNIGHT!1!!1!!

  2. full knight

  3. A closed Knight's Tour

  4. Mã Đi Tuần

  5. Knight 2000 CT Mini-Walkthrough

  6. KNİGHT ONLİNE ZERODA GÖREV İTEMİYLE PK ATILIRMI ?

COMMENTS

  1. Closed Knight's Tours of the 6 by 6 Board

    Enumeration. The total of geometrically distinct closed 6×6 tours is 1245.These consist of 5 with quaternary symmetry, 17 with binary symmetry and 1223 asymmetric. Thus since an asymmetric tour can be presented in 8 different orientations, a binary symmetric tour in 4 different orientations and a quaternary symmetric tour in 2 different orientations there are 5×2 + 17×4 + 1223×8 = 10 + 68 ...

  2. How I can shortly prove that you can have a closed knight's tour on the

    On the website, the explanation that a knight's tour on a $6\times6$ board is possible is the continued proof of around $1\frac{1}{2}$ pages! It will be great if one of you could provide a simple, concise proof that the $6\times6$ is possible.. After being asked this question I tried to formulate conjectures to try and prove that the 6x6 is possible by finding solutions based on rules that I ...

  3. knight's tour problem 6x6 chessboard

    The Knight's Tour is a mathematical problem involving a knight on a chessboard. The knight is placed on the empty board and, moving according to the rules of...

  4. Knights tour solved for 6x6 chessboard

    Link to code: https://github.com/ironmaniiith/cool-stuffs/tree/master/knights-tourHappy Coding :D

  5. The Knight's tour problem

    The Knight's tour problem. Backtracking is an algorithmic paradigm that tries different solutions until finds a solution that "works". Problems that are typically solved using the backtracking technique have the following property in common. These problems can only be solved by trying every possible configuration and each configuration is ...

  6. Knight's tour

    An open knight's tour of a chessboard An animation of an open knight's tour on a 5 × 5 board. A knight's tour is a sequence of moves of a knight on a chessboard such that 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 ...

  7. A Knight's Tour

    The knight's tour puzzle is played on a chess board with a single chess piece, the knight. The object of the puzzle is to find a sequence of moves that allow the knight to visit every square on the board exactly once, like so: One possible knight's tour. One such sequence is called a "tour.". The upper bound on the number of possible ...

  8. The Knight's Tour: Where Chess, Programming, and Math Meet

    The Knight's Tour is a problem that asks if the knight can go through all of the 64 squares of a chess board without landing in the same square twice. But first, we need to tackle the smaller cases. Which is the smaller size of a board which might have a solution? 2x2, No. The knight cannot make any move. 3x3, No. The knight cannot land at ...

  9. Knight's Tour » Linux Magazine

    Most of the Knight's Tour solution videos you watch on YouTube and elsewhere demonstrate the Diamonds and Squares method. The second approach is known as Warnsdorff's rule. This strategy takes a bit more effort to master. ... Unlike Warnsdorff's rule, the Diamonds and Squares technique cannot be used to solve the Knight's Tour on a 6x6 or a ...

  10. 9.14. Knight's Tour Analysis

    For a 6x6 board, \(k = 4.4\), there are \(1.5 \times 10^{23}\) ... 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 ...

  11. 8.14. Knight's Tour Analysis

    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 × 10 14. For a 6x6 board, k = 4.4, there are 1.5 × 10 23 nodes, and for a regular 8x8 chess board, k = 5.25, there are 1.3 × 10 46. Of course, since there are multiple solutions to the problem we won't have to explore every single node ...

  12. Algorithm for knight's tour on a 6x6 array only works on index [0, 0]

    The Knight's tour is a chessboard # puzzle in which the objective is to find a sequence of moves by the knight in # which it visits every square on the board exactly one. It uses a 6x6 array for # the chessboard where each square is identified by a row and column index, the # range of which both start at 0.

  13. Some Closed Knight's Tours

    The following small knight's tour was used as part of the base of the recursion in a divide-and-conquer algorithm described in Ian Parberry, "An Efficient Algorithm for the Knight's Tour Problem", Discrete Applied Mathematics, Vol. 73, pp. 251-260, 1997.[]You may have noticed by now that all of the closed knight's tours you have seen so far (6x6, 8x8, and 10x10) have even sides.

  14. Optimizing Recursion in Knight's Tour

    Optimizing Recursion in Knight's Tour. I'm trying to write a program for a university project. It should count all possible open tours (i.e. the start and end fields are not the same) recursively on a chessboard depending on board size and starting field (as per assignment). If the size is less than 6x6, all of the solutions should be displayed ...

  15. Knight's Tour Generator: Main Page

    Generate. A knight's tour or tourney will be saved in SVG format (a vector graphics image file that can be viewed in a browser) and as a text file listing the knight's move 0-7 from each cell of a square chessboard. You will be prompted for the generation algorithm, the tourney type, whether or not the board is to be blurred, and the board size ...

  16. 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 ...

  17. Optimal algorithms for constructing knight's tours on arbitrary

    The knight's tour problem is an ancient puzzle whose goal is to find out how to construct a series of legal moves made by a knight so that it visits every square of a chessboard exactly once. ... Solution of the knight's Hamiltonian path problem on chessboards. Discrete Appl. Math., 50 (1994), pp. 125-134. View PDF View article View in Scopus ...

  18. Using the Knight's Tour to impress

    The Knight's Tour. The "Knight's Tour" of the chessboard was first proposed (solved) in a ninth century Arabic manuscript by Abu Zakariya Yahya ben Ibrahim al-Hakim. The author give two tours, one by Ali C. Mani, an otherwise unknown chess player, and the other by al-Adli ar-Rumi, who flourished around 840 and is known to have written a book on ...

  19. Mark R. Keen

    The Knight's tour puzzle can be played in many different ways but the original, as far as I can tell, is to begin on an arbitrary square of the board and visit every other square once and only once using the moves of the knight. ... T. Hindrichs, H. Morsy & I. Wegener: Solution of the Knight's Hamiltonian Path Problem on Chessboards. Discr ...

  20. Knight's Tour

    The only restriction is that the knight cannot visit the same square twice. The puzzle is said to be completed if the knight visited all squares (i.e. 64 on a standard 8x8 board) on the board. The classic Knight's Tour problem can be extended to any board size (larger than 4). In this small game you can test nine different board size: 5x5, 6x6 ...

  21. Canvas Knight's Tour: Open & Closed Knights Tour Chess Board

    Play Canvas Knight's Tour game online for free. Use our free simulator to conduct open or closed Knights Tours for boards of any size board. This game is rendered in mobile-friendly HTML5, so it offers cross-device gameplay. You can play it on mobile devices like Apple iPhones, Google Android powered cell phones from manufactures like Samsung, tablets like the iPad or Kindle Fire, laptops, and ...