< Back to forum

Infinite chessboard

Let's consider an infinite chessboard where a knight is at position (x, y) and needs to reach at point(p, q). If we consider this chessboard on 2d cartesian plane. Do anybody know how to solve this question other than A* search algo.

#Graph #DP

Asked by: Anonymous on July 2, 2019, 4:13 p.m. Last updated on July 2, 2019, 4:13 p.m.

avatar

Do you want the shortest path from source to destinotion through your algorithm ,or just the answer to the question if it is reachable..

Because,don't you feel, a knight can reach any of the positions on the chess board?

SHUBHAM_GUPTA1 last updated on July 7, 2019, 4:18 p.m.
avatar

Shortest path i meant, forgot to mention that.

agrawalanjali996 last updated on July 7, 2019, 5:57 p.m.
Enter your answer details below:


Enter your comment details below:




1 Answer(s)

avatar

From what I feel, to get the shortest path ,you have to take the bfs or the a* heuristic as you mentioned. I was thinking of a do solution with the tag you mentioned ,but as the source and destination keep changing , i dont think a dp solution is possible and anyways there is no significance of a dp solution for one source to destination query,i guess.

SHUBHAM_GUPTA1 last updated on July 13, 2019, 5:13 a.m. 1    Reply    Upvote   

Instruction to write good question
  1. 1. Write a title that summarizes the specific problem
  2. 2. Pretend you're talking to a busy colleague
  3. 3. Spelling, grammar and punctuation are important!

Bad: C# Math Confusion
Good: Why does using float instead of int give me different results when all of my inputs are integers?
Bad: [php] session doubt
Good: How can I redirect users to different pages based on session data in PHP?
Bad: android if else problems
Good: Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.