4
$\begingroup$

Two knights are placed on opposite corners of a 4x4 grid. Can you move* each knight 7 times, such that each cell of the grid is visited exactly once by exactly one of the knights?

*Note that a knight moves 1 cell in one direction (horizontal or vertical) and two cells in an orthogonal direction.

$\endgroup$
0
8
$\begingroup$

One possible answer is

. 2 . .
. . 6 3
5 . 1 .
0 . 4 7

7 . 5 0
4 1 . .
. 6 . 2
. 3 . .

It doesn't look very symmetric at first glance, but if you look more closely,

Both knights exit the corner (0-1), cycle through four cells on the sides (2-5), and then enter another corner (6-7).

I think it's likely that there isn't any answer which does not follow this pattern. I'm pretty sure this property holds for all answers, with the following reasoning:

Let's classify the cells into four categories.

A B C D
C D A B
B A D C
D C B A

And let's assume the two knights start at the two corner D's, as in my solution at the top.

Then we can observe some facts:

  1. The two center D's must be the first moves of both knights. This is the only way for both to escape the corners. This settles the (0-1) part.
  2. There are some restrictions on moving between different groups. A knight can't move from A to D directly, nor can it move from B to C directly (and vice versa).
  3. For any knight, the only way to step on an A is to step on one of center A's first. Then it should move into one of the corner A's (otherwise there's no way to cover both corner A's). If a knight uses three cells, then it must use all four and stop at the second corner A. This means that the knight follows the path of D-D-B-B-A-A-A-A (or C's instead of B's), and then the other knight must go over two D's, two B's, and four C's, and the first two steps must be D. This is impossible by 2. Therefore, both knights must occupy two A's each, finishing at the corners.
  4. Now the two knights' paths are D-D-?-?-?-?-A-A. Since the remaining cells are B's and C's, and by 2, the two paths must be D-D-B-B-B-B-A-A and D-D-C-C-C-C-A-A respectively.

Assuming the initial positions are fixed at the corner D's, we have two choices with center D's, two choices with assigning B/C, and two choices with corner A's. So we can find 8 different solutions.

$\endgroup$
3
  • $\begingroup$ Very well done and very fast! Can you find any other solutions? $\endgroup$ Feb 24 at 1:27
  • $\begingroup$ @DmitryKamenetsky Please see my edit. $\endgroup$
    – Bubbler
    Feb 24 at 5:48
  • $\begingroup$ That's it you got it! $\endgroup$ Feb 24 at 12:40

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.