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?