A variant of the Knight's tour problem The Next CEO of Stack Overflowbinomial congruence $sum_i=1^fracp-12binom2iiequiv 0~or (-2)pmod p$How many knight's tours are there?Existence of Knight's Tours on an ordinary chessboardOdd-length cycles on the knight's graphFor which chess boards do solutions exist for this generalised Knight's Tour problem?Chess King Tour 8x8 problemA closed Knight's Tour does not exist on some chessboardsChess rook tour of 64 movesKnight's tour problem existance proofLooking for a challenging task or variant related to the knight's tour problemProperties of a general knight in the knight's tour problem.

How do I transpose the first and deepest levels of an arbitrarily nested array?

How do I reset passwords on multiple websites easily?

Can we say or write : "No, it'sn't"?

Which kind of appliances can one connect to electric sockets located in an airplane's toilet?

Why didn't Khan get resurrected in the Genesis Explosion?

What connection does MS Office have to Netscape Navigator?

Example of a Mathematician/Physicist whose Other Publications during their PhD eclipsed their PhD Thesis

Why don't programming languages automatically manage the synchronous/asynchronous problem?

Is there a difference between "Fahrstuhl" and "Aufzug"

Would a completely good Muggle be able to use a wand?

sp_blitzCache results Memory grants

Won the lottery - how do I keep the money?

Can you replace a racial trait cantrip when leveling up?

Contours of a clandestine nature

If the heap is zero-initialized for security, then why is the stack merely uninitialized?

Indicator light circuit

Multiple labels for a single equation

Plot of histogram similar to output from @risk

Why has the US not been more assertive in confronting Russia in recent years?

Is it my responsibility to learn a new technology in my own time my employer wants to implement?

How do I make a variable always equal to the result of some calculations?

Preparing Indesign booklet with .psd graphics for print

If a black hole is created from light, can this black hole then move at speed of light?

How did the Bene Gesserit know how to make a Kwisatz Haderach?



A variant of the Knight's tour problem



The Next CEO of Stack Overflowbinomial congruence $sum_i=1^fracp-12binom2iiequiv 0~or (-2)pmod p$How many knight's tours are there?Existence of Knight's Tours on an ordinary chessboardOdd-length cycles on the knight's graphFor which chess boards do solutions exist for this generalised Knight's Tour problem?Chess King Tour 8x8 problemA closed Knight's Tour does not exist on some chessboardsChess rook tour of 64 movesKnight's tour problem existance proofLooking for a challenging task or variant related to the knight's tour problemProperties of a general knight in the knight's tour problem.










17












$begingroup$


The knight's tour problem is a famous problem in chess and computer science which asks the following question: can we move the knight on an $n times n$ chessboard such that it visits every square exactly once? The answer is yes iff $ngeq5$. Additionally, there are algorithms which can solve it in $O(n^2)$ time.



I have two variations of it discussed below.



Fix an $n times n$ chessboard. In this variant, instead of one knight we have $m$ knights. These knights take turns moving (ie., one knight moves, after that another one, once all of them have moved, the first one moves again and the cycle repeats itself).



What is the largest $m$ such that for some initial starting position, each knight can tour the board (as described in the first paragraph) without threatening any other knight? In other words, there is no "instance" of the chessboard in which one knight may capture another knight (e.g., knight $A$ cannot be, for example, two cells right and one cell up from another knight $B$ when it is his turn). Note that there is obviously an upper bound on $m$ (e.g., $n^2$).



In essence, I'm looking for a function $f:mathbbN_geq 5 to mathbbN$ which assigns to each $n$ the largest possible $m$.



My second variation is exactly the same, except now there are no restrictions on the turns. After one knight moves, any knight can move, including the one that has moved prior. I do not know how these variations relate to each other; perhaps they are equivalent.



Also, as a function of $n$ what would the time complexity of an optimal algorithm be? Can either of these variants be solved in polynomial time?










share|cite|improve this question











$endgroup$
















    17












    $begingroup$


    The knight's tour problem is a famous problem in chess and computer science which asks the following question: can we move the knight on an $n times n$ chessboard such that it visits every square exactly once? The answer is yes iff $ngeq5$. Additionally, there are algorithms which can solve it in $O(n^2)$ time.



    I have two variations of it discussed below.



    Fix an $n times n$ chessboard. In this variant, instead of one knight we have $m$ knights. These knights take turns moving (ie., one knight moves, after that another one, once all of them have moved, the first one moves again and the cycle repeats itself).



    What is the largest $m$ such that for some initial starting position, each knight can tour the board (as described in the first paragraph) without threatening any other knight? In other words, there is no "instance" of the chessboard in which one knight may capture another knight (e.g., knight $A$ cannot be, for example, two cells right and one cell up from another knight $B$ when it is his turn). Note that there is obviously an upper bound on $m$ (e.g., $n^2$).



    In essence, I'm looking for a function $f:mathbbN_geq 5 to mathbbN$ which assigns to each $n$ the largest possible $m$.



    My second variation is exactly the same, except now there are no restrictions on the turns. After one knight moves, any knight can move, including the one that has moved prior. I do not know how these variations relate to each other; perhaps they are equivalent.



    Also, as a function of $n$ what would the time complexity of an optimal algorithm be? Can either of these variants be solved in polynomial time?










    share|cite|improve this question











    $endgroup$














      17












      17








      17


      4



      $begingroup$


      The knight's tour problem is a famous problem in chess and computer science which asks the following question: can we move the knight on an $n times n$ chessboard such that it visits every square exactly once? The answer is yes iff $ngeq5$. Additionally, there are algorithms which can solve it in $O(n^2)$ time.



      I have two variations of it discussed below.



      Fix an $n times n$ chessboard. In this variant, instead of one knight we have $m$ knights. These knights take turns moving (ie., one knight moves, after that another one, once all of them have moved, the first one moves again and the cycle repeats itself).



      What is the largest $m$ such that for some initial starting position, each knight can tour the board (as described in the first paragraph) without threatening any other knight? In other words, there is no "instance" of the chessboard in which one knight may capture another knight (e.g., knight $A$ cannot be, for example, two cells right and one cell up from another knight $B$ when it is his turn). Note that there is obviously an upper bound on $m$ (e.g., $n^2$).



      In essence, I'm looking for a function $f:mathbbN_geq 5 to mathbbN$ which assigns to each $n$ the largest possible $m$.



      My second variation is exactly the same, except now there are no restrictions on the turns. After one knight moves, any knight can move, including the one that has moved prior. I do not know how these variations relate to each other; perhaps they are equivalent.



      Also, as a function of $n$ what would the time complexity of an optimal algorithm be? Can either of these variants be solved in polynomial time?










      share|cite|improve this question











      $endgroup$




      The knight's tour problem is a famous problem in chess and computer science which asks the following question: can we move the knight on an $n times n$ chessboard such that it visits every square exactly once? The answer is yes iff $ngeq5$. Additionally, there are algorithms which can solve it in $O(n^2)$ time.



      I have two variations of it discussed below.



      Fix an $n times n$ chessboard. In this variant, instead of one knight we have $m$ knights. These knights take turns moving (ie., one knight moves, after that another one, once all of them have moved, the first one moves again and the cycle repeats itself).



      What is the largest $m$ such that for some initial starting position, each knight can tour the board (as described in the first paragraph) without threatening any other knight? In other words, there is no "instance" of the chessboard in which one knight may capture another knight (e.g., knight $A$ cannot be, for example, two cells right and one cell up from another knight $B$ when it is his turn). Note that there is obviously an upper bound on $m$ (e.g., $n^2$).



      In essence, I'm looking for a function $f:mathbbN_geq 5 to mathbbN$ which assigns to each $n$ the largest possible $m$.



      My second variation is exactly the same, except now there are no restrictions on the turns. After one knight moves, any knight can move, including the one that has moved prior. I do not know how these variations relate to each other; perhaps they are equivalent.



      Also, as a function of $n$ what would the time complexity of an optimal algorithm be? Can either of these variants be solved in polynomial time?







      discrete-mathematics graph-theory chessboard knight-tours






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Jan 3 '17 at 3:33







      MathematicsStudent1122

















      asked Dec 25 '16 at 10:28









      MathematicsStudent1122MathematicsStudent1122

      9,00332668




      9,00332668




















          2 Answers
          2






          active

          oldest

          votes


















          0












          $begingroup$

          For even $n$, $n ge 6$, the answer is $m = n^2 - 1$ for both questions and the time is $O(n^2)$.



          Obviously $m le n^2 - 1$ is an upper bound, because at least one cell should be initially free. Let us see why it is reachable.



          It is possible to construct a closed (cyclic) tour for one knight in the time of $O(n^2)$. The tour has additional property of symmetry, and the algo has property of good parallelization (i. e. it takes $O(1)$ on $n^2$ processors).



          Let $C = v_1 v_2 ldots v_n v_1$ be sequence of cells in such closed tour. Then we place the first knight into $v_n,$ the second one into $v_n - 1$, and so on, placing the last one, $m$th knight, into $v_2$. At the first turn the first knight moves to $v_1$, the second one moves to $v_n$, and so on, the last one moves to $v_3$. Then the first one moves to $v_2$ and so on and so on. Every knight walks through the entire tour.



          For odd $n$ there is also a more tight upper bound: $m le fracn^2 + 12$. It follows from a note that our graph is bipartite and has an odd order, so we should start every tour in the bigger part of graph (of $fracn^2 + 12$ cells). For the first question the upper bound is even less by $1$, because after the first turn all knights should be in the smaller part of graph (of $fracn^2 - 12$ cells).



          May be some time later I'll investigate odd case more precisely.






          share|cite|improve this answer









          $endgroup$












          • $begingroup$
            This is clearly wrong. If $m=n^2 - 1$, each square except one will always be occupied by a knight. Some knights will obviously threaten each other. I think you misunderstood the problem.
            $endgroup$
            – MathematicsStudent1122
            Dec 31 '16 at 14:18











          • $begingroup$
            @MathematicsStudent1122 to be honest, Symlic answered the question in the exact way I interpreted it. You might want to reword your question a bit. I took "threaten each other" to mean that, if we label all of the knights $K_1, K_2, K_3,dots ,K_n$ then we start by moving $K_1$, which is "threatening" the other knights if it has no square to move to that doesn't attack another knight. Once we move $K_1$ we then focus on $K_2$, then $K_3$, and so forth, looping back to $K_1$ after $K_n$ until a full tour is made by all Knights. Symlic's answers suffices under this interpretation.
            $endgroup$
            – Brevan Ellefsen
            Jan 3 '17 at 2:27











          • $begingroup$
            @BrevanEllefsen Threatening doesn't mean that each square a knight can move to is occupied. Only one. In other words, if we enumerate each position on the board $x_1, x_2, x_3..x_n$ there is no position such that two knights are in cells in which one can capture the other (e.g., a knight $K_j$ cannot be in a cell two to the right and one up from some other knight $K_i$). No, I won't reword it because $13$ other people aren't confused. Your interpretation is just wrong. I think this is straightforward.
            $endgroup$
            – MathematicsStudent1122
            Jan 3 '17 at 2:46











          • $begingroup$
            @MathematicsStudent1122 OK. You can do what you want. Let it be noted however, that the only answer you have interpreted the question the way I did. Moreover, clarity is never a bad thing. Moreover, upvotes are not equivalent to mutual understanding of all parts of a question - they simply show an interest in seeing answers to said question (I have often seen posts upvoted with 10+ votes that did not deserve a single vote). That being said, my comment wasn't meant to attack you in any way... I meant it to help you get an answer. The more clear a question, the more likely an answer.
            $endgroup$
            – Brevan Ellefsen
            Jan 3 '17 at 2:50










          • $begingroup$
            Plus, editing a question puts it in the recent question feed and you would have an excuse to do that were you to add the details you put in your comment. I repeat what my point is though - (potential) redundancy for the purpose of clarity ought to be encouraged
            $endgroup$
            – Brevan Ellefsen
            Jan 3 '17 at 2:52


















          0












          $begingroup$

          Only a partial hint/answer here, consider how many squares, attack how many others. In an N by N there are $(N-4)^2$ squares in which a knight can attack 8 squares (some of which are in that same block). there are a further $4N-4$ that attack 4 places, 4 that attack 2, and 4(N-4) that attack 6.






          share|cite|improve this answer









          $endgroup$













            Your Answer





            StackExchange.ifUsing("editor", function ()
            return StackExchange.using("mathjaxEditing", function ()
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
            );
            );
            , "mathjax-editing");

            StackExchange.ready(function()
            var channelOptions =
            tags: "".split(" "),
            id: "69"
            ;
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function()
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled)
            StackExchange.using("snippets", function()
            createEditor();
            );

            else
            createEditor();

            );

            function createEditor()
            StackExchange.prepareEditor(
            heartbeatType: 'answer',
            autoActivateHeartbeat: false,
            convertImagesToLinks: true,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: 10,
            bindNavPrevention: true,
            postfix: "",
            imageUploader:
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            ,
            noCode: true, onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            );



            );













            draft saved

            draft discarded


















            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2071380%2fa-variant-of-the-knights-tour-problem%23new-answer', 'question_page');

            );

            Post as a guest















            Required, but never shown

























            2 Answers
            2






            active

            oldest

            votes








            2 Answers
            2






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            0












            $begingroup$

            For even $n$, $n ge 6$, the answer is $m = n^2 - 1$ for both questions and the time is $O(n^2)$.



            Obviously $m le n^2 - 1$ is an upper bound, because at least one cell should be initially free. Let us see why it is reachable.



            It is possible to construct a closed (cyclic) tour for one knight in the time of $O(n^2)$. The tour has additional property of symmetry, and the algo has property of good parallelization (i. e. it takes $O(1)$ on $n^2$ processors).



            Let $C = v_1 v_2 ldots v_n v_1$ be sequence of cells in such closed tour. Then we place the first knight into $v_n,$ the second one into $v_n - 1$, and so on, placing the last one, $m$th knight, into $v_2$. At the first turn the first knight moves to $v_1$, the second one moves to $v_n$, and so on, the last one moves to $v_3$. Then the first one moves to $v_2$ and so on and so on. Every knight walks through the entire tour.



            For odd $n$ there is also a more tight upper bound: $m le fracn^2 + 12$. It follows from a note that our graph is bipartite and has an odd order, so we should start every tour in the bigger part of graph (of $fracn^2 + 12$ cells). For the first question the upper bound is even less by $1$, because after the first turn all knights should be in the smaller part of graph (of $fracn^2 - 12$ cells).



            May be some time later I'll investigate odd case more precisely.






            share|cite|improve this answer









            $endgroup$












            • $begingroup$
              This is clearly wrong. If $m=n^2 - 1$, each square except one will always be occupied by a knight. Some knights will obviously threaten each other. I think you misunderstood the problem.
              $endgroup$
              – MathematicsStudent1122
              Dec 31 '16 at 14:18











            • $begingroup$
              @MathematicsStudent1122 to be honest, Symlic answered the question in the exact way I interpreted it. You might want to reword your question a bit. I took "threaten each other" to mean that, if we label all of the knights $K_1, K_2, K_3,dots ,K_n$ then we start by moving $K_1$, which is "threatening" the other knights if it has no square to move to that doesn't attack another knight. Once we move $K_1$ we then focus on $K_2$, then $K_3$, and so forth, looping back to $K_1$ after $K_n$ until a full tour is made by all Knights. Symlic's answers suffices under this interpretation.
              $endgroup$
              – Brevan Ellefsen
              Jan 3 '17 at 2:27











            • $begingroup$
              @BrevanEllefsen Threatening doesn't mean that each square a knight can move to is occupied. Only one. In other words, if we enumerate each position on the board $x_1, x_2, x_3..x_n$ there is no position such that two knights are in cells in which one can capture the other (e.g., a knight $K_j$ cannot be in a cell two to the right and one up from some other knight $K_i$). No, I won't reword it because $13$ other people aren't confused. Your interpretation is just wrong. I think this is straightforward.
              $endgroup$
              – MathematicsStudent1122
              Jan 3 '17 at 2:46











            • $begingroup$
              @MathematicsStudent1122 OK. You can do what you want. Let it be noted however, that the only answer you have interpreted the question the way I did. Moreover, clarity is never a bad thing. Moreover, upvotes are not equivalent to mutual understanding of all parts of a question - they simply show an interest in seeing answers to said question (I have often seen posts upvoted with 10+ votes that did not deserve a single vote). That being said, my comment wasn't meant to attack you in any way... I meant it to help you get an answer. The more clear a question, the more likely an answer.
              $endgroup$
              – Brevan Ellefsen
              Jan 3 '17 at 2:50










            • $begingroup$
              Plus, editing a question puts it in the recent question feed and you would have an excuse to do that were you to add the details you put in your comment. I repeat what my point is though - (potential) redundancy for the purpose of clarity ought to be encouraged
              $endgroup$
              – Brevan Ellefsen
              Jan 3 '17 at 2:52















            0












            $begingroup$

            For even $n$, $n ge 6$, the answer is $m = n^2 - 1$ for both questions and the time is $O(n^2)$.



            Obviously $m le n^2 - 1$ is an upper bound, because at least one cell should be initially free. Let us see why it is reachable.



            It is possible to construct a closed (cyclic) tour for one knight in the time of $O(n^2)$. The tour has additional property of symmetry, and the algo has property of good parallelization (i. e. it takes $O(1)$ on $n^2$ processors).



            Let $C = v_1 v_2 ldots v_n v_1$ be sequence of cells in such closed tour. Then we place the first knight into $v_n,$ the second one into $v_n - 1$, and so on, placing the last one, $m$th knight, into $v_2$. At the first turn the first knight moves to $v_1$, the second one moves to $v_n$, and so on, the last one moves to $v_3$. Then the first one moves to $v_2$ and so on and so on. Every knight walks through the entire tour.



            For odd $n$ there is also a more tight upper bound: $m le fracn^2 + 12$. It follows from a note that our graph is bipartite and has an odd order, so we should start every tour in the bigger part of graph (of $fracn^2 + 12$ cells). For the first question the upper bound is even less by $1$, because after the first turn all knights should be in the smaller part of graph (of $fracn^2 - 12$ cells).



            May be some time later I'll investigate odd case more precisely.






            share|cite|improve this answer









            $endgroup$












            • $begingroup$
              This is clearly wrong. If $m=n^2 - 1$, each square except one will always be occupied by a knight. Some knights will obviously threaten each other. I think you misunderstood the problem.
              $endgroup$
              – MathematicsStudent1122
              Dec 31 '16 at 14:18











            • $begingroup$
              @MathematicsStudent1122 to be honest, Symlic answered the question in the exact way I interpreted it. You might want to reword your question a bit. I took "threaten each other" to mean that, if we label all of the knights $K_1, K_2, K_3,dots ,K_n$ then we start by moving $K_1$, which is "threatening" the other knights if it has no square to move to that doesn't attack another knight. Once we move $K_1$ we then focus on $K_2$, then $K_3$, and so forth, looping back to $K_1$ after $K_n$ until a full tour is made by all Knights. Symlic's answers suffices under this interpretation.
              $endgroup$
              – Brevan Ellefsen
              Jan 3 '17 at 2:27











            • $begingroup$
              @BrevanEllefsen Threatening doesn't mean that each square a knight can move to is occupied. Only one. In other words, if we enumerate each position on the board $x_1, x_2, x_3..x_n$ there is no position such that two knights are in cells in which one can capture the other (e.g., a knight $K_j$ cannot be in a cell two to the right and one up from some other knight $K_i$). No, I won't reword it because $13$ other people aren't confused. Your interpretation is just wrong. I think this is straightforward.
              $endgroup$
              – MathematicsStudent1122
              Jan 3 '17 at 2:46











            • $begingroup$
              @MathematicsStudent1122 OK. You can do what you want. Let it be noted however, that the only answer you have interpreted the question the way I did. Moreover, clarity is never a bad thing. Moreover, upvotes are not equivalent to mutual understanding of all parts of a question - they simply show an interest in seeing answers to said question (I have often seen posts upvoted with 10+ votes that did not deserve a single vote). That being said, my comment wasn't meant to attack you in any way... I meant it to help you get an answer. The more clear a question, the more likely an answer.
              $endgroup$
              – Brevan Ellefsen
              Jan 3 '17 at 2:50










            • $begingroup$
              Plus, editing a question puts it in the recent question feed and you would have an excuse to do that were you to add the details you put in your comment. I repeat what my point is though - (potential) redundancy for the purpose of clarity ought to be encouraged
              $endgroup$
              – Brevan Ellefsen
              Jan 3 '17 at 2:52













            0












            0








            0





            $begingroup$

            For even $n$, $n ge 6$, the answer is $m = n^2 - 1$ for both questions and the time is $O(n^2)$.



            Obviously $m le n^2 - 1$ is an upper bound, because at least one cell should be initially free. Let us see why it is reachable.



            It is possible to construct a closed (cyclic) tour for one knight in the time of $O(n^2)$. The tour has additional property of symmetry, and the algo has property of good parallelization (i. e. it takes $O(1)$ on $n^2$ processors).



            Let $C = v_1 v_2 ldots v_n v_1$ be sequence of cells in such closed tour. Then we place the first knight into $v_n,$ the second one into $v_n - 1$, and so on, placing the last one, $m$th knight, into $v_2$. At the first turn the first knight moves to $v_1$, the second one moves to $v_n$, and so on, the last one moves to $v_3$. Then the first one moves to $v_2$ and so on and so on. Every knight walks through the entire tour.



            For odd $n$ there is also a more tight upper bound: $m le fracn^2 + 12$. It follows from a note that our graph is bipartite and has an odd order, so we should start every tour in the bigger part of graph (of $fracn^2 + 12$ cells). For the first question the upper bound is even less by $1$, because after the first turn all knights should be in the smaller part of graph (of $fracn^2 - 12$ cells).



            May be some time later I'll investigate odd case more precisely.






            share|cite|improve this answer









            $endgroup$



            For even $n$, $n ge 6$, the answer is $m = n^2 - 1$ for both questions and the time is $O(n^2)$.



            Obviously $m le n^2 - 1$ is an upper bound, because at least one cell should be initially free. Let us see why it is reachable.



            It is possible to construct a closed (cyclic) tour for one knight in the time of $O(n^2)$. The tour has additional property of symmetry, and the algo has property of good parallelization (i. e. it takes $O(1)$ on $n^2$ processors).



            Let $C = v_1 v_2 ldots v_n v_1$ be sequence of cells in such closed tour. Then we place the first knight into $v_n,$ the second one into $v_n - 1$, and so on, placing the last one, $m$th knight, into $v_2$. At the first turn the first knight moves to $v_1$, the second one moves to $v_n$, and so on, the last one moves to $v_3$. Then the first one moves to $v_2$ and so on and so on. Every knight walks through the entire tour.



            For odd $n$ there is also a more tight upper bound: $m le fracn^2 + 12$. It follows from a note that our graph is bipartite and has an odd order, so we should start every tour in the bigger part of graph (of $fracn^2 + 12$ cells). For the first question the upper bound is even less by $1$, because after the first turn all knights should be in the smaller part of graph (of $fracn^2 - 12$ cells).



            May be some time later I'll investigate odd case more precisely.







            share|cite|improve this answer












            share|cite|improve this answer



            share|cite|improve this answer










            answered Dec 31 '16 at 14:08









            SmylicSmylic

            4,54921225




            4,54921225











            • $begingroup$
              This is clearly wrong. If $m=n^2 - 1$, each square except one will always be occupied by a knight. Some knights will obviously threaten each other. I think you misunderstood the problem.
              $endgroup$
              – MathematicsStudent1122
              Dec 31 '16 at 14:18











            • $begingroup$
              @MathematicsStudent1122 to be honest, Symlic answered the question in the exact way I interpreted it. You might want to reword your question a bit. I took "threaten each other" to mean that, if we label all of the knights $K_1, K_2, K_3,dots ,K_n$ then we start by moving $K_1$, which is "threatening" the other knights if it has no square to move to that doesn't attack another knight. Once we move $K_1$ we then focus on $K_2$, then $K_3$, and so forth, looping back to $K_1$ after $K_n$ until a full tour is made by all Knights. Symlic's answers suffices under this interpretation.
              $endgroup$
              – Brevan Ellefsen
              Jan 3 '17 at 2:27











            • $begingroup$
              @BrevanEllefsen Threatening doesn't mean that each square a knight can move to is occupied. Only one. In other words, if we enumerate each position on the board $x_1, x_2, x_3..x_n$ there is no position such that two knights are in cells in which one can capture the other (e.g., a knight $K_j$ cannot be in a cell two to the right and one up from some other knight $K_i$). No, I won't reword it because $13$ other people aren't confused. Your interpretation is just wrong. I think this is straightforward.
              $endgroup$
              – MathematicsStudent1122
              Jan 3 '17 at 2:46











            • $begingroup$
              @MathematicsStudent1122 OK. You can do what you want. Let it be noted however, that the only answer you have interpreted the question the way I did. Moreover, clarity is never a bad thing. Moreover, upvotes are not equivalent to mutual understanding of all parts of a question - they simply show an interest in seeing answers to said question (I have often seen posts upvoted with 10+ votes that did not deserve a single vote). That being said, my comment wasn't meant to attack you in any way... I meant it to help you get an answer. The more clear a question, the more likely an answer.
              $endgroup$
              – Brevan Ellefsen
              Jan 3 '17 at 2:50










            • $begingroup$
              Plus, editing a question puts it in the recent question feed and you would have an excuse to do that were you to add the details you put in your comment. I repeat what my point is though - (potential) redundancy for the purpose of clarity ought to be encouraged
              $endgroup$
              – Brevan Ellefsen
              Jan 3 '17 at 2:52
















            • $begingroup$
              This is clearly wrong. If $m=n^2 - 1$, each square except one will always be occupied by a knight. Some knights will obviously threaten each other. I think you misunderstood the problem.
              $endgroup$
              – MathematicsStudent1122
              Dec 31 '16 at 14:18











            • $begingroup$
              @MathematicsStudent1122 to be honest, Symlic answered the question in the exact way I interpreted it. You might want to reword your question a bit. I took "threaten each other" to mean that, if we label all of the knights $K_1, K_2, K_3,dots ,K_n$ then we start by moving $K_1$, which is "threatening" the other knights if it has no square to move to that doesn't attack another knight. Once we move $K_1$ we then focus on $K_2$, then $K_3$, and so forth, looping back to $K_1$ after $K_n$ until a full tour is made by all Knights. Symlic's answers suffices under this interpretation.
              $endgroup$
              – Brevan Ellefsen
              Jan 3 '17 at 2:27











            • $begingroup$
              @BrevanEllefsen Threatening doesn't mean that each square a knight can move to is occupied. Only one. In other words, if we enumerate each position on the board $x_1, x_2, x_3..x_n$ there is no position such that two knights are in cells in which one can capture the other (e.g., a knight $K_j$ cannot be in a cell two to the right and one up from some other knight $K_i$). No, I won't reword it because $13$ other people aren't confused. Your interpretation is just wrong. I think this is straightforward.
              $endgroup$
              – MathematicsStudent1122
              Jan 3 '17 at 2:46











            • $begingroup$
              @MathematicsStudent1122 OK. You can do what you want. Let it be noted however, that the only answer you have interpreted the question the way I did. Moreover, clarity is never a bad thing. Moreover, upvotes are not equivalent to mutual understanding of all parts of a question - they simply show an interest in seeing answers to said question (I have often seen posts upvoted with 10+ votes that did not deserve a single vote). That being said, my comment wasn't meant to attack you in any way... I meant it to help you get an answer. The more clear a question, the more likely an answer.
              $endgroup$
              – Brevan Ellefsen
              Jan 3 '17 at 2:50










            • $begingroup$
              Plus, editing a question puts it in the recent question feed and you would have an excuse to do that were you to add the details you put in your comment. I repeat what my point is though - (potential) redundancy for the purpose of clarity ought to be encouraged
              $endgroup$
              – Brevan Ellefsen
              Jan 3 '17 at 2:52















            $begingroup$
            This is clearly wrong. If $m=n^2 - 1$, each square except one will always be occupied by a knight. Some knights will obviously threaten each other. I think you misunderstood the problem.
            $endgroup$
            – MathematicsStudent1122
            Dec 31 '16 at 14:18





            $begingroup$
            This is clearly wrong. If $m=n^2 - 1$, each square except one will always be occupied by a knight. Some knights will obviously threaten each other. I think you misunderstood the problem.
            $endgroup$
            – MathematicsStudent1122
            Dec 31 '16 at 14:18













            $begingroup$
            @MathematicsStudent1122 to be honest, Symlic answered the question in the exact way I interpreted it. You might want to reword your question a bit. I took "threaten each other" to mean that, if we label all of the knights $K_1, K_2, K_3,dots ,K_n$ then we start by moving $K_1$, which is "threatening" the other knights if it has no square to move to that doesn't attack another knight. Once we move $K_1$ we then focus on $K_2$, then $K_3$, and so forth, looping back to $K_1$ after $K_n$ until a full tour is made by all Knights. Symlic's answers suffices under this interpretation.
            $endgroup$
            – Brevan Ellefsen
            Jan 3 '17 at 2:27





            $begingroup$
            @MathematicsStudent1122 to be honest, Symlic answered the question in the exact way I interpreted it. You might want to reword your question a bit. I took "threaten each other" to mean that, if we label all of the knights $K_1, K_2, K_3,dots ,K_n$ then we start by moving $K_1$, which is "threatening" the other knights if it has no square to move to that doesn't attack another knight. Once we move $K_1$ we then focus on $K_2$, then $K_3$, and so forth, looping back to $K_1$ after $K_n$ until a full tour is made by all Knights. Symlic's answers suffices under this interpretation.
            $endgroup$
            – Brevan Ellefsen
            Jan 3 '17 at 2:27













            $begingroup$
            @BrevanEllefsen Threatening doesn't mean that each square a knight can move to is occupied. Only one. In other words, if we enumerate each position on the board $x_1, x_2, x_3..x_n$ there is no position such that two knights are in cells in which one can capture the other (e.g., a knight $K_j$ cannot be in a cell two to the right and one up from some other knight $K_i$). No, I won't reword it because $13$ other people aren't confused. Your interpretation is just wrong. I think this is straightforward.
            $endgroup$
            – MathematicsStudent1122
            Jan 3 '17 at 2:46





            $begingroup$
            @BrevanEllefsen Threatening doesn't mean that each square a knight can move to is occupied. Only one. In other words, if we enumerate each position on the board $x_1, x_2, x_3..x_n$ there is no position such that two knights are in cells in which one can capture the other (e.g., a knight $K_j$ cannot be in a cell two to the right and one up from some other knight $K_i$). No, I won't reword it because $13$ other people aren't confused. Your interpretation is just wrong. I think this is straightforward.
            $endgroup$
            – MathematicsStudent1122
            Jan 3 '17 at 2:46













            $begingroup$
            @MathematicsStudent1122 OK. You can do what you want. Let it be noted however, that the only answer you have interpreted the question the way I did. Moreover, clarity is never a bad thing. Moreover, upvotes are not equivalent to mutual understanding of all parts of a question - they simply show an interest in seeing answers to said question (I have often seen posts upvoted with 10+ votes that did not deserve a single vote). That being said, my comment wasn't meant to attack you in any way... I meant it to help you get an answer. The more clear a question, the more likely an answer.
            $endgroup$
            – Brevan Ellefsen
            Jan 3 '17 at 2:50




            $begingroup$
            @MathematicsStudent1122 OK. You can do what you want. Let it be noted however, that the only answer you have interpreted the question the way I did. Moreover, clarity is never a bad thing. Moreover, upvotes are not equivalent to mutual understanding of all parts of a question - they simply show an interest in seeing answers to said question (I have often seen posts upvoted with 10+ votes that did not deserve a single vote). That being said, my comment wasn't meant to attack you in any way... I meant it to help you get an answer. The more clear a question, the more likely an answer.
            $endgroup$
            – Brevan Ellefsen
            Jan 3 '17 at 2:50












            $begingroup$
            Plus, editing a question puts it in the recent question feed and you would have an excuse to do that were you to add the details you put in your comment. I repeat what my point is though - (potential) redundancy for the purpose of clarity ought to be encouraged
            $endgroup$
            – Brevan Ellefsen
            Jan 3 '17 at 2:52




            $begingroup$
            Plus, editing a question puts it in the recent question feed and you would have an excuse to do that were you to add the details you put in your comment. I repeat what my point is though - (potential) redundancy for the purpose of clarity ought to be encouraged
            $endgroup$
            – Brevan Ellefsen
            Jan 3 '17 at 2:52











            0












            $begingroup$

            Only a partial hint/answer here, consider how many squares, attack how many others. In an N by N there are $(N-4)^2$ squares in which a knight can attack 8 squares (some of which are in that same block). there are a further $4N-4$ that attack 4 places, 4 that attack 2, and 4(N-4) that attack 6.






            share|cite|improve this answer









            $endgroup$

















              0












              $begingroup$

              Only a partial hint/answer here, consider how many squares, attack how many others. In an N by N there are $(N-4)^2$ squares in which a knight can attack 8 squares (some of which are in that same block). there are a further $4N-4$ that attack 4 places, 4 that attack 2, and 4(N-4) that attack 6.






              share|cite|improve this answer









              $endgroup$















                0












                0








                0





                $begingroup$

                Only a partial hint/answer here, consider how many squares, attack how many others. In an N by N there are $(N-4)^2$ squares in which a knight can attack 8 squares (some of which are in that same block). there are a further $4N-4$ that attack 4 places, 4 that attack 2, and 4(N-4) that attack 6.






                share|cite|improve this answer









                $endgroup$



                Only a partial hint/answer here, consider how many squares, attack how many others. In an N by N there are $(N-4)^2$ squares in which a knight can attack 8 squares (some of which are in that same block). there are a further $4N-4$ that attack 4 places, 4 that attack 2, and 4(N-4) that attack 6.







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                answered Jun 28 '17 at 2:36







                user451844


































                    draft saved

                    draft discarded
















































                    Thanks for contributing an answer to Mathematics Stack Exchange!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid


                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.

                    Use MathJax to format equations. MathJax reference.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function ()
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2071380%2fa-variant-of-the-knights-tour-problem%23new-answer', 'question_page');

                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    Popular posts from this blog

                    How should I support this large drywall patch? Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?How do I cover large gaps in drywall?How do I keep drywall around a patch from crumbling?Can I glue a second layer of drywall?How to patch long strip on drywall?Large drywall patch: how to avoid bulging seams?Drywall Mesh Patch vs. Bulge? To remove or not to remove?How to fix this drywall job?Prep drywall before backsplashWhat's the best way to fix this horrible drywall patch job?Drywall patching using 3M Patch Plus Primer

                    random experiment with two different functions on unit interval Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern)Random variable and probability space notionsRandom Walk with EdgesFinding functions where the increase over a random interval is Poisson distributedNumber of days until dayCan an observed event in fact be of zero probability?Unit random processmodels of coins and uniform distributionHow to get the number of successes given $n$ trials , probability $P$ and a random variable $X$Absorbing Markov chain in a computer. Is “almost every” turned into always convergence in computer executions?Stopped random walk is not uniformly integrable

                    Lowndes Grove History Architecture References Navigation menu32°48′6″N 79°57′58″W / 32.80167°N 79.96611°W / 32.80167; -79.9661132°48′6″N 79°57′58″W / 32.80167°N 79.96611°W / 32.80167; -79.9661178002500"National Register Information System"Historic houses of South Carolina"Lowndes Grove""+32° 48' 6.00", −79° 57' 58.00""Lowndes Grove, Charleston County (260 St. Margaret St., Charleston)""Lowndes Grove"The Charleston ExpositionIt Happened in South Carolina"Lowndes Grove (House), Saint Margaret Street & Sixth Avenue, Charleston, Charleston County, SC(Photographs)"Plantations of the Carolina Low Countrye