8
$\begingroup$

Consider lame chess king that can move only one cell left, down and diagonal upright. Consider square chess board.

Question: Can such a king visit all cells of a board (each cell only once) and end up in the cell to the left of the original?

I've tried many ideas: colorings, induction, graphs, etc. But nothing of these helped. Any help would be great!

$\endgroup$
7
  • $\begingroup$ did you try smaller boards? $\endgroup$
    – miracle173
    Commented Dec 8, 2021 at 16:30
  • 1
    $\begingroup$ Where does it start? And I am guessing it can’t visit the same square twice, right? $\endgroup$
    – Tan
    Commented Dec 8, 2021 at 16:30
  • 1
    $\begingroup$ @Tan Yes, thank you, it can't, I'll fix it. It can start where you want. $\endgroup$
    – Grigori
    Commented Dec 8, 2021 at 16:32
  • $\begingroup$ @miracle173, yep, I haven't found such tours, but all mentioned ideas were banned! $\endgroup$
    – Grigori
    Commented Dec 8, 2021 at 16:34
  • 2
    $\begingroup$ It can't be done (checked by brute force), for $n \times n, n\le 8$ grids. $\endgroup$
    – Vepir
    Commented Dec 8, 2021 at 18:29

1 Answer 1

Reset to default
6
$\begingroup$

We can move and touch each square only once as shown in this picture. Start at the bottom right square

enter image description here

But we cannot end on the square left to the start square.

Such a tour consists of $l$ moves to the left, $d$ moves down and $x$ moves diagonal upright. The following equations hold: $$l+d+x=63$$ because we touch every square of the $8\times 8$ squares exactly once. $$d=x$$ because we end up in the same row as we started, so the number of down moves ($d$) must be equal to the number of up moves that can be only achieved by the diagonal moves($x$). Finally the number of left moves($l$) must be one more than the number of right moves($x$), so $$l=x+1$$

From this we get

$$(x+1)+x+x=63$$

which has no integer solution.

This argument works for all square boards because $n^2-2$ is not divisible by $3$ for any $n$.

$\endgroup$
2
  • $\begingroup$ Great solution! Thank you! I think it works for arbitrary square board, because length of tour will be N^2 - 1, which always is divisible by 3. $\endgroup$
    – Grigori
    Commented Dec 8, 2021 at 21:31
  • $\begingroup$ @Alexander for $N=3k$ the expression $N^2-1$ is not divisible by $3$. But $N^2-2$ is never divisible by $3$. I added this to my answer. $\endgroup$
    – miracle173
    Commented Dec 9, 2021 at 9:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .