3
$\begingroup$

An $(a,b)$-knight moves $a$ units horizontally and $b$ units vertically (or $b$ horizontally and $a$ vertically) for each move. For example, the traditional knight is a $(1,2)$- or $(2,1)$-knight. Does there exist general algorithms to the following problems?

  1. Given $a,b$ and an infinite chessboard, can an $(a,b)$-knight reach every point on the chessboard no matter where it starts?

  2. Given $a,b$ and an $m\times n$ chessboard, can an $(a,b)$-knight reach every point on the chessboard no matter where it starts? Here you can make the assumption that $m,n\gg a,b$ so the space won't be too limited for the knight to move.

In an infinite chessboard, it should be simpler, because the knight can reach every point if and only if it can achieve a single-unit up, down, left and right movement. For $m\times n$ chessboards though, I guess there might still be problems (or requirement for special treatment) with the edge or corner points, even when $m,n\gg a,b$?

$\endgroup$
  • 2
    $\begingroup$ I'm thinking that one might be interested in the GCD of $a$ and $b$ ... $\endgroup$ – Matti P. Jun 3 at 12:27
  • 3
    $\begingroup$ @MattiP. That can't be the only thing. Bishops are really just $(1, 1)$ knights that can move several steps in one move. They can't reach everywhere. $\endgroup$ – Arthur Jun 3 at 12:27
  • 2
    $\begingroup$ I think the if and only if condition is $\gcd(a+b,a-b)=1$. $\endgroup$ – Hw Chu Jun 3 at 12:38
  • 2
    $\begingroup$ That is just a lazy way to state $\gcd(a,b) = 1$ and "$a$ and $b$ have different parity", as the comments have already stated. I am a bit busy now to write down an answer, but the "only if" side is already in the comments, and for the "if" side, claim that you can reach from $(0,0)$ to $(2a,0)$ or $(2b, 0)$, then claim you can reach from $(0,0)$ to $(2,0)$, then claim you can reach from $(0,0)$ to $(0,1)$, which is all you need. $\endgroup$ – Hw Chu Jun 3 at 12:47
  • 1
    $\begingroup$ I think for finite chessboards, imposing $2\max(a,b)+\min(a,b)\leq\min(m,n)$ should give enough room to move (though extremely tight, see 5x5 knight tour). Haven't fully check the details though. $\endgroup$ – user10354138 Jun 3 at 12:56
4
$\begingroup$

If $gcd(a,b)=1$ and $a+b$ is odd then the knight can visit every point (also by comments these conditions are nesessary) That's because by combinig $(a,b)$ step with $(a,-b)$ step yields a $(2a,0)$ move and similarly for $b$. Since $gcd(2a,2b)$=2 he can achieve by euclidean algorithm a $(2,0)$ move. Since $a+b$ is odd he can perform $(a,b)$ move and by adequate $2$-moves go back to be only one square apart. The answer for finite chessboard is the same since the knight can draw a sqare of size $ab$ in the middle of a chessboard and if $n$, $m$ are sufficiently large he can reach every point of this square. Now he can reach every other point by choosing the right starting point inside the square by Chineese Remainder Theorem. The proof requires some details but the idea is roughly correct (I think).

$\endgroup$
  • $\begingroup$ The answer for a finite chessboard is not always the same. Try $a=2,b=1$ on a $3×3$ chessboard for a classic case. $\endgroup$ – Oscar Lanzi Jun 3 at 15:30
  • 1
    $\begingroup$ No, it isn't. But the question is what happens for sufficiently large finite chessboard. And I sketch the solution of the fact that for all pairs $(a,b)$ there exists $N$ such that for all chessboards of size greater than $N$ the knight can visit any square. It woulf be interesting what is the minimal such $N$ though. $\endgroup$ – Bartek Jun 3 at 15:34
2
$\begingroup$

If $\gcd(a,b)>1$ or if $a\equiv b\pmod 2$, then (1) is clearly impossible.

The set of reachable positions with an $(a,b)$ knight is a sublattice $\Lambda$ of $\Bbb Z^2$ that is invariant under $90°$ rotation as well as vertical reflection. Let $(u,v)\in\Lambda-\{(0,0)\}$ be a $|\cdot|_1$-shortest non-zero vector (i.e., such that $|u|+|v|$ is minimized). Wlog $u\ge v\ge 0$ (but of course $u>0$). Then also $(2v,0)=(v,u)+(v,-u)\in\Lambda$. Then minimality of $|u|+|v|$ implies that either $v=0$ or $u=v$. We conclude that either $$\tag1\Lambda=\{\,(ui,uj)\mid i,j\in\Bbb Z\,\}$$ or $$\tag2\Lambda=\{\,((i+j)u,(i-j)u)\mid i,j\in\Bbb Z\,\}.$$ From $a\not\equiv b\mod 2$, we conclude that $(2)$ is impossible. From $\gcd(a,b)$ and $(a,b)\in\Lambda$, we conclude $u=1$. Hence all fields are reached.

$\endgroup$
  • $\begingroup$ Why is (1) impossible if $a,b$ are both odd? $\endgroup$ – Vim Jun 3 at 13:02
  • 1
    $\begingroup$ Okay I see, in that case the knight won't be able to reach the opposite colour. $\endgroup$ – Vim Jun 3 at 13:09
  • $\begingroup$ If i understand correctly, you are saying the shortest $(u,v)$ is a "generator" that (together with its $90°$ rotations and reflections) generate every other point in $\Lambda$. I agree it is true in this example, but is it obvious / does it follow directly from the definition of the sublattice? $\endgroup$ – antkam Jun 4 at 4:14

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.