7
$\begingroup$

Given a $N\times N$ "chess" board (Let $N = 10^{100}$) and a knight at $(0,0)$.

Can the knight go to the position $(x, y)$ with jump $[a, b]$ moves ?

jump $[a, b]$ mean: the knight on $(x,y)$ can move to $(x \pm a, y \pm b),\ (x \mp a, y \pm b), \ (x \pm b, y \pm a) \text{ or}\ (x \mp b, y \pm a)$


Can I use A* search algorithm to solve this problem ?

Can I solve it without a computer ?

$\endgroup$
  • 4
    $\begingroup$ being relatively prime is not enough, for example the knight still can't change colours with (odd,odd) moves, like (1,1) or (3,5). $\endgroup$ – mercio Mar 13 '14 at 13:26
  • $\begingroup$ @mercio Why with $(1,1)$ the knight can't change colour? If $(a,b) = (1,1)$ it means that the knight moves like a normal chess knight, who can reach every slots of the chessboard... $\endgroup$ – sirfoga Mar 13 '14 at 15:57
  • 1
    $\begingroup$ @Foga A normal chess knight is $(a,b)=(1,2)$. $\endgroup$ – Ted Mar 13 '14 at 15:58
  • $\begingroup$ sorry! in my country the horse = your knight! what a misunderstanding! $\endgroup$ – sirfoga Mar 13 '14 at 16:01
  • 1
    $\begingroup$ If you can go everywhere, you can go to $(0,1)$. If you can go to $(0,1)$, you can go everywhere. Did you try to prove that you can go to $(0,1)$ if $a \neq 0 \neq b$, $a$ and $b$ prime together and $a+b$ is odd? $\endgroup$ – Sylvain Biehler Mar 13 '14 at 16:40
5
$\begingroup$

Here's a proof outline for the specific subcase of whether the knight can reach all positions; the rest should be an easy exercise. First of all, (as pointed out in comments) the knight can get everywhere iff it can get from $(0, 0)$ to $(1, 0)$: obviously if it can reach all squares then it can reach any particular square. Contrariwise, if it can reach $(1, 0)$ then by symmetry it can reach $(0, 1)$ and then by composing the move sequences $m$ and $n$ times respectively then it can get to $(m, n)$ for any $m$ and $n$.

Now, note that we can restrict to half of the available moves if we're willing to talk about both positive and negative move counts; we never need moves of the form $(x, y)\to (x+a, y+b)$ and $(x, y)\to (x-a, y-b)$ in the same sequence (since we could get to the same location by omitting both moves), so we can just talk about $\alpha (+a, +b)$ moves with the caveat that $\alpha$ can be negative. For concreteness' sake, we'll limit to the four classes of moves $(\pm a, +b)$ and $(\pm b, +a)$, and use the variables $\alpha_+$, $\alpha_-$, $\beta_+$, $\beta_-$ for the number of moves of the four types. Then for a move sequence to reach $(1, 0)$ we must have $a(\alpha_+-\alpha_-)+b(\beta_+-\beta_-) = 1$ and simultaneously $b(\alpha_++\alpha_-)+a(\beta_++\beta_-) = 0$. Now, the latter equation can be solved by $\alpha_++\alpha_-=a$, $\beta_++\beta_-=-b$, and if $\gcd(a,b)=1$ (and only then) then we can find $c, d$ such that $ac+bd=1$.

From these values, though, we can backsolve for $\alpha_\pm$ and $\beta_\pm$: from $\alpha_++\alpha_- = a$ and $\alpha_+-\alpha_-=c$ we get $\alpha_+ = \frac12(a+c)$ and $\alpha_-=\frac12(a-c)$, and then likewise $\beta_+ = \frac12(-b+d)$ and $\beta_- = \frac12(-b-d)$.

Furthermore, since $\gcd(a,b)=1$ then at least one of $a,b$ is odd; we'll say that $a$ is always odd. Now, by adding $b$ to $c$ and subtracting $a$ from $d$ if necessary we can always choose $c$ odd and $d$ even in $ac+bd=1$; if $a$ is odd and $b$ is even then this is the end of the story, since then $\alpha_\pm=\frac12(a\pm c)$ and likewise $\beta_\pm$ will all be integers. Unfortunately, if $a$ and $b$ are both odd then there's no way of choosing $c$ and $d$ both odd, since then $ac+bd$ will always be even — this is the 'checkerboard' obstruction, that every sequence of moves will lead to a square of the same color (i.e., with $x+y$ having the same parity) as the starting square.

On the other hand, this construction shows that the checkerboard obstruction is essentially the only obstruction; starting from $a, b$ of opposite parity (again, we can arbitrarily choose $a$ as the odd one) with $\gcd(a,b)=1$ then we can find $c, d$ such that $ac+bd=1$ via the Euclidean algorithm, then find $\alpha_\pm$ and $\beta_\pm$ from the equations above; these values give the move sequence needed to get to $(1, 0)$, and from there we can get to anywhere else on the (presumed infinite) board. (An interesting exercise is to try and find the smallest board on which you can get everywhere, factoring in the edge effects — the $(n, n-1)$ case makes a nice challenge).

$\endgroup$
4
$\begingroup$

To add an algebraic approach going into the same direction as Steven Stadnicki's excellent answer:

Let's call any combination of moves a translation. If the board was infinite, the set of all possible translations of the knight would form a subgroup of the additive group $\Bbb Z \times \Bbb Z$. Hence, the question could be restated as to whether $ (\pm a,b)$,$(\pm b,a)$ generate $\Bbb Z \times \Bbb Z$.

This is obviously false if $(a,b)$ are not coprime. So suppose $a,b$ are coprime and let $$G:=\langle (\pm a,b),(\pm b,a)\rangle \subseteq \Bbb Z \times \Bbb Z$$ It is clear that $(0,2a),(0,2b) \in G$, hence $(0,2) \in G$. Similarly, $(2,0) \in G$, showing $2\Bbb Z \times 2\Bbb Z \subseteq G$. So the only remaining question is whether the images of $(a,b),(b,a)$ generate $\Bbb Z/2\Bbb Z \times \Bbb Z/2\Bbb Z$. This is the case iff $(a,b) \not \equiv (b,a)$ in $\Bbb Z/2\Bbb Z \times \Bbb Z/2\Bbb Z$, or equivalently $(a,b) \not \equiv (1,1) \bmod 2$.

In other words:

On an infinite board the knight reaches all positions iff $a,b$ are coprime and of different parity.

Note that this argument can be translated to $\Bbb N \times \Bbb N$ if you require the board to be bounded to the left and to the bottom of $(0,0)$.

$\endgroup$
  • $\begingroup$ That's elegant! $\endgroup$ – Henning Makholm Mar 13 '14 at 21:33
  • $\begingroup$ @HenningMakholm Thanks. :) $\endgroup$ – benh Mar 13 '14 at 21:47
0
$\begingroup$

The knight can move only onto positions like$$(x,y) = (a(m_a-n_a)+b(m_b-n_b),a(r_a-s_a)+b(r_b-s_b))$$ where

  • $m = $ number of times the knight goes right
  • $n = $ number of times the knight goes left
  • $r =$ number of times the knight goes up
  • $s =$ number of times the knight goes down
  • $m_a =$ number of times the knight goes right by $a$
  • $n_a =$ number of times the knight goes left by $a$
  • $m_b =$ number of times the knight goes right by $b$
  • $n_b =$ number of times the knight goes left by $b$
  • $r_a =$ number of times the knight goes up by $a$
  • $s_a =$ number of times the knight goes down by $a$
  • $r_b =$ number of times the knight goes up by $b$
  • $s_b =$ number of times the knight goes down by $b$

In fact, consider only the movement on $x$-axis: let $m$ the number of times the knight goes right, and $n$ the number of times the knight goes left. Then you get that, after some moves, the knight is on the $(am_a + bm_b-an_a -bn_b) = (a(m_a-n_a)+b(m_b-n_b))$-th slot, where $m_a+m_b = m$ and $n_a +n_b =n$. Now, let's take a look at the vertical movement: at every move (right or left) the knight can also go upward or downward. Let $r$ the number of times the knight goes upward and $s$ the number of times the knight goes downward. Similarly the knight can reach all slots in the form $(ar_a + br_b-as_a -bs_b) = (a(r_a-s_a)+b(r_b-s_b))$-th slot, where $r_a+r_b = r$ and $s_a +s_b =s$. Clearly $r+s=m+n$.

So the positions the knight can reach are in the form $(a(m_a-n_a)+b(m_b-n_b),a(r_a-s_a)+b(r_b-s_b))$

Note that if $GCD(a,b) = g > 1$ then the knight can only reach positions multiple of $g$.

$\endgroup$
  • $\begingroup$ I find the use of $\pm$ here confusing -- it is not clear to me where and how each of the signs are quantified. $\endgroup$ – Henning Makholm Mar 13 '14 at 13:49
  • $\begingroup$ sorry...I've edited the answer as to make it clearer $\endgroup$ – sirfoga Mar 13 '14 at 13:55
  • $\begingroup$ I still don't understand the statement of the conclusion. For an ordinary chess knight with $(a,b)=(1,2)$, are you claiming that the $y$ coordinates of reachable points are always multiples of $2$? $\endgroup$ – Henning Makholm Mar 13 '14 at 14:05
  • $\begingroup$ yes of course! because at every vertical move the knight can go up or down only by $2 \Rightarrow $ he can reach only slots in the form $2r-2s \Rightarrow \text{ only multiple of }2$ $\endgroup$ – sirfoga Mar 13 '14 at 14:07
  • 1
    $\begingroup$ Okay, now you have managed to rephrase the question faithfully, but it doesn't seem that you have made any progress in answering it. Given $a,b,x,y$, how would you concretely go about determining whether $(x,y)$ can be written in the form you give? $\endgroup$ – Henning Makholm Mar 13 '14 at 14: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.