I had this task in programming competition: There are two knights, which are $(p_1,q_1)$ and $(p_2, q_2)$. $(p,q)$ knight is figure, with p(q)-length first step, and q(p)-length second step in perpendicular direction. Simple chess knight is (2,1) or (1,2) knight. Given $(x_1,y_1)$ and $(x_2,y_2)$ - positions of two knights on $(W\times H)$ chess board. Find minimal path which leads both knights in same cell.
As I never saw task like this, I've started with simplier:
Given $(p,q)$ knight on $(W\times H)$ chess board in $(x_0,y_0)$ initial cell, can knight visit $(x,y)$ cell?
I can use some recursive algorithm for finding it, of course, but I've decided to look at this problem analyticaly. I made up this system:
$$pk_1+qk_2=x-x_0\\ qk_1+pk_2=y-y_0$$
Solutions of this system are: $$k_2=\frac{(y-y_0)p}{p^2-q^2}\\ k_1=\frac{x-x_0-qk_2}{p}$$
I thought, that point will be: all available for visit cells will lead to $k_1, k_2$ be integers. But from doing some examples I realised, that actually for available cells $k_1, k_2$ are rational, and for aunavailiable cells they are irrational. So I have questions:
- Where is my mistake in reasoning? [Answer] Because I don't take into account direction, thanks @Joffan.
- It is not seem to be practical way to use in program, because I can not distinguish rational from irrational in code. So what will be except recursion and linear programming?
- I think that this problem has some name, to google it and further reading. So where I can find some information about it?
If you allow $k_1,k_2$ to be integers, you have accounted for moves $(p,q), (-p,-q), (q,p), (-q,-p)$, but have not allowed $(p,-q),(-p,q),(q,-p),(-q,p)$ You are correct that $k_1,k_2$ should be integers but need $k_3,k_4$ for the other moves available. Then your intuition that the $k$'s should be integers is correct. The solution will not be unique as there are paths that return to the starting point. If you can move to a neighboring square, you can get anywhere. For example, with a standard $(2,1)$ knight you can move $(0,0) \to (1,2) \to (-1,1) \to (0,1)$, showing you can get to any square. If you can't get to every square there is a nice pattern that repeats of the squares you can get to. If $p$ and $q$ have a common factor $n$ you will only be able to get to squares that are multiples of $n$ in the orthogonal directions. There can also be parity restrictions. With a $(1,1)$ leaper you can't change colors so can only reach half the squares.