1
$\begingroup$

I apologize if this is not the right board to post this question. I am dealing with a computational question that extends the question posed in Minimum number of moves to reach a cell in a chessboard by a knight to the variant form of chess posed in Knight move variant: Can it move from $A$ to $B$. Specifically, what is the number of minimum moves for a modified knight (call it ($\alpha,\beta$)-knight) that moves with $\pm\alpha$ and $\pm\beta$ along the coordinates (instead of the usual $[\pm 2, \pm 1]$)) in any direction to reach a point $(x, y)$ starting from the origin (0,0)? This would mean moving from $(x,y)$ to any of the following: (𝑥±$\alpha$,𝑦±$\beta$), (𝑥∓$\alpha$,𝑦±$\beta$), (𝑥±$\beta$,𝑦±$\alpha$) or (𝑥∓$\beta$,𝑦±$\alpha$) We can assume without loss of generality that $x \geq y$.

My initial thoughts of how to approach this is as follows:

  1. Modify the equation to reach either the $x$-axis or the diagonal as well as the number of subsequent moves from the diagonal to reach the origin as solved in Minimum number of moves to reach a cell in a chessboard by a knight.
  2. Solve this problem computationally with a recurrence equation that can be solved using dynamic programming (thought I suspect for larger$N$ in a $N\times N$ chessboard for large $\alpha$ and large $\beta$, this becomes intractable).
  3. Use the logic behind the proof posted in Knight move variant: Can it move from $A$ to $B$ to come up with an analytical solution for a recurrence equation rather than try to solve it computationally.
  4. Graph approach using Dijkstra's algorithm akin to solution posted in Chess knight move in 8x8 chessboard. Again, this may become computationally intractable unless this is solved using sparse graphs.

Any suggestions would be appreciated.

$\endgroup$
  • $\begingroup$ I would look into the limits of sum of indexes - as example (1,1) limits you to only even sum indexes which means that you can not get to half the board. $\endgroup$ – Moti Jul 27 at 3:52
  • $\begingroup$ @Moti that's an interesting thought. Another thing I thought about was taking into consideration the range of tiles visited to lie between lines $y = \frac{\alpha}{\beta}x$ and $y = \frac{\beta}{\alpha}x$. $\endgroup$ – rshroff08 Jul 27 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.