Answers.Body: <p><a href="http://books.google.de/books?id=QxX2CX5OVMsC&amp;pg=PA337&amp;lpg=PA337&amp;dq=knight%20metric&amp;source=bl&amp;ots=3J5nDWweOY&amp;sig=_-pQwRWZrh0fI9SHzmkxlCb-Xcc&amp;hl=de&amp;sa=X&amp;ei=-FkoU6WaLen8ywOjgoHoDg&amp;ved=0CDIQ6AEwAA#v=onepage&amp;q=knight%20metric&amp;f=false" rel="nofollow">It's well documented.</a></p>
  
  <p>It's actually a fairly boring metric. The only special cases are the squares next to the knight and the squares on the same diagonal that are two squares away. In all other cases, quite regular.</p>
  
  <p>If you mean with other pieces on the board, you get a <a href="https://en.wikipedia.org/wiki/Shortest_path_problem" rel="nofollow">shortest path problem</a> which is related to the Travelling Salesman Problem but is soluble in polynomial time.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-03-19T14:01:59.323Z
Answers.Text: This does not really answer my question. My question is on how a human player compute the shortest path (without or with other pieces on the board). Your answer is about how a computer would answer the question. I might be wrong but I don't think that a human chess player build the graph in order to search for a path. Beside, I don't think that the shortest path with other pieces relates to a Travelling Salesman problem. I think that even in this case it should be a Breadth-first search, so it is far less complex than the travelling salesman.
Answers.UserDisplayName: pim999
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-03-19T15:43:08.957Z
Answers.Text: Well, in your head, you're building graphsto find out by basically doing breadth-first. There's quite a bit of intuition connected to it, of course. If this is what you are aiming at, I may change the answer.
Answers.UserDisplayName: chaosflaws
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-03-19T01:47:03.847Z
Answers.LastActivityDate: 2014-03-19T01:47:03.847Z
Answers.UserDisplayName: chaosflaws
Answers.Body: <p>I know this is a super old question. I made a program that outputs all the positions a knight can be relative to starting position within six moves(which happens to be the maximum number of moves needed to get anywhere) </p>
  
  <pre><code>0: (0, 0) 
  1: (2, 1) 
  2: (2, 0) (3, 3) (4, 2) (3, 1) (1, 1) (4, 0) 
  3: (3, 2) (5, 4) (4, 1) (3, 0) (6, 1) (6, 3) (4, 3) (5, 0) (1, 0) (5, 2) 
  4: (7, 3) (6, 4) (5, 5) (6, 6) (7, 1) (4, 4) (6, 0) (6, 2) (7, 5) (2, 2) (5, 1) (5, 3) 
  5: (7, 4) (6, 5) (7, 0) (7, 6) (7, 2) 
  6: (7, 7)
  </code></pre>
  
  <p>Number on the left is turn number, and the list on the right corresponds to all the positions the knight can be in with duplicate positions removed (we don't care that you can go back to your starting position for example, these are the shortest paths to each of these positions). Also, no negative numbers are represented. For example 2,1 -2,1, 2,-1 and -2,-1 are all considered the same position. Also the biggest number is always shown first. For example (4,2) means the night can move 4 spaces in some direction, and then 2 in an orthogonal direction. </p>
  
  <p>One more caveat is that these numbers are the theoretical minimum with no pieces in the way, and a theoretical infinite plane to work with. That is, to achieve this could potentially require moves that exit the game board and come back. I think it only requires exiting in rare cases. For example, if you're in a corner of a board and want to move 1,1 toward the center, the 2 moves that should be able to do this require you going out of bounds first. </p>
  
  <p>Memorizing this is probably not that useful, but there's some interesting takeaways that may be worth noting. </p>
  
  <p>For example, it takes a whole 3 moves to move a knight 1 square forward. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-24T19:28:30.300Z
Answers.LastActivityDate: 2020-01-24T19:43:02.230Z
Answers.LastEditDate: 2020-01-24T19:43:02.230Z
Answers.UserDisplayName: Cruncher
Answers.Body: <p>To me the easy human way it is to start from the square that you want to go to (backtracking approach), lets call it 'A' and exclude from the path calculation the direct linked paths from 'A' that you can't go to because they are attack or there is a piece on it. </p>
  
  <p>For example, you want to go to the <strong>square c4</strong>, so the directed linked paths will be from by <code>a5</code>, <code>a3</code>, <code>b2</code>, <code>d2</code>, <code>e3</code>, <code>e5</code>, <code>d6</code> and <code>b6</code>, but if only the square <code>a5</code> and <code>b6</code> are available you can reduce your calculation to only to 2 paths now. Furthermore, if you use this "technique" you can check if the target square is reachable at all (if have at least 1 directed linked path not being occupied or attacked).</p>
  
  <p>After doing that, you go to the position where you knight stands and you check which are the squares that you can go to. Using this two phase approach you reduce you tree of calculation immensely.</p>
  
  <p>You should also know beforehand how many moves you need to go from one square to another with your knight, in order to avoid the calculation of larger paths than the ones really need it. I din't check online to find any heuristic for this but I can give you some inside tips about it:</p>
  
  <ul>
  <li>The Knight on a black square can only go to a white square and vise-versa, in the next move;</li>
  <li>Every square on the diagonal of the actual square of the Knight can be reach in only two moves. Square <code>(x,y)</code> to the squares
  <code>(x-1,y+1)</code>, <code>(x+1,y+1)</code>, <code>(x+1,y-1)</code> and <code>(x-1,y-1)</code> takes <strong>2
  moves</strong>;</li>
  <li>The squares up, above, right and left of the actual square takes <strong>3 moves</strong>;</li>
  <li>Every square on the diagonal of the actual square with a one square between them (e.g actual  square = c4, target square a6),
  takes <strong>4 moves</strong>.</li>
  <li>Every square on the diagonal of the actual square with a 2 squares between them (e.g actual  square = c4, target square f7), takes only
  <strong>2 moves</strong>.</li>
  </ul>
  
  <p>Finally, if you are in a given color square you will take a <strong>odd number of moves</strong> to reach the <strong>opposite color</strong> square. If the target square have the same color as the square that you are in now it will take a <strong>even number of moves</strong>.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-03-23T20:45:30.883Z
Answers.LastActivityDate: 2014-03-23T23:09:18.200Z
Answers.LastEditDate: 2014-03-23T23:09:18.200Z
Answers.UserDisplayName: dreamcrash
Body: <p>Is there a practical way of computing the shortest path from a square to another, for a knight? (for a human chess player, not for a computer)</p>
  
  <p>Usually, when I want to send my knight from a square to another, I try to find a path with a rather empirical way. "OK, to get there, I should go here or here... But this square is attacked, so I can only go here..." and so on. Is there a more straightforward approach?</p>
  
  <p>Thanks in advance.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-01-25T00:16:30.743Z
Comments.Text: If it's long enough to be nontrivial, it's probably a waste of moves, and the board will change by the time it gets there. Spending several moves developing one piece is generally not a good idea (although of course there are exceptions).
Comments.UserDisplayName: Acccumulation
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2014-03-18T21:48:41.927Z
Comments.Text: http://stackoverflow.com/questions/2339101/knights-shortest-path-chess-question
Comments.UserDisplayName: Dag Oskar Madsen
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2014-03-19T14:06:24.843Z
Comments.Text: Thanks but it does not answer my question. My question is about human players, not algorithms. I don't think that the human player build the graph in his head!
Comments.UserDisplayName: pim999
Tags: <knights><beginner>
Title: Shortest path for a knight
ThreadText: # Shortest path for a knight
  
  (Asked by: username_0 on 2014-03-18)
  
  Is there a practical way of computing the shortest path from a square to another, for a knight? (for a human chess player, not for a computer)
  
  Usually, when I want to send my knight from a square to another, I try to find a path with a rather empirical way. "OK, to get there, I should go here or here... But this square is attacked, so I can only go here..." and so on. Is there a more straightforward approach?
  
  Thanks in advance.
  
  **Tags:** knights, beginner
  
  > **Comments:**
  > **username_2**: http://stackoverflow.com/questions/2339101/knights-shortest-path-chess-question  
  > **username_0**: Thanks but it does not answer my question. My question is about human players, not algorithms. I don't think that the human player build the graph in his head!  
  > **username_1**: If it's long enough to be nontrivial, it's probably a waste of moves, and the board will change by the time it gets there. Spending several moves developing one piece is generally not a good idea (although of course there are exceptions).  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_5 on 2014-03-23. Score: 9 | Accepted answer
  
  To me the easy human way it is to start from the square that you want to go to (backtracking approach), lets call it 'A' and exclude from the path calculation the direct linked paths from 'A' that you can't go to because they are attack or there is a piece on it.
  
  For example, you want to go to the **square c4**, so the directed linked paths will be from by `a5`, `a3`, `b2`, `d2`, `e3`, `e5`, `d6` and `b6`, but if only the square `a5` and `b6` are available you can reduce your calculation to only to 2 paths now. Furthermore, if you use this "technique" you can check if the target square is reachable at all (if have at least 1 directed linked path not being occupied or attacked).
  
  After doing that, you go to the position where you knight stands and you check which are the squares that you can go to. Using this two phase approach you reduce you tree of calculation immensely.
  
  You should also know beforehand how many moves you need to go from one square to another with your knight, in order to avoid the calculation of larger paths than the ones really need it. I din't check online to find any heuristic for this but I can give you some inside tips about it:
  
  * The Knight on a black square can only go to a white square and vise-versa, in the next move;
  * Every square on the diagonal of the actual square of the Knight can be reach in only two moves. Square `(x,y)` to the squares
    `(x-1,y+1)`, `(x+1,y+1)`, `(x+1,y-1)` and `(x-1,y-1)` takes **2
    moves**;
  * The squares up, above, right and left of the actual square takes **3 moves**;
  * Every square on the diagonal of the actual square with a one square between them (e.g actual square = c4, target square a6),
    takes **4 moves**.
  * Every square on the diagonal of the actual square with a 2 squares between them (e.g actual square = c4, target square f7), takes only
    **2 moves**.
  
  Finally, if you are in a given color square you will take a **odd number of moves** to reach the **opposite color** square. If the target square have the same color as the square that you are in now it will take a **even number of moves**.
  
  
  ---
  
  ### Answer by username_3 on 2014-03-19. Score: 3
  
  [It's well documented.](http://books.google.de/books?id=QxX2CX5OVMsC&pg=PA337&lpg=PA337&dq=knight%20metric&source=bl&ots=3J5nDWweOY&sig=_-pQwRWZrh0fI9SHzmkxlCb-Xcc&hl=de&sa=X&ei=-FkoU6WaLen8ywOjgoHoDg&ved=0CDIQ6AEwAA#v=onepage&q=knight%20metric&f=false)
  
  It's actually a fairly boring metric. The only special cases are the squares next to the knight and the squares on the same diagonal that are two squares away. In all other cases, quite regular.
  
  If you mean with other pieces on the board, you get a [shortest path problem](https://en.wikipedia.org/wiki/Shortest_path_problem) which is related to the Travelling Salesman Problem but is soluble in polynomial time.
  
  > **Comments:**
  > **username_0**: This does not really answer my question. My question is on how a human player compute the shortest path (without or with other pieces on the board). Your answer is about how a computer would answer the question. I might be wrong but I don't think that a human chess player build the graph in order to search for a path. Beside, I don't think that the shortest path with other pieces relates to a Travelling Salesman problem. I think that even in this case it should be a Breadth-first search, so it is far less complex than the travelling salesman.  
  > **username_3**: Well, in your head, you're building graphsto find out by basically doing breadth-first. There's quite a bit of intuition connected to it, of course. If this is what you are aiming at, I may change the answer.  
  
  ---
  
  ### Answer by username_4 on 2020-01-24. Score: 1
  
  I know this is a super old question. I made a program that outputs all the positions a knight can be relative to starting position within six moves(which happens to be the maximum number of moves needed to get anywhere)
  
  ```
  0: (0, 0) 
  1: (2, 1) 
  2: (2, 0) (3, 3) (4, 2) (3, 1) (1, 1) (4, 0) 
  3: (3, 2) (5, 4) (4, 1) (3, 0) (6, 1) (6, 3) (4, 3) (5, 0) (1, 0) (5, 2) 
  4: (7, 3) (6, 4) (5, 5) (6, 6) (7, 1) (4, 4) (6, 0) (6, 2) (7, 5) (2, 2) (5, 1) (5, 3) 
  5: (7, 4) (6, 5) (7, 0) (7, 6) (7, 2) 
  6: (7, 7)
  
  ```
  
  Number on the left is turn number, and the list on the right corresponds to all the positions the knight can be in with duplicate positions removed (we don't care that you can go back to your starting position for example, these are the shortest paths to each of these positions). Also, no negative numbers are represented. For example 2,1 -2,1, 2,-1 and -2,-1 are all considered the same position. Also the biggest number is always shown first. For example (4,2) means the night can move 4 spaces in some direction, and then 2 in an orthogonal direction.
  
  One more caveat is that these numbers are the theoretical minimum with no pieces in the way, and a theoretical infinite plane to work with. That is, to achieve this could potentially require moves that exit the game board and come back. I think it only requires exiting in rare cases. For example, if you're in a corner of a board and want to move 1,1 toward the center, the 2 moves that should be able to do this require you going out of bounds first.
  
  Memorizing this is probably not that useful, but there's some interesting takeaways that may be worth noting.
  
  For example, it takes a whole 3 moves to move a knight 1 square forward.
  
  
  ---
  
  