Knight’s Shortest Path on Chessboard

by

EDIT: See simon’s answer, where he fixed the formula presented here.

Actually there is an O(1) formula

This is an image that I’ve made to visualize it ( Squares a knight can reach on Nth move are painted with same color ).
Knight's Move

Can you notice the pattern here?

Although we can see the pattern, it is really hard to find the function f( x , y ) that returns the number of moves required to go from square ( 0 , 0 ) to square ( x , y )

But here is the formula that works when 0 <= y <= x

int f( int x , int y )
{
    int delta = x - y;

    if( y > delta )
        return 2 * ( ( y - delta ) / 3 ) + delta;
    else
        return delta - 2 * ( ( delta - y ) / 4 );
}

Note: This question was asked on SACO 2007 Day 1
And solutions are here

More Related Contents:

  1. shortest path from A to B without superfluous edges (in Java) [closed]
  2. Why doesn’t Dijkstra’s algorithm work for negative weight edges?
  3. Negative weights using Dijkstra’s Algorithm
  4. Drawing in JLayeredPane over exising JPanels
  5. Does adding a JLabel to a JPanel “hide” the JPanel?
  6. Finding all the shortest paths between two nodes in unweighted undirected graph
  7. How to draw a chessboard with Pygame and move the pieces on the board?
  8. The best shortest path algorithm
  9. Shortest path to transform one word into another
  10. R optimization with equality and inequality constraints
  11. Complete graph with only two possible costs. What’s the shortest path’s cost from 0 to N – 1
  12. Is there an effiecient way of making a function to drag and drop multiple png’s?
  13. How does a Breadth-First Search work when looking for Shortest Path?

Leave a Comment