14
$\begingroup$

It is known that a knight can visit every cell of a 8x8 chess board exactly once. Here we consider the same task for a chameleon chess piece. This piece begins as a knight, then it transforms into a bishop, then it transforms back to a knight, and so on transforming after every move. Note that as a bishop it cannot jump over visited cells, ie., it can only move to the unvisited cells in its line of sight. Starting in the corner, can the chameleon piece visit every cell of a 8x8 grid exactly once? Can it form a closed path that comes back to it's starting point?

Here is an example solution for a 4x4 grid:

4 by 4 grid, 1st row numbers 1,10,12,7. 2nd row numbers 11,8,6,13. 3rd row numbers 9,2,4,15. 4th row: 3,16,14,5

$\endgroup$
3
  • $\begingroup$ If it moves a distance of more than one diagonally while in bishop mode, are all the squares it passes now also crossed off as visited? $\endgroup$ Nov 29, 2021 at 8:03
  • $\begingroup$ no only the square it lands on is visited. So you will still make 63 moves $\endgroup$ Nov 29, 2021 at 8:28
  • $\begingroup$ Is there a solution without any long bishop moves? $\endgroup$ Nov 29, 2021 at 14:53

3 Answers 3

17
$\begingroup$

For starters, we'll want to check parity. Every bishop-like move stays on the same coloured square, and every knight-like move switches colours. This means that we visit two light squares and then two dark ones, so it once we have reached 64 squares, 32 of them will have been dark, which is exactly right.

With this out of the way, we need to find a strategy. (Brute forcing the possibilities would take too long otherwise.)

The most beautiful strategy would be to find some compact shapes which can be filled at once, figure out their allowed connections, and tile the entire board with them. As an example shape, starting as a knight in the corner of an otherwise empty 3x3 square, it's easy to visit the entire 3x3 square, ending as a knight in the middle spot, allowing for 8 different directions to continue in.

enter image description here

If we try this approach, we'll find out it definitely works for the "just some path" case, but we'll just as soon notice that if we want to find a closed path, we're going to need a more powerful tool.

So this time we'll start by drawing two lines from the chameleon in the corner:

  1. The forward path, which starts with a knight's move, and can make long bishop's moves unless any of the skipped squares were already visited by the path itself, and
  2. The return path, which starts with a bishop's move, and can make long bishop's moves only if all of the skipped squares were already visited by that path itself.

With those restrictions, all the long bishop's moves will only jump over squares that are unvisited at the time of the jump.

Turns out that

It's not all that hard to find a closed path this way:

enter image description here

$\endgroup$
3
  • 3
    $\begingroup$ Absolutely brilliant work! I really like how you simplified the task. I also like how you used mostly short bishop moves. $\endgroup$ Nov 29, 2021 at 11:57
  • 1
    $\begingroup$ I think there is a little flaw in your 3x3 reasonning. If you fill a 3x3 square and jump to the next square with a knight jump, then you will have to start filling the second square with a bishop move, which I think is not possible (when would you go to the central cell?). $\endgroup$
    – Evargalo
    Dec 1, 2021 at 9:04
  • $\begingroup$ @evargalo had to double check, but yes, I did say "as an example shape" :-) $\endgroup$
    – Bass
    Dec 1, 2021 at 16:23
13
$\begingroup$

Here is a solution that

Uses only short bishop moves - and a very nice set of them, too! They are shown below in red, with the knight moves in blue:
enter image description here

Actually, now that I think about it, we can prove

That if our bishop only wants to walk one square at a time, this is the only set of bishop moves possible. That's because the bishop moves must form a matching: every square is the start or end of exactly one bishop move. For the corner squares, we know exactly which one that is, so we can fill it in. That leaves only one possibility for squares like a3 or c1. We can keep going, filling in the bishop move for squares that only have one short bishop move remaining, and eventually we will get the red X pattern we see in the solution above. (Filling in the knight moves is not very hard trial and error.)

$\endgroup$
1
  • 1
    $\begingroup$ This is beautiful! $\endgroup$ Dec 1, 2021 at 4:29
11
$\begingroup$

Bass's answer uses a 3x3 base. If instead we build from the 4x4 provided in the problem, we find that

it's possible to make an auxiliary 4x4 that matches up with the original well enough to connect two copies of it!
enter image description here
Here, the original 4x4 lies in the top right and bottom left quadrants, and the auxiliary 4x4 in the remaining two. Two "long" bishop moves are colored orange.

$\endgroup$
4
  • $\begingroup$ very nice! I was wondering if the provided 4x4 can be used somehow. $\endgroup$ Nov 29, 2021 at 14:52
  • $\begingroup$ is there a solution that uses 4 identical 4x4? $\endgroup$ Nov 29, 2021 at 14:54
  • 1
    $\begingroup$ @DmitryKamenetsky I don't believe so, because for any position that a 4*4 ends, a knight can't move to a mirror position in one of the other four quadrants. $\endgroup$
    – george
    Nov 29, 2021 at 19:50
  • $\begingroup$ Right; both fourfold symmetries of the chessboard change color, and eight moves of each kind leave you at the color you started on. I don't know how to factor quadrants being traversed in both directions into a proof, though. $\endgroup$ Nov 30, 2021 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.