CareerCup

1) Build a graph of (NxN) vertices that there exist an edge (v->w) if the knight can move from v to w. The maximum order of a vertices is 8 so the maximum number of edge is 8xNxN.
We perform the BFS from the source to find
- If the destination is reachable from the source
- if there're a path, then BFS give the minimum number of hops

Node : there're no need to build the graph explicitly we only want to do the BFS on the implicit graph.

2. I believe for infinite chess board all the positions are reachable so
- the solution is not extendable if the destination is unreachable from the source
- Otherwise, the solution on the infinite chess board is at least as good as NxN that gives us the upper bound for the search on the infinite chess board. Again we can rerun the BFS with the bound from the previous step to check if we can find a better solution.

I think you should use BFS rather DFS as BFS will find min no.of hops

A* for question 2

For 2), I want to place the piece at (inf, inf)
and I want to know the hops for it to reach (-inf, inf).

This pseudocode is for the case of a board of -infinity to + infinity
it also works for n>2 except for the corner cases (which need additional conditions)
Requirement - board origin = 0,0

int hops;
int quotient = (abs(p-x) + abs(q-y))/3;
int remainder = (abs(p-x) + abs(q-y))%3;

int adjustment = 0
if (remainder == 1) then adjustment = 3;
else if (remainder ==2) then adjustment = 2;

hops = quotient + adjustment;

-- validated the above with http :// tacticstime . com/wp-content/uploads/2011/09/chess_knight_all.png
-- There seems to be some cases when x=p or y=q that this does not give the least hops (eg. (x,y)=(0,0) and (p,q) = (4,0), so some additional conditions needed there as well.

Isnt it (N-x)? Knight is already at position x. (N-x)=p

The A* Algorithm would work here, I think. For each of the squares you can reach from the start position, get the linear distance to the goal and add 1. Select the square where this value is the smallest and repeat, adding 2 instead of 1. The function for A* is g(x)+h(x), where g(x) is a cost function (here, merely a number of moves) and h(x) is a heuristic function (we decided on linear distance to the goal) for a square x.

Why not use BFS even on an infinite board? You don't need to construct the graph, you just know what are the neighbors for each field. And even with A* you have growing data structures to maintain.

I think its Recursive DP problem.

do you have a C solution?

rrr