0
$\begingroup$

I apologize if this is not the right board to post this question but I'm cross-posting from the mathematics board. I am dealing with a computational question that extends the question posed in https://math.stackexchange.com/questions/104700/minimum-number-of-moves-to-reach-a-cell-in-a-chessboard-by-a-knight to the variant form of chess posed in https://math.stackexchange.com/questions/710815/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$.

This is similar to the question posed in this forum here: Knight on a chessboard. I'd like to know if there is a closed form answer rather than a solution that requires BFS because I would like to work with a chess board (or coordinate grid) that is $N \times N$ where $N$ is large (e.g. $10^6$).

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 https://math.stackexchange.com/questions/104700/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). Would this be more feasible than the BFS solution posted in: Knight on a chessboard?
  3. Use the logic behind the proof posted in https://math.stackexchange.com/questions/710815/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 https://math.stackexchange.com/questions/1585538/chess-knight-move-in-8x8-chessboard. Again, this may become computationally intractable unless this is solved using sparse graphs.

Any suggestions would be appreciated.

Improve this question
$\endgroup$
3
  • $\begingroup$ Let $k(\alpha,\beta, N, i,j)$ be the minimum number of steps needed for a $(\alpha,\beta)$-knight to reach position $(i,j)$ in a board of $N\times N$ starting from $(0,0)$. Is there a closed-form formula for $k$? Very unlikely. If $\alpha,\beta$ are fixed, there is a closed-form formula (with less than $8\alpha\beta$ clauses) for $k_{\alpha, \beta}$, where $k_{\alpha, \beta}(i,j)=k(\alpha, \beta, \infty, i,j)$. $\endgroup$
    – John L.
    Commented Jul 27, 2019 at 21:36
  • $\begingroup$ @Apass.Jack thank you for this insight. That actually help's narrow the problem down significantly. Just to clarify, suppose we assume $\alpha$ and $\beta$ are fixed, then what would be the list of $8\alpha\beta$ clauses? If I were to guess, my approach then would be as follows: suppose you reach the diagonal (x,x). Keep traveling down around the diagonal in a zig zag pattern until you reach the last $2\beta + 1 \times 2\beta + 1$ (if WLOG $\beta \geq \alpha$) sub grid near the target point $(i,j)$. At this point, it's a matter of reaching the final $(i,j)$ with these $8\alpha\beta$ clauses? $\endgroup$
    – rshroff08
    Commented Jul 27, 2019 at 23:14
  • $\begingroup$ The above approach is somewhat similar to what I see here: cs.stackexchange.com/questions/97903/… $\endgroup$
    – rshroff08
    Commented Jul 27, 2019 at 23:16

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.