1.0SOUL OF MATHEMATICShttps://soulofmathematics.comRajarshi Deyhttps://soulofmathematics.com/index.php/author/rajarshidey1729gmail-com/rich600338<blockquote class="wp-embedded-content" data-secret="QwVBFKVdYW"><a href="https://soulofmathematics.com/index.php/the-knights-tour/">The Knight’s Tour</a></blockquote><iframe sandbox="allow-scripts" security="restricted" src="https://soulofmathematics.com/index.php/the-knights-tour/embed/#?secret=QwVBFKVdYW" width="600" height="338" title="“The Knight’s Tour” — SOUL OF MATHEMATICS" data-secret="QwVBFKVdYW" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" class="wp-embedded-content"></iframe><script type="text/javascript"> /* <![CDATA[ */ /*! This file is auto-generated */ !function(d,l){"use strict";l.querySelector&&d.addEventListener&&"undefined"!=typeof URL&&(d.wp=d.wp||{},d.wp.receiveEmbedMessage||(d.wp.receiveEmbedMessage=function(e){var t=e.data;if((t||t.secret||t.message||t.value)&&!/[^a-zA-Z0-9]/.test(t.secret)){for(var s,r,n,a=l.querySelectorAll('iframe[data-secret="'+t.secret+'"]'),o=l.querySelectorAll('blockquote[data-secret="'+t.secret+'"]'),c=new RegExp("^https?:$","i"),i=0;i<o.length;i++)o[i].style.display="none";for(i=0;i<a.length;i++)s=a[i],e.source===s.contentWindow&&(s.removeAttribute("style"),"height"===t.message?(1e3<(r=parseInt(t.value,10))?r=1e3:~~r<200&&(r=200),s.height=r):"link"===t.message&&(r=new URL(s.getAttribute("src")),n=new URL(t.value),c.test(n.protocol))&&n.host===r.host&&l.activeElement===s&&(d.top.location.href=t.value))}},d.addEventListener("message",d.wp.receiveEmbedMessage,!1),l.addEventListener("DOMContentLoaded",function(){for(var e,t,s=l.querySelectorAll("iframe.wp-embedded-content"),r=0;r<s.length;r++)(t=(e=s[r]).getAttribute("data-secret"))||(t=Math.random().toString(36).substring(2,12),e.src+="#?secret="+t,e.setAttribute("data-secret",t)),e.contentWindow.postMessage({message:"ready",secret:t},"*")},!1)))}(window,document); /* ]]> */ </script> https://i0.wp.com/soulofmathematics.com/wp-content/uploads/2020/09/ILAIsmB.gif?fit=335%2C334&ssl=1335334The knight’s tour problem is the mathematical problem of finding a knight’s tour, and probably making knight the most interesting piece on the chess board. The knight visits every square exactly once, if the knight ends on a square that is one knight’s move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is closed; otherwise, it is open. The knight’s tour problem is an instance of the more general Hamiltonian path problem in graph theory. The problem of finding a closed knight’s tour is similarly an instance of the Hamiltonian cycle problem. Unlike the general Hamiltonian path problem, the knight’s tour problem can be solved in linear time. Hamiltonian Path Problem In Graph Theory, a graph is usually defined to be a collection of nodes or vertices and the set of edges which define which nodes are connected with each other. So we use a well known notation of representing a graph G = (V,E) where V = { v1, v2, v3, … , vn } and E = {(i, j)|i ∈ V and j ∈ V and i and j is connected}. Hamiltonian Path is defined to be a single path that visits every node in the given graph, or a permutation of nodes in such a way that for every adjacent node in the permutation there is an edge defined in the graph. Notice that it does not make much sense in repeating the same paths. In order to avoid this repetition, we permute with |V|C2 combinations of starting and ending vertices. Simple way of solving the Hamiltonian Path problem would be to permutate all possible paths and see if edges exist on all the adjacent nodes in the permutation. If the graph is a complete graph, then naturally all generated permutations would quality as a Hamiltonian path. For example. let us find a Hamiltonian path in graph G = (V,E) where V = {1,2,3,4} and E = {(1,2),(2,3),(3,4)}. Just by inspection, we can easily see that the Hamiltonian path exists in permutation 1234. The given algorithm will first generate the following permutations based on the combinations:1342 1432 1243 1423 1234 1324 2143 2413 2134 2314 3124 3214 The number that has to be generated is (|V|C2 ) (|V| – 2)! Existence Schwenk proved that for any m × n board with m ≤ n, a closed knight’s tour is always possible unless one or more of these three conditions are met: m and n are both odd m = 1, 2, or 4 m = 3 and n = 4, 6, or 8. Cull and Conrad proved that on any rectangular board whose smaller dimension is at least 5, there is a (possibly open) knight’s tour. n Number of directed tours (open and closed)on an n × n board(sequence A165134 in the OEIS) 1 1 2 0 3 0 4 0 5 1,728 6 6,637,920 7 165,575,218,320 8 19,591,828,170,979,904 Neural network solutions The neural network is designed such that each legal knight’s move on the chessboard is represented by a neuron. Therefore, the network basically takes the shape of the knight’s graph over an n×n chess board. (A knight’s graph is simply the set of all knight moves on the board) Each neuron can be either “active” or “inactive” (output of 1 or 0). If a neuron is active, it is considered part of the solution to the knight’s tour. Once the network is started, each active neuron is configured so that it reaches a “stable” state if and only if it has exactly two neighboring neurons that are also active (otherwise, the state of the neuron changes). When the entire network is stable, a solution is obtained. The complete transition rules are as follows: where t represents time (incrementing in discrete intervals), U(Ni,j) is the state of the neuron connecting square i to square j, V(Ni,j) is the output of the neuron from i to j, and G(Ni,j) is the set of “neighbors” of the neuron (all neurons that share a vertex with Ni,j). Code For Knight’s Tour