Question

In: Advanced Math

The Knight’s Tour Puzzle asks if it is possible to find a sequence of 64 knight’s...

The Knight’s Tour Puzzle asks if it is possible to find a sequence of 64 knight’s moves so that a knight on a chessboard visits all the different squares and ends up on the starting point.
a) Formulate the problem in terms of graphs.

b) Can the puzzle be solved?

c) Can you find an explicit solution?

d) What happens on a 3×3 chessboard

This question from Euler and Hamilton Paths and Circuits.

Thanks in advance.

Solutions

Expert Solution

Knight’s Tour Puzzle :-

A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once. If the knight ends on a square that is one knight's move from the beginning square so that it could tour the board again immediately, following the same path,Then the tour is closed or it opens again

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

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

Knight's graph showing all possible paths for a knight's tour on a standard 8 × 8 chessboard. The numbers on each node indicate the number of possible moves that can be made from that position.

a):Knight Graph:-

The knight graph is a graph on vertices in which each vertex represents a square in an chessboard, and each edge corresponds to a legal move by a knight (which may only make moves which simultaneously shift one square along one axis and two along the other).

The number of edges in the knight graph is (8 times the triangular numbers), so for , 2, ..., the first few values are 0, 0, 8, 24, 48, 80, 120, ...

Knight graphs are bipartite and therefore are perfect.

The following table summarizes some named graph complements of knight graphs.

-knight graph -queen graph
-knight graph -queen graph

The knight graph is implemented in the Wolfram Language as KnightTourGraph[m, n], and precomputed properties are available in using GraphData["Knight", m, n].

Closed formulas for the numbers of -graph cycles of the knight graph are given by for odd and

A knight's path is a sequence of moves by a knight such that each square of the board is visited exactly once. It is therefore a Hamiltonian path on the corresponding knight graph.

The above figures show six knight's paths on an chessboard, all but the first of which are re-entrant. The final path has the additional property that it is a semimagic square with row and column sums of 260 and main diagonal sums of 348 and 168.If the final position of such a path is a knight's move away from the initial position of the knight, the path is called re-entrant or closed and corresponds to a Hamiltonian cycle on the underlying knight graph. It shows that a knight's tour exists on an board iff and is even.

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

Brute-force algorithms

A brute-force search for a knight's tour is impractical on all but the smallest boards.

For example, there are approximately 4×1051 possible move sequences on an 8 × 8 board and it is well beyond the capacity of modern computers (or networks of computers) to perform operations on such a large set. However, the size of this number is not indicative of the difficulty of the problem, which can be solved "by using human insight and ingenuity ... without much difficulty.

Warnsdorff's rule

It is a heuristic for finding a single knight's tour. The knight is moved so that it always proceeds to the square from which the knight will have the fewest onward moves. When calculating the number of onward moves for each candidate square, we do not count moves that revisit any square already visited. It is possible to have two or more choices for which the number of onward moves is equal;

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

A graphical representation of Warnsdorff's Rule. Each square contains an integer giving the number of moves that the knight could make from that square. In this case, the rule tells us to move to the square with the smallest integer in it, namely 2.

Neural network solutions:-

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

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

where represents discrete intervals of time, is the state of the neuron connecting square to square , is the output of the neuron from to , and is the set of neighbors of the neuron.

Although divergent cases are possible, the network usually eventually converges, which occurs when no neuron changes its state from time to . When the network converges, either the network encodes a knight's tour or a series of two or more independent circuits within the same board.


Related Solutions

Draw all possible border pieces of a puzzle, each having a different shape. Border-pieces are puzzle...
Draw all possible border pieces of a puzzle, each having a different shape. Border-pieces are puzzle pieces that have at least one smooth edge.
Scala: Write and test a program as elegantly as possible You are given a puzzle like...
Scala: Write and test a program as elegantly as possible You are given a puzzle like this: 7 __ 10 __ 2 Each blank may be filled with a ‘+’ (plus) or ‘-’ (minus), producing a value k. For all combinations of plus and minus, find the value of k that is closest to 0. In the above case, there are 4 combinations, each producing a different value: 7 + 10 + 2 = 19 7 + 10 - 2...
Refer to the table of codons for the following question. A possible sequence of nucleotides in...
Refer to the table of codons for the following question. A possible sequence of nucleotides in the template strand of DNA that would code for the polypeptide sequence phe-leu-ile-val would be _____. (Hint: TEMPLATE strand!) 5’ TTG-CTA-CAG-TAG 3’ 5’ AUG-CTG-CAG-TAT 3’ 3’ AAA-AAT-ATA-ACA 5’ 3’ AAA-GAA-TAA-CAA 5’
The Knapsack problem is an optimization problem that asks to fill a knapsack with maximum possible...
The Knapsack problem is an optimization problem that asks to fill a knapsack with maximum possible value. Using greedy paradigm, we can solve this problem easily. Your task is the following: (a) Write the pseudo-code of a greedy solution for knapsack problem. (b) Give is the time complexity of your solution in part (a). (c) Implement part (a) in C programming language.
Suppose a beginning physics student asks you if it’s possible for a particle to be at...
Suppose a beginning physics student asks you if it’s possible for a particle to be at two different places at the same instant in time. Use the Double-Slit Experiment to answer the student’s question. Details would be really helpful
The Knapsack problem is an optimization problem that asks to fill a knapsack with maximum possible...
The Knapsack problem is an optimization problem that asks to fill a knapsack with maximum possible value. Using greedy paradigm, we can solve this problem easily. Your task is the following: (a) Write the pseudo-code of a greedy solution for knapsack problem. (b) Give is the time complexity of your solution in part (a). (c) Implement part (a) in C programming language.
What are the antibiotic resistant genes for doxycycline? If possible, give the gene sequence.
What are the antibiotic resistant genes for doxycycline? If possible, give the gene sequence.
64. Computationally predicting protein structure from a sequence may involve a “homology modeling” approach and/or “ab...
64. Computationally predicting protein structure from a sequence may involve a “homology modeling” approach and/or “ab initio” techniques such as fragment assembly. Describe how both evolutionary data and knowledge of physico-chemical principles / force fields are used in predicting the structure adopted by a protein sequence.
For a given RNA sequence, there are 3 possible ORFs. How is the actual ORF determined...
For a given RNA sequence, there are 3 possible ORFs. How is the actual ORF determined by the cell?
Sequence 1: 5'ACTGTCGATGCTAGCTTGATCCAAGTATTGCTAGACAGAATTGACATATAGGCGATGCTAGT3' Sequence 2: 5'ATCGCTAGGATCGCTAGATTTAAGTCGCTGATCGGCTAGATATAACAGGTCCTGAATCGCTA3' Design a splint oligomer and write the all-possible content(s) needed...
Sequence 1: 5'ACTGTCGATGCTAGCTTGATCCAAGTATTGCTAGACAGAATTGACATATAGGCGATGCTAGT3' Sequence 2: 5'ATCGCTAGGATCGCTAGATTTAAGTCGCTGATCGGCTAGATATAACAGGTCCTGAATCGCTA3' Design a splint oligomer and write the all-possible content(s) needed for reaction to occur.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT