bonanova Posted May 4, 2014 Report Share Posted May 4, 2014 The Black King sets out one day to tour his kindom, a standard 8x8 chessboard. He's not feeling well, though, and he wants to return by the shortest path to his starting square. We'll assume all squares are one unit on a side and ask, what is the length of such a trip? Wait. This is Brainden. You all are geniuses. Let's add a wrinkle. The King is actually feeling fine, and he wants his walk to provide him the maximum possiblle workout. Diagonal moves now come into play. To avoid radical complications , we'll count their length as two N-S or E-W moves. So here's the actual question: what is the maximal length of a complete King's tour of an 8x8 chessboard? Bonus points if a proof is given. Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted June 21, 2014 Author Report Share Posted June 21, 2014 Quote Link to comment Share on other sites More sharing options...
0 Perhaps check it again Posted May 4, 2014 Report Share Posted May 4, 2014 In one paragraph you are asking for the shortest path for the complete tour, but in another tour, you are asking for the maximal length of a complete tour? How are these two plans not contradicting each other? Quote Link to comment Share on other sites More sharing options...
0 Perhaps check it again Posted May 4, 2014 Report Share Posted May 4, 2014 It should be: "..., but in another paragraph, you are asking for..." Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted May 4, 2014 Author Report Share Posted May 4, 2014 If you like, warm up with "What's 64 times 1?" before getting to the actual question. Quote Link to comment Share on other sites More sharing options...
0 Perhaps check it again Posted May 5, 2014 Report Share Posted May 5, 2014 (edited) The statement of your problem would have been much clearer (and leaving no ambiguity that you wanted only one question answered) if you had phrased part of it along these lines: [insert the first original two sentences as given.] We'll assume all squares are one unit on a side, and we might ask, "What is the length of such a trip?" Wait. This is Brainden. You are all geniuses. Let's alter the problem.** [insert the remaining original text.] ** You're not just "adding a wrinkle." You're substantially changing the problem, mainly going from shortest path to maximal length path. Edited May 5, 2014 by Perhaps check it again 2 Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted May 5, 2014 Author Report Share Posted May 5, 2014 It seems you understand the OP. Now about the maximal path length ... Quote Link to comment Share on other sites More sharing options...
0 k-man Posted May 5, 2014 Report Share Posted May 5, 2014 Assuming that 1) The king starts from e8 (the normal starting position for the black King) and 2) Every square is to be visited only once is 116 with 12 lateral moves and 52 diagonal moves. Here is the picture of my solution: Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted May 5, 2014 Author Report Share Posted May 5, 2014 Cool. Best so far. There is a slightly longer path. What's the fraction of diagonal moves if the dimensions are 8x2? Quote Link to comment Share on other sites More sharing options...
0 plasmid Posted May 9, 2014 Report Share Posted May 9, 2014 Cool. Best so far. There is a slightly longer path.What's the fraction of diagonal moves if the dimensions are 8x2?If I'm drawing correct inferences from this hint... does this mean the king doesn't have to finish the tour adjacent to his starting square so he can take one more step to get back home? Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted May 9, 2014 Author Report Share Posted May 9, 2014 A tour of the chessboard is technically a path that visits all the squares. I mean to ask for a tour that comes back to the original square - a closed path. There will be an even number (64) of moves. And the answer, no secret here, maximizes the number of diagonal moves. Quote Link to comment Share on other sites More sharing options...
0 plasmid Posted May 9, 2014 Report Share Posted May 9, 2014 Ok, asking for the solution for an 8x2 grid seemed that you were suggesting he repeat this four times, minus one move at the end, to visit every square with only eight non-diagonal moves. But since I have yet to encounter a cylindrical chess board, this won't fly. Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted May 9, 2014 Author Report Share Posted May 9, 2014 yeah, everything you said. the comment was to suggest the obtainable degree of diagonal moves. Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted May 17, 2014 Author Report Share Posted May 17, 2014 Assuming that 1) The king starts from e8 (the normal starting position for the black King) and 2) Every square is to be visited only once is 116 with 12 lateral moves and 52 diagonal moves. Here is the picture of my solution: Black King.gif Four fewer lateral moves is possible. Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted May 20, 2014 Author Report Share Posted May 20, 2014 Ok, asking for the solution for an 8x2 grid seemed that you were suggesting he repeat this four times, minus one move at the end, to visit every square with only eight non-diagonal moves. But since I have yet to encounter a cylindrical chess board, this won't fly.King moves.jpg But it is the right idea. The minimum number (8) of adjacent steps can be maintained as small parts of the four rectangles are minimally changed to effectively stitch them together. Quote Link to comment Share on other sites More sharing options...
Question
bonanova
The Black King sets out one day to tour his kindom, a standard 8x8 chessboard.
He's not feeling well, though, and he wants to return by the shortest path to his starting square.
We'll assume all squares are one unit on a side and ask, what is the length of such a trip?
Wait. This is Brainden. You all are geniuses. Let's add a wrinkle.
The King is actually feeling fine, and he wants his walk to provide him the maximum possiblle workout.
Diagonal moves now come into play. To avoid radical complications , we'll count their length as two N-S or E-W moves.
So here's the actual question: what is the maximal length of a complete King's tour of an 8x8 chessboard?
Bonus points if a proof is given.
Link to comment
Share on other sites
14 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.