{"version":"1.0","provider_name":"SOUL OF MATHEMATICS","provider_url":"https:\/\/soulofmathematics.com","author_name":"Rajarshi Dey","author_url":"https:\/\/soulofmathematics.com\/index.php\/author\/rajarshidey1729gmail-com\/","title":"The Knight's Tour - SOUL OF MATHEMATICS","type":"rich","width":600,"height":338,"html":"<blockquote class=\"wp-embedded-content\" data-secret=\"NyAIqPOpg3\"><a href=\"https:\/\/soulofmathematics.com\/index.php\/the-knights-tour\/\">The Knight&#8217;s Tour<\/a><\/blockquote><iframe sandbox=\"allow-scripts\" security=\"restricted\" src=\"https:\/\/soulofmathematics.com\/index.php\/the-knights-tour\/embed\/#?secret=NyAIqPOpg3\" width=\"600\" height=\"338\" title=\"&#8220;The Knight&#8217;s Tour&#8221; &#8212; SOUL OF MATHEMATICS\" data-secret=\"NyAIqPOpg3\" frameborder=\"0\" marginwidth=\"0\" marginheight=\"0\" scrolling=\"no\" class=\"wp-embedded-content\"><\/iframe><script type=\"text\/javascript\">\n\/* <![CDATA[ *\/\n\/*! This file is auto-generated *\/\n!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);\n\/* ]]> *\/\n<\/script>\n","thumbnail_url":"https:\/\/i0.wp.com\/soulofmathematics.com\/wp-content\/uploads\/2020\/09\/ILAIsmB.gif?fit=335%2C334&ssl=1","thumbnail_width":335,"thumbnail_height":334,"description":"The\u00a0knight&#8217;s tour problem\u00a0is the\u00a0mathematical problem\u00a0of finding a knight&#8217;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&#8217;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&#8217;s tour problem is an instance of the more general\u00a0Hamiltonian path problem\u00a0in\u00a0graph theory. The problem of finding a closed knight&#8217;s tour is similarly an instance of the\u00a0Hamiltonian cycle problem. Unlike the general Hamiltonian path problem, the knight&#8217;s tour problem can be solved in\u00a0linear 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\u00a0V = { v1, v2, v3, &#8230; , vn }\u00a0and E = {(i, j)|i \u2208 V and j \u2208 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| &#8211; 2)! Existence Schwenk\u00a0proved that for any\u00a0m\u00a0\u00d7\u00a0n\u00a0board with\u00a0m\u00a0\u2264\u00a0n, a closed knight&#8217;s tour is always possible\u00a0unless\u00a0one or more of these three conditions are met: m&nbsp;and&nbsp;n&nbsp;are both odd m&nbsp;= 1, 2, or 4 m&nbsp;= 3 and&nbsp;n&nbsp;= 4, 6, or 8. Cull\u00a0and Conrad\u00a0proved that on any rectangular board whose smaller dimension is at least 5, there is a (possibly open) knight&#8217;s tour. n Number of directed tours (open and closed)on an&nbsp;n&nbsp;\u00d7&nbsp;n&nbsp;board(sequence&nbsp;A165134&nbsp;in the&nbsp;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\u2019s move on the chessboard is represented by a neuron. Therefore, the network basically takes the shape of the&nbsp;knight\u2019s graph&nbsp;over an&nbsp;n\u00d7n&nbsp;chess board. (A knight\u2019s graph is simply the set of all knight moves on the board) Each neuron can be either \u201cactive\u201d or \u201cinactive\u201d (output of 1 or 0). If a neuron is active, it is considered part of the solution to the knight\u2019s tour. Once the network is started, each active neuron is configured so that it reaches a \u201cstable\u201d 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\u00a0t\u00a0represents time (incrementing in discrete intervals),\u00a0U(Ni,j)\u00a0is the state of the neuron connecting square\u00a0i\u00a0to square\u00a0j,\u00a0V(Ni,j)\u00a0is the output of the neuron from\u00a0i\u00a0to\u00a0j, and\u00a0G(Ni,j)\u00a0is the set of \u201cneighbors\u201d of the neuron (all neurons that share a vertex with\u00a0Ni,j). Code For Knight&#8217;s Tour"}