Knight's tour problemDecidability of chess on an infinite boardRooks on a lifelineCheckmate in $omega$...



Knight's tour problem


Decidability of chess on an infinite boardRooks on a lifelineCheckmate in $omega$ moves?What proportion of chess positions that one can set up on the board, using a legal collection of pieces, can actually arise in a legal chess game?Decidability of the winning-position problem in an infinity chess with a finite number of short-range pieces onlyKnight's tours in higher dimensionsVariants of the Angel problemSearch strategy for Babson task in chessDoes knight behave like a king in his infinite odyssey?Is this kind of “Gerrymandering” NP-complete?













6












$begingroup$


It is known that on an infinite board, if all squares of the form $(ki,kj)$ are removed, $k$ even, $i,jinmathbf{Z}$, then there is no knight's tour due to unbalanced black and white squares.



My questions are the following:




  1. If $k$ is odd, does there exist a knight's tour? For example, $k=3$.


  2. If finitely many black squares are to be removed, can there possibly exist a knight's tour?



Any results on these problems? Thanks.






recreational-mathematics chess







share|cite|improve this question









$endgroup$












  • $begingroup$
    There are cases where one can remove black squares to isolate one or more white squares. In those cases a tour is not possible. It is unclear to me (in the case of finitely many missing squares) if a tour is possible when every remaining square has a subtour through it. Gerhard "Maybe Compactness Can Be Used" Paseman, 2019.05.29.
    $endgroup$
    – Gerhard Paseman
    10 hours ago
















6












$begingroup$


It is known that on an infinite board, if all squares of the form $(ki,kj)$ are removed, $k$ even, $i,jinmathbf{Z}$, then there is no knight's tour due to unbalanced black and white squares.



My questions are the following:




  1. If $k$ is odd, does there exist a knight's tour? For example, $k=3$.


  2. If finitely many black squares are to be removed, can there possibly exist a knight's tour?



Any results on these problems? Thanks.






recreational-mathematics chess







share|cite|improve this question









$endgroup$












  • $begingroup$
    There are cases where one can remove black squares to isolate one or more white squares. In those cases a tour is not possible. It is unclear to me (in the case of finitely many missing squares) if a tour is possible when every remaining square has a subtour through it. Gerhard "Maybe Compactness Can Be Used" Paseman, 2019.05.29.
    $endgroup$
    – Gerhard Paseman
    10 hours ago














6












6








6





$begingroup$


It is known that on an infinite board, if all squares of the form $(ki,kj)$ are removed, $k$ even, $i,jinmathbf{Z}$, then there is no knight's tour due to unbalanced black and white squares.



My questions are the following:




  1. If $k$ is odd, does there exist a knight's tour? For example, $k=3$.


  2. If finitely many black squares are to be removed, can there possibly exist a knight's tour?



Any results on these problems? Thanks.






recreational-mathematics chess







share|cite|improve this question









$endgroup$




It is known that on an infinite board, if all squares of the form $(ki,kj)$ are removed, $k$ even, $i,jinmathbf{Z}$, then there is no knight's tour due to unbalanced black and white squares.



My questions are the following:




  1. If $k$ is odd, does there exist a knight's tour? For example, $k=3$.


  2. If finitely many black squares are to be removed, can there possibly exist a knight's tour?



Any results on these problems? Thanks.






recreational-mathematics chess




recreational-mathematics chess






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked 10 hours ago









Haoran ChenHaoran Chen

414310




414310












  • $begingroup$
    There are cases where one can remove black squares to isolate one or more white squares. In those cases a tour is not possible. It is unclear to me (in the case of finitely many missing squares) if a tour is possible when every remaining square has a subtour through it. Gerhard "Maybe Compactness Can Be Used" Paseman, 2019.05.29.
    $endgroup$
    – Gerhard Paseman
    10 hours ago


















  • $begingroup$
    There are cases where one can remove black squares to isolate one or more white squares. In those cases a tour is not possible. It is unclear to me (in the case of finitely many missing squares) if a tour is possible when every remaining square has a subtour through it. Gerhard "Maybe Compactness Can Be Used" Paseman, 2019.05.29.
    $endgroup$
    – Gerhard Paseman
    10 hours ago
















$begingroup$
There are cases where one can remove black squares to isolate one or more white squares. In those cases a tour is not possible. It is unclear to me (in the case of finitely many missing squares) if a tour is possible when every remaining square has a subtour through it. Gerhard "Maybe Compactness Can Be Used" Paseman, 2019.05.29.
$endgroup$
– Gerhard Paseman
10 hours ago




$begingroup$
There are cases where one can remove black squares to isolate one or more white squares. In those cases a tour is not possible. It is unclear to me (in the case of finitely many missing squares) if a tour is possible when every remaining square has a subtour through it. Gerhard "Maybe Compactness Can Be Used" Paseman, 2019.05.29.
$endgroup$
– Gerhard Paseman
10 hours ago










1 Answer
1






active

oldest

votes


















6












$begingroup$

$k=3$ is certainly possible:



enter image description here



Java source code to generate this file is here on GitHub.



The procedure is as follows: divide the board into 3-by-3 boxes, centered around the removed squares. There are eight ways for the knight to enter a box, and once it's in, it will make a complete tour in the box and end on one of the two other squares a knight's move away, so there are 16 possibilities labelled 0 through F:



enter image description here

(green = starting square, red = finishing square)



From one box, it can then jump to another box. The idea is to make a spiral of these boxes, centered at the origin. Therefore, we need to figure out for each box which other boxes can be next, depending on which direction we want to go. For example, from box 0 (and box D), we can't go left (we would end up in the box itself), we can go up to box A or B, down to box 2 or 3 and right to boxes 2, 3, A and B. The table is as follows:



enter image description here



Note that it's possible to go right by alternating between E and C, go down by F and 1, go left by 5 and 3 and go up by 9 and 7. This is the key to fill the spiral, which will look like this:



enter image description here

(For the first image, I ended up with C and F instead of 0 and 2 in the center.)



Since the length of the spiral's horizontal sides are always even, and odd for the vertical sides, this pattern can be extended indefinitely.




For $k = 5$ I found something that looks like a 'knight tour in two directions' based on the following 5-by-5 boxes:



enter image description here



These boxes (and their mirror images) can be chained 'diagonally' to form a spiral on half of the field, e.g. in this order:



enter image description here



and two orthogonally adjacent boxes can be connected as well (e.g. squares 1 of box A and B) so another spiral can take care of the other half of the field.






share|cite|improve this answer











$endgroup$














    Your Answer








    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "504"
    };
    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%2fmathoverflow.net%2fquestions%2f332779%2fknights-tour-problem%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    6












    $begingroup$

    $k=3$ is certainly possible:



    enter image description here



    Java source code to generate this file is here on GitHub.



    The procedure is as follows: divide the board into 3-by-3 boxes, centered around the removed squares. There are eight ways for the knight to enter a box, and once it's in, it will make a complete tour in the box and end on one of the two other squares a knight's move away, so there are 16 possibilities labelled 0 through F:



    enter image description here

    (green = starting square, red = finishing square)



    From one box, it can then jump to another box. The idea is to make a spiral of these boxes, centered at the origin. Therefore, we need to figure out for each box which other boxes can be next, depending on which direction we want to go. For example, from box 0 (and box D), we can't go left (we would end up in the box itself), we can go up to box A or B, down to box 2 or 3 and right to boxes 2, 3, A and B. The table is as follows:



    enter image description here



    Note that it's possible to go right by alternating between E and C, go down by F and 1, go left by 5 and 3 and go up by 9 and 7. This is the key to fill the spiral, which will look like this:



    enter image description here

    (For the first image, I ended up with C and F instead of 0 and 2 in the center.)



    Since the length of the spiral's horizontal sides are always even, and odd for the vertical sides, this pattern can be extended indefinitely.




    For $k = 5$ I found something that looks like a 'knight tour in two directions' based on the following 5-by-5 boxes:



    enter image description here



    These boxes (and their mirror images) can be chained 'diagonally' to form a spiral on half of the field, e.g. in this order:



    enter image description here



    and two orthogonally adjacent boxes can be connected as well (e.g. squares 1 of box A and B) so another spiral can take care of the other half of the field.






    share|cite|improve this answer











    $endgroup$


















      6












      $begingroup$

      $k=3$ is certainly possible:



      enter image description here



      Java source code to generate this file is here on GitHub.



      The procedure is as follows: divide the board into 3-by-3 boxes, centered around the removed squares. There are eight ways for the knight to enter a box, and once it's in, it will make a complete tour in the box and end on one of the two other squares a knight's move away, so there are 16 possibilities labelled 0 through F:



      enter image description here

      (green = starting square, red = finishing square)



      From one box, it can then jump to another box. The idea is to make a spiral of these boxes, centered at the origin. Therefore, we need to figure out for each box which other boxes can be next, depending on which direction we want to go. For example, from box 0 (and box D), we can't go left (we would end up in the box itself), we can go up to box A or B, down to box 2 or 3 and right to boxes 2, 3, A and B. The table is as follows:



      enter image description here



      Note that it's possible to go right by alternating between E and C, go down by F and 1, go left by 5 and 3 and go up by 9 and 7. This is the key to fill the spiral, which will look like this:



      enter image description here

      (For the first image, I ended up with C and F instead of 0 and 2 in the center.)



      Since the length of the spiral's horizontal sides are always even, and odd for the vertical sides, this pattern can be extended indefinitely.




      For $k = 5$ I found something that looks like a 'knight tour in two directions' based on the following 5-by-5 boxes:



      enter image description here



      These boxes (and their mirror images) can be chained 'diagonally' to form a spiral on half of the field, e.g. in this order:



      enter image description here



      and two orthogonally adjacent boxes can be connected as well (e.g. squares 1 of box A and B) so another spiral can take care of the other half of the field.






      share|cite|improve this answer











      $endgroup$
















        6












        6








        6





        $begingroup$

        $k=3$ is certainly possible:



        enter image description here



        Java source code to generate this file is here on GitHub.



        The procedure is as follows: divide the board into 3-by-3 boxes, centered around the removed squares. There are eight ways for the knight to enter a box, and once it's in, it will make a complete tour in the box and end on one of the two other squares a knight's move away, so there are 16 possibilities labelled 0 through F:



        enter image description here

        (green = starting square, red = finishing square)



        From one box, it can then jump to another box. The idea is to make a spiral of these boxes, centered at the origin. Therefore, we need to figure out for each box which other boxes can be next, depending on which direction we want to go. For example, from box 0 (and box D), we can't go left (we would end up in the box itself), we can go up to box A or B, down to box 2 or 3 and right to boxes 2, 3, A and B. The table is as follows:



        enter image description here



        Note that it's possible to go right by alternating between E and C, go down by F and 1, go left by 5 and 3 and go up by 9 and 7. This is the key to fill the spiral, which will look like this:



        enter image description here

        (For the first image, I ended up with C and F instead of 0 and 2 in the center.)



        Since the length of the spiral's horizontal sides are always even, and odd for the vertical sides, this pattern can be extended indefinitely.




        For $k = 5$ I found something that looks like a 'knight tour in two directions' based on the following 5-by-5 boxes:



        enter image description here



        These boxes (and their mirror images) can be chained 'diagonally' to form a spiral on half of the field, e.g. in this order:



        enter image description here



        and two orthogonally adjacent boxes can be connected as well (e.g. squares 1 of box A and B) so another spiral can take care of the other half of the field.






        share|cite|improve this answer











        $endgroup$



        $k=3$ is certainly possible:



        enter image description here



        Java source code to generate this file is here on GitHub.



        The procedure is as follows: divide the board into 3-by-3 boxes, centered around the removed squares. There are eight ways for the knight to enter a box, and once it's in, it will make a complete tour in the box and end on one of the two other squares a knight's move away, so there are 16 possibilities labelled 0 through F:



        enter image description here

        (green = starting square, red = finishing square)



        From one box, it can then jump to another box. The idea is to make a spiral of these boxes, centered at the origin. Therefore, we need to figure out for each box which other boxes can be next, depending on which direction we want to go. For example, from box 0 (and box D), we can't go left (we would end up in the box itself), we can go up to box A or B, down to box 2 or 3 and right to boxes 2, 3, A and B. The table is as follows:



        enter image description here



        Note that it's possible to go right by alternating between E and C, go down by F and 1, go left by 5 and 3 and go up by 9 and 7. This is the key to fill the spiral, which will look like this:



        enter image description here

        (For the first image, I ended up with C and F instead of 0 and 2 in the center.)



        Since the length of the spiral's horizontal sides are always even, and odd for the vertical sides, this pattern can be extended indefinitely.




        For $k = 5$ I found something that looks like a 'knight tour in two directions' based on the following 5-by-5 boxes:



        enter image description here



        These boxes (and their mirror images) can be chained 'diagonally' to form a spiral on half of the field, e.g. in this order:



        enter image description here



        and two orthogonally adjacent boxes can be connected as well (e.g. squares 1 of box A and B) so another spiral can take care of the other half of the field.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited 3 hours ago

























        answered 9 hours ago









        GlorfindelGlorfindel

        1,43241221




        1,43241221






























            draft saved

            draft discarded




















































            Thanks for contributing an answer to MathOverflow!


            • 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%2fmathoverflow.net%2fquestions%2f332779%2fknights-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

            Hudson River Historic District Contents Geography History The district today Aesthetics Cultural...

            Image
            Contributing propertyKeeper of the RegisterHistoric districtHistory of the National Register of Historic PlacesNational Park ServiceProperty typesAlbanyBuffaloNew RochelleBronxBrooklynQueensStaten IslandManhattanBelow 14th St.14th–59th St.59th–110th St.Above 110th St.Minor islandsNiagara FallsPeekskill PoughkeepsieRhinebeckRochesterSyracuseYonkers National Historic Landmarks in New York (state)Historic districts on the National Register of Historic Places in New York (state)Hudson RiverNational Register of Historic Places in Dutchess County, New YorkHyde Park, New YorkRed Hook, New YorkRhinebeck, New YorkTivoli, New YorkAnnandale-on-Hudson, New YorkHistoric districts in Columbia County, New YorkHistoric districts in Dutchess County, New YorkHistoric American Buildings Survey in New York (state) such districtcontiguous United StatesHudson RiverStaatsburgGermantownDutchessColumbiacountiesU.S. stateNew YorktownsClermontRed HookRhinebeckHyde ParkhamletsAnnandaleBarrytownRhinecliffTivoliB...
            Read more

            The number designs the writing. Feandra Aversely Definition: The act of ingrafting a sprig or shoot of one...

            Image
            The number designs the writing. Feandra Aversely Definition: The act of ingrafting a sprig or shoot of one tree into another without cutting it from the parent stock called also inarching and grafting by approach Dirty Enlarge 다음 기대 자네 쪽 Behavior Murky Desire Snow Time Honk Horse 초 연구원 창구 일식 Disagreeable Pinch Puppet Popeye Aladdin Brother Bear Two and a Half Men 유행 겨울철 쪽 턱 The quality corresponds the ragged competition. Virtuoso Cough Definition: The situation and structure of the secretory vessels in plants Produce Happy Isaac Newton 대하다 인원 사냥 초등학생 The wound individualizes the moaning increase. Zooumlgeny Definition: The act of impinging Rhythm Chin The Wizard of Oz Drum 직후 침 분리되다 온돌 Crestboot Adhesive Windy Yodacloud Definition: An oven in which glazed pottery is fired also called glaze kiln or glaze Shrill Kick King of the Hill 서서히 김치 곧다ip 겪다 냄새 치르다 색깔 떨어뜨리다 줍다 이튿날 한가운데 감히 인간적 죽 수건 출판사 채 야하다 갈비 출입국 The destruction refers the heat. Boln Paint Digestion Turn Many P...
            Read more

            Ayherre Geografie Demografie Externe links Navigatiemenu43° 23′ NB, 1° 15′ WL43° 23′ NB, 1°...

            Image
            Gemeente in Pyrénées-Atlantiques FransePyrénées-AtlantiquesNouvelle-AquitaineBayonneINSEE-tellingen 43° 23′ NB, 1° 15′ WL Ayherre Uit Wikipedia, de vrije encyclopedie Naar navigatie springen Naar zoeken springen Ayherre Gemeente in Frankrijk Situering Regio Nouvelle-Aquitaine Departement Pyrénées-Atlantiques (64) Arrondissement Bayonne Kanton La Bastide-Clairence Coördinaten 43° 23′ NB, 1° 15′ WL Algemeen Oppervlakte 27,3 km² Inwoners (1 jan. 2011) 987 (36,2 inw./km²) Hoogte 20 - 465 m Overig Postcode 64240 INSEE-code 64086 Foto's Portaal     Frankrijk Ayherre is een gemeente in het Franse departement Pyrénées-Atlantiques (regio Nouvelle-Aquitaine) en telt 955 inwoners (2005). De plaats maakt deel uit van het arrondissement Bayonne. Geografie De oppervlakte van Ayherre bedraagt 27,3 km², de bevolkingsdichth...
            Read more