{"id":1369,"date":"2021-05-27T11:44:18","date_gmt":"2021-05-27T06:14:18","guid":{"rendered":"https:\/\/soulofmathematics.com\/?p=1369"},"modified":"2021-05-27T11:44:19","modified_gmt":"2021-05-27T06:14:19","slug":"the-knights-tour","status":"publish","type":"post","link":"https:\/\/soulofmathematics.com\/index.php\/the-knights-tour\/","title":{"rendered":"The Knight’s Tour"},"content":{"rendered":"\n

The\u00a0knight’s tour problem<\/strong>\u00a0is the\u00a0mathematical problem\u00a0of 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.<\/p>\n\n\n\n

The knight’s tour problem is an instance of the more general\u00a0Hamiltonian path problem\u00a0in\u00a0graph theory. The problem of finding a closed knight’s tour is similarly an instance of the\u00a0Hamiltonian cycle problem. Unlike the general Hamiltonian path problem, the knight’s tour problem can be solved in\u00a0linear time.<\/p>\n\n\n\n

Hamiltonian Path Problem <\/h3>\n\n\n\n
\"\"<\/figure><\/div>\n\n\n\n

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<\/sub>, v2<\/sub>, v3<\/sub>, … , vn<\/sub> }<\/em>\u00a0and E = {(i, j)|i \u2208 V and j \u2208 V and i and j is connected}.<\/p>\n\n\n\n

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|<\/sub>C2<\/sub> combinations of starting and ending vertices.<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

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<\/p>\n\n\n\n

The number that has to be generated is (|V|<\/sub>C2<\/sub> ) (|V| – 2)!<\/p>\n\n\n\n

Existence<\/h3>\n\n\n\n
\"\"<\/figure><\/div>\n\n\n\n

Schwenk\u00a0proved that for any\u00a0m<\/em>\u00a0\u00d7\u00a0n<\/em>\u00a0board with\u00a0m<\/em>\u00a0\u2264\u00a0n<\/em>, a closed knight’s tour is always possible\u00a0unless<\/em>\u00a0one or more of these three conditions are met:<\/p>\n\n\n\n

  1. m<\/em> and n<\/em> are both odd<\/li>
  2. m<\/em> = 1, 2, or 4<\/li>
  3. m<\/em> = 3 and n<\/em> = 4, 6, or 8.<\/li><\/ol>\n\n\n\n

    Cull\u00a0and Conrad\u00a0proved that on any rectangular board whose smaller dimension is at least 5, there is a (possibly open) knight’s tour.<\/p>\n\n\n\n

    n<\/em><\/th>Number of directed tours (open and closed)
    on an n<\/em> \u00d7 n<\/em> board
    (sequence A165134<\/a> in the OEIS<\/a>)<\/th><\/tr>
    1<\/td>1<\/td><\/tr>
    2<\/td>0<\/td><\/tr>
    3<\/td>0<\/td><\/tr>
    4<\/td>0<\/td><\/tr>
    5<\/td>1,728<\/td><\/tr>
    6<\/td>6,637,920<\/td><\/tr>
    7<\/td>165,575,218,320<\/td><\/tr>
    8<\/td>19,591,828,170,979,904<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

    Neural network solutions<\/h3>\n\n\n\n

    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 knight\u2019s graph<\/em> over an n\u00d7n chess board. (A knight\u2019s graph is simply the set of all knight moves on the board)<\/p>\n\n\n\n

    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:<\/p>\n\n\n\n

    \"\"<\/figure><\/div>\n\n\n\n

    where\u00a0t\u00a0represents time (incrementing in discrete intervals),\u00a0U(Ni,j<\/sub>)\u00a0is the state of the neuron connecting square\u00a0i\u00a0to square\u00a0j,\u00a0V(Ni,j<\/sub>)\u00a0is the output of the neuron from\u00a0i\u00a0to\u00a0j, and\u00a0G(Ni,j<\/sub>)\u00a0is the set of \u201cneighbors\u201d of the neuron (all neurons that share a vertex with\u00a0Ni,j<\/sub>).<\/p>\n\n\n\n

    Code For Knight’s Tour<\/h3>\n\n\n\n
    \n\n\/\/ Java program for Knight Tour problem\nclass KnightTour {\nstatic int N = 8;\n\n\/* A utility function to check if i,j are\nvalid indexes for N*N chessboard *\/\nstatic boolean isSafe(int x, int y, int sol[][])\n{\n    return (x >= 0 && x < N && y >= 0 && y < N\n            && sol[x][y] == -1);\n}\n\n\/* A utility function to print solution\nmatrix sol[N][N] *\/\nstatic void printSolution(int sol[][])\n{\n    for (int x = 0; x < N; x++) {\n        for (int y = 0; y < N; y++)\n            System.out.print(sol[x][y] + \" \");\n        System.out.println();\n    }\n}\n\n\/* This function solves the Knight Tour problem\nusing Backtracking. This function mainly\nuses solveKTUtil() to solve the problem. It\nreturns false if no complete tour is possible,\notherwise return true and prints the tour.\nPlease note that there may be more than one\nsolutions, this function prints one of the\nfeasible solutions. *\/\nstatic boolean solveKT()\n{\n    int sol[][] = new int[8][8];\n\n    \/* Initialization of solution matrix *\/\n    for (int x = 0; x < N; x++)\n        for (int y = 0; y < N; y++)\n            sol[x][y] = -1;\n\n    \/* xMove[] and yMove[] define next move of Knight.\n    xMove[] is for next value of x coordinate\n    yMove[] is for next value of y coordinate *\/\n    int xMove[] = { 2, 1, -1, -2, -2, -1, 1, 2 };\n    int yMove[] = { 1, 2, 2, 1, -1, -2, -2, -1 };\n\n    \/\/ Since the Knight is initially at the first block\n    sol[0][0] = 0;\n\n    \/* Start from 0,0 and explore all tours using\n    solveKTUtil() *\/\n    if (!solveKTUtil(0, 0, 1, sol, xMove, yMove)) {\n        System.out.println(\"Solution does not exist\");\n        return false;\n    }\n    else\n        printSolution(sol);\n\n    return true;\n}\n\n\/* A recursive utility function to solve Knight\nTour problem *\/\nstatic boolean solveKTUtil(int x, int y, int movei,\n                        int sol[][], int xMove[],\n                        int yMove[])\n{\n    int k, next_x, next_y;\n    if (movei == N * N)\n        return true;\n\n    \/* Try all next moves from the current coordinate\n        x, y *\/\n    for (k = 0; k < 8; k++) {\n        next_x = x + xMove[k];\n        next_y = y + yMove[k];\n        if (isSafe(next_x, next_y, sol)) {\n            sol[next_x][next_y] = movei;\n            if (solveKTUtil(next_x, next_y, movei + 1,\n                            sol, xMove, yMove))\n                return true;\n            else\n                sol[next_x][next_y]\n                    = -1; \/\/ backtracking\n        }\n    }\n\n    return false;\n}\n\n\/* Driver Code *\/\npublic static void main(String args[])\n{\n    \/\/ Function Call\n    solveKT();\n}\n}<\/code><\/pre>\n\n\n\n

    <\/p>\n","protected":false},"excerpt":{"rendered":"
    The\u00a0knight’s tour problem\u00a0is the\u00a0mathematical problem\u00a0of 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\u00a0Hamiltonian path problem\u00a0in\u00a0graph theory. The problem of finding a closed knight’s tour is similarly an instance of the\u00a0Hamiltonian cycle problem. Unlike the general Hamiltonian path problem, the knight’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, … , 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| – 2)! Existence Schwenk\u00a0proved that for any\u00a0m\u00a0\u00d7\u00a0n\u00a0board with\u00a0m\u00a0\u2264\u00a0n, a closed knight’s tour is always possible\u00a0unless\u00a0one 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\u00a0and Conrad\u00a0proved 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 \u00d7 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\u2019s move on the chessboard is represented by a neuron. Therefore, the network basically takes the shape of the knight\u2019s graph over an n\u00d7n 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’s Tour<\/p>\n","protected":false},"author":1,"featured_media":1371,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-1369","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-sneak-peeks"],"featured_image_src":"https:\/\/i0.wp.com\/soulofmathematics.com\/wp-content\/uploads\/2020\/09\/ILAIsmB.gif?fit=335%2C334&ssl=1","blog_images":{"medium":"https:\/\/i0.wp.com\/soulofmathematics.com\/wp-content\/uploads\/2020\/09\/ILAIsmB.gif?fit=300%2C300&ssl=1","large":"https:\/\/i0.wp.com\/soulofmathematics.com\/wp-content\/uploads\/2020\/09\/ILAIsmB.gif?fit=335%2C334&ssl=1"},"ams_acf":[],"yoast_head":"\nThe Knight's Tour - SOUL OF MATHEMATICS<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/soulofmathematics.com\/index.php\/the-knights-tour\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"The Knight's Tour - SOUL OF MATHEMATICS\" \/>\n<meta property=\"og:description\" content=\"The\u00a0knight’s tour problem\u00a0is the\u00a0mathematical problem\u00a0of 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\u00a0Hamiltonian path problem\u00a0in\u00a0graph theory. The problem of finding a closed knight’s tour is similarly an instance of the\u00a0Hamiltonian cycle problem. Unlike the general Hamiltonian path problem, the knight’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, … , 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| – 2)! Existence Schwenk\u00a0proved that for any\u00a0m\u00a0\u00d7\u00a0n\u00a0board with\u00a0m\u00a0\u2264\u00a0n, a closed knight’s tour is always possible\u00a0unless\u00a0one 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\u00a0and Conrad\u00a0proved 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 \u00d7 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\u2019s move on the chessboard is represented by a neuron. Therefore, the network basically takes the shape of the knight\u2019s graph over an n\u00d7n 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’s Tour\" \/>\n<meta property=\"og:url\" content=\"https:\/\/soulofmathematics.com\/index.php\/the-knights-tour\/\" \/>\n<meta property=\"og:site_name\" content=\"SOUL OF MATHEMATICS\" \/>\n<meta property=\"article:published_time\" content=\"2021-05-27T06:14:18+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2021-05-27T06:14:19+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/i0.wp.com\/soulofmathematics.com\/wp-content\/uploads\/2020\/09\/ILAIsmB.gif?fit=335%2C334&ssl=1\" \/>\n\t<meta property=\"og:image:width\" content=\"335\" \/>\n\t<meta property=\"og:image:height\" content=\"334\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/gif\" \/>\n<meta name=\"author\" content=\"Rajarshi Dey\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Rajarshi Dey\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"5 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/soulofmathematics.com\/index.php\/the-knights-tour\/\",\"url\":\"https:\/\/soulofmathematics.com\/index.php\/the-knights-tour\/\",\"name\":\"The Knight's Tour - SOUL OF MATHEMATICS\",\"isPartOf\":{\"@id\":\"https:\/\/soulofmathematics.com\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/soulofmathematics.com\/index.php\/the-knights-tour\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/soulofmathematics.com\/index.php\/the-knights-tour\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/i0.wp.com\/soulofmathematics.com\/wp-content\/uploads\/2020\/09\/ILAIsmB.gif?fit=335%2C334&ssl=1\",\"datePublished\":\"2021-05-27T06:14:18+00:00\",\"dateModified\":\"2021-05-27T06:14:19+00:00\",\"author\":{\"@id\":\"https:\/\/soulofmathematics.com\/#\/schema\/person\/c61ee309ed66bc94ba7a27f6129b945c\"},\"breadcrumb\":{\"@id\":\"https:\/\/soulofmathematics.com\/index.php\/the-knights-tour\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/soulofmathematics.com\/index.php\/the-knights-tour\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/soulofmathematics.com\/index.php\/the-knights-tour\/#primaryimage\",\"url\":\"https:\/\/i0.wp.com\/soulofmathematics.com\/wp-content\/uploads\/2020\/09\/ILAIsmB.gif?fit=335%2C334&ssl=1\",\"contentUrl\":\"https:\/\/i0.wp.com\/soulofmathematics.com\/wp-content\/uploads\/2020\/09\/ILAIsmB.gif?fit=335%2C334&ssl=1\",\"width\":335,\"height\":334,\"caption\":\"Knight's tour\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/soulofmathematics.com\/index.php\/the-knights-tour\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/soulofmathematics.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"The Knight’s Tour\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/soulofmathematics.com\/#website\",\"url\":\"https:\/\/soulofmathematics.com\/\",\"name\":\"SOUL OF MATHEMATICS\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/soulofmathematics.com\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/soulofmathematics.com\/#\/schema\/person\/c61ee309ed66bc94ba7a27f6129b945c\",\"name\":\"Rajarshi Dey\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/soulofmathematics.com\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/14acfcec71e13078f5b322bb6adfd1f6579c091317d0e0077c2311511263a8b0?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/14acfcec71e13078f5b322bb6adfd1f6579c091317d0e0077c2311511263a8b0?s=96&d=mm&r=g\",\"caption\":\"Rajarshi Dey\"},\"sameAs\":[\"http:\/\/soulofmathematics.com\"],\"url\":\"https:\/\/soulofmathematics.com\/index.php\/author\/rajarshidey1729gmail-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"The Knight's Tour - SOUL OF MATHEMATICS","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/soulofmathematics.com\/index.php\/the-knights-tour\/","og_locale":"en_US","og_type":"article","og_title":"The Knight's Tour - SOUL OF MATHEMATICS","og_description":"The\u00a0knight’s tour problem\u00a0is the\u00a0mathematical problem\u00a0of 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\u00a0Hamiltonian path problem\u00a0in\u00a0graph theory. The problem of finding a closed knight’s tour is similarly an instance of the\u00a0Hamiltonian cycle problem. Unlike the general Hamiltonian path problem, the knight’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, … , 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| – 2)! Existence Schwenk\u00a0proved that for any\u00a0m\u00a0\u00d7\u00a0n\u00a0board with\u00a0m\u00a0\u2264\u00a0n, a closed knight’s tour is always possible\u00a0unless\u00a0one 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\u00a0and Conrad\u00a0proved 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 \u00d7 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\u2019s move on the chessboard is represented by a neuron. Therefore, the network basically takes the shape of the knight\u2019s graph over an n\u00d7n 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’s Tour","og_url":"https:\/\/soulofmathematics.com\/index.php\/the-knights-tour\/","og_site_name":"SOUL OF MATHEMATICS","article_published_time":"2021-05-27T06:14:18+00:00","article_modified_time":"2021-05-27T06:14:19+00:00","og_image":[{"width":335,"height":334,"url":"https:\/\/i0.wp.com\/soulofmathematics.com\/wp-content\/uploads\/2020\/09\/ILAIsmB.gif?fit=335%2C334&ssl=1","type":"image\/gif"}],"author":"Rajarshi Dey","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Rajarshi Dey","Est. reading time":"5 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/soulofmathematics.com\/index.php\/the-knights-tour\/","url":"https:\/\/soulofmathematics.com\/index.php\/the-knights-tour\/","name":"The Knight's Tour - SOUL OF MATHEMATICS","isPartOf":{"@id":"https:\/\/soulofmathematics.com\/#website"},"primaryImageOfPage":{"@id":"https:\/\/soulofmathematics.com\/index.php\/the-knights-tour\/#primaryimage"},"image":{"@id":"https:\/\/soulofmathematics.com\/index.php\/the-knights-tour\/#primaryimage"},"thumbnailUrl":"https:\/\/i0.wp.com\/soulofmathematics.com\/wp-content\/uploads\/2020\/09\/ILAIsmB.gif?fit=335%2C334&ssl=1","datePublished":"2021-05-27T06:14:18+00:00","dateModified":"2021-05-27T06:14:19+00:00","author":{"@id":"https:\/\/soulofmathematics.com\/#\/schema\/person\/c61ee309ed66bc94ba7a27f6129b945c"},"breadcrumb":{"@id":"https:\/\/soulofmathematics.com\/index.php\/the-knights-tour\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/soulofmathematics.com\/index.php\/the-knights-tour\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/soulofmathematics.com\/index.php\/the-knights-tour\/#primaryimage","url":"https:\/\/i0.wp.com\/soulofmathematics.com\/wp-content\/uploads\/2020\/09\/ILAIsmB.gif?fit=335%2C334&ssl=1","contentUrl":"https:\/\/i0.wp.com\/soulofmathematics.com\/wp-content\/uploads\/2020\/09\/ILAIsmB.gif?fit=335%2C334&ssl=1","width":335,"height":334,"caption":"Knight's tour"},{"@type":"BreadcrumbList","@id":"https:\/\/soulofmathematics.com\/index.php\/the-knights-tour\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/soulofmathematics.com\/"},{"@type":"ListItem","position":2,"name":"The Knight’s Tour"}]},{"@type":"WebSite","@id":"https:\/\/soulofmathematics.com\/#website","url":"https:\/\/soulofmathematics.com\/","name":"SOUL OF MATHEMATICS","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/soulofmathematics.com\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/soulofmathematics.com\/#\/schema\/person\/c61ee309ed66bc94ba7a27f6129b945c","name":"Rajarshi Dey","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/soulofmathematics.com\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/14acfcec71e13078f5b322bb6adfd1f6579c091317d0e0077c2311511263a8b0?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/14acfcec71e13078f5b322bb6adfd1f6579c091317d0e0077c2311511263a8b0?s=96&d=mm&r=g","caption":"Rajarshi Dey"},"sameAs":["http:\/\/soulofmathematics.com"],"url":"https:\/\/soulofmathematics.com\/index.php\/author\/rajarshidey1729gmail-com\/"}]}},"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"https:\/\/i0.wp.com\/soulofmathematics.com\/wp-content\/uploads\/2020\/09\/ILAIsmB.gif?fit=335%2C334&ssl=1","jetpack-related-posts":[],"jetpack_shortlink":"https:\/\/wp.me\/pcfs4y-m5","_links":{"self":[{"href":"https:\/\/soulofmathematics.com\/index.php\/wp-json\/wp\/v2\/posts\/1369","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/soulofmathematics.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/soulofmathematics.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/soulofmathematics.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/soulofmathematics.com\/index.php\/wp-json\/wp\/v2\/comments?post=1369"}],"version-history":[{"count":13,"href":"https:\/\/soulofmathematics.com\/index.php\/wp-json\/wp\/v2\/posts\/1369\/revisions"}],"predecessor-version":[{"id":2586,"href":"https:\/\/soulofmathematics.com\/index.php\/wp-json\/wp\/v2\/posts\/1369\/revisions\/2586"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/soulofmathematics.com\/index.php\/wp-json\/wp\/v2\/media\/1371"}],"wp:attachment":[{"href":"https:\/\/soulofmathematics.com\/index.php\/wp-json\/wp\/v2\/media?parent=1369"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/soulofmathematics.com\/index.php\/wp-json\/wp\/v2\/categories?post=1369"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/soulofmathematics.com\/index.php\/wp-json\/wp\/v2\/tags?post=1369"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}