Knight's Shortest Path on Chessboard

Question

I've been practicing for an upcoming programming competition and I have stumbled across a question that I am just completely bewildered at. However, I feel as though it's a concept I should learn now rather than cross my fingers that it never comes up.

Basically, it deals with a knight piece on a chess board. You are given two inputs: starting location and ending location. The goal is to then calculate and print the shortest path that the knight can take to get to the target location.

I've never dealt with shortest-path-esque things, and I don't even know where to start. What logic do I employ to go about tackling this?

P.S. If it's of any relevance, they want you to supplement the knight's normal moves by also allowing it to move to the four corners of the square formed by the (potentially) eight moves a knight can make, given that the center of the square is the knight's location.

Achromatin

Could you clarify the P.S.? You mean, if a knight is on E4, it can move to C2, C6, G2, and G6? – Pudendas

Yes, in addition to it's normal moves. – Achromatin

Here's some mathematical analysis of the problem: math.stackexchange.com/questions/104700/… – Risibility

Answer 1

You have a graph here, where all available moves are connected (value=1), and unavailable moves are disconnected (value=0), the sparse matrix would be like:

(a1,b3)=1,
(a1,c2)=1,
  .....

And the shortest path of two points in a graph can be found using http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Pseudo-code from wikipedia-page:

function Dijkstra(Graph, source):
   for each vertex v in Graph:           // Initializations
       dist[v] := infinity               // Unknown distance function from source to v
       previous[v] := undefined          // Previous node in optimal path from source
   dist[source] := 0                     // Distance from source to source
   Q := the set of all nodes in Graph
   // All nodes in the graph are unoptimized - thus are in Q
   while Q is not empty:                 // The main loop
       u := vertex in Q with smallest dist[]
       if dist[u] = infinity:
          break                         // all remaining vertices are inaccessible from source
       remove u from Q
       for each neighbor v of u:         // where v has not yet been removed from Q.
           alt := dist[u] + dist_between(u, v) 
           if alt < dist[v]:             // Relax (u,v,a)
               dist[v] := alt
               previous[v] := u
   return dist[]

EDIT:

1. as moron, said using the http://en.wikipedia.org/wiki/A*_algorithm can be faster.
2. the fastest way, is to pre-calculate all the distances and save it to a 8x8 full matrix. well, I would call that cheating, and works only because the problem is small. But sometimes competitions will check how fast your program runs.
3. The main point is that if you are preparing for a programming competition, you must know common algorithms including Dijkstra's. A good starting point is reading Introduction to Algorithms ISBN 0-262-03384-4. Or you could try wikipedia, http://en.wikipedia.org/wiki/List_of_algorithms

Mulholland

This seems to be complex compared to Mustafa's solution below. – Laundryman

What do you mean by unavailable move? A knight can reach any square right!? – Kristinkristina

Answer 2

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 N^th move are painted with same color ).

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

Winepress

Any chance you could describe how you worked out that formula? – Benevolent

I didn't derive the formula myself. I found it on the solutions link that I provided on my answer. – Winepress

Does this code work? If a knight is positiona at (0,0) and I want to move it to point (1,0). This satisfies 0 <= y <= x. delta =1-0 = 1. y is not bigger than delta (0<1). This means I am going for the else case. delta - 2 * ( ( delta - y ) / 4 ) = 1-2((1-0)/4)= 1-1/2=1. The is no whay I can move knight from (0,0) to (1,0) in one move. Question is does this algoritm work? Or what am I doing wrong? – Stocktonontees

Seems like it works only for direct possible positions. But if user provides (2,2) it returns 0 and if user provides (4,4) it returns 2 which are wrong. – Kane

In the answers given the algorithm actually uses the floor notation – Billibilliard

It should be 2 * floor((y - delta) / 3) + delta and delta - 2 * floor((delta - y) / 4). This is official solution from this contest page, but it's wrong. This first equation (from if) returns wrong answers. On the chessboard [-1000..1000] x [-1000..1000], which is 2001x2001 big (but logically unlimited), the given answer counts 2,669,329 of 4,004,001 fields correct (66.66%). Anyone knows the working solution without any loops? – Durante

I agree this solution does not work. See other answers such as https://mcmap.net/q/203165/-knight-39-s-shortest-path-on-chessboard for a working O(1) solution. – Annabel

Why did you post answer and didn't check it at simple examples? It doesn't work even at input (1, 1) – Farrar

Answer 3

Here's a correct O(1) solution, but for the case where the knight moves like a chess knight only, and on an infinite chess board:

https://jsfiddle.net/graemian/5qgvr1ba/11/

The key to finding this is to notice the patterns that emerge when you draw the board. In the diagram below, the number in the square is the minimum number of moves needed to reach that square (you can use breadth-first search to find this):

Because the solution is symmetrical across the axes and the diagonals, I've only drawn the x >= 0 and y >= x case.

The bottom-left block is the starting position and the numbers in the blocks represent the minimum number of moves to reach those blocks.

There are 3 patterns to notice:

• The incrementing blue vertical groups of 4
• The "primary" red diagonals (they run top-left to bottom-right, like a backslash)
• The "secondary" green diagonals (same orientation as red)

(Make sure you see both sets of diagonals as top-left to bottom-right. They have a constant move-count. The bottom-left top-right diagonals are much more complex.)

You can derive formulas for each. The yellow blocks are special cases. So the solution becomes:

function getMoveCountO1(x, y) {

    var newXY = simplifyBySymmetry(x, y);

    x = newXY.x;
    y = newXY.y;

    var specialMoveCount = getSpecialCaseMoveCount(x ,y);

    if (specialMoveCount !== undefined)
        return specialMoveCount;

    else if (isVerticalCase(x, y))
        return getVerticalCaseMoveCount(x ,y);

    else if (isPrimaryDiagonalCase(x, y))
        return getPrimaryDiagonalCaseMoveCount(x ,y);

    else if (isSecondaryDiagonalCase(x, y))
        return getSecondaryDiagonalCaseMoveCount(x ,y);

}

with the hardest being the vertical groups:

function isVerticalCase(x, y) {

    return y >= 2 * x;

}

function getVerticalCaseMoveCount(x, y) {

    var normalizedHeight = getNormalizedHeightForVerticalGroupCase(x, y);

    var groupIndex = Math.floor( normalizedHeight / 4);

    var groupStartMoveCount = groupIndex * 2 + x;

    return groupStartMoveCount + getIndexInVerticalGroup(x, y);

}

function getIndexInVerticalGroup(x, y) {

    return getNormalizedHeightForVerticalGroupCase(x, y) % 4;

}

function getYOffsetForVerticalGroupCase(x) {

    return x * 2;

}

function getNormalizedHeightForVerticalGroupCase(x, y) {

    return y - getYOffsetForVerticalGroupCase(x);

}

See the fiddle for the other cases.

Maybe there are simpler or more elegant patterns I missed? If so, I would love to see them. In particular, I notice some diagonal patterns in the blue vertical cases, but I haven't explored them. Regardless, this solution still satisfies the O(1) constraint.

Risibility

This doesn't seem to handle the (literal) corner cases. If the "0" is the lower left square on the board (a1), then you can not get to the nearest "2" space (b2) in two moves. Because to do so your first move would have to be to the non-existent space to the left of (a3). – Aisha

Right, I changed my answer to include the infinite chess board assumption – Risibility

@JonatasWalker Please explain, I don't see a problem going from (8,0) to (0,0). It takes 4 moves? – Risibility

Sorry @GraemePyle, my fault, removing my comment. – Schapira

hi @GraemePyle - I agree with you this is the best overall programming approach. Great diagram by the way! – Christo

Answer 4

Very interesting problem which I was encountered recently. After looking some solutions I was tried to recover analytic formula (O(1) time and space complexity) given on SACO 2007 Day 1 solutions.

First of all I want to appreciate Graeme Pyle for very nice visualization which helped me to fix formula.

For some reason (maybe for simplification or beauty or just a mistake) they moved minus sign into floor operator, as a result they have got wrong formula floor(-a) != -floor(a) for any a.

Here is the correct analytic formula:

var delta = x-y;
if (y > delta) {
    return delta - 2*Math.floor((delta-y)/3);
} else {
    return delta - 2*Math.floor((delta-y)/4);
}

The formula works for all (x,y) pairs (after applying axes and diagonal symmetry) except (1,0) and (2,2) corner cases, which are not satisfy to pattern and hardcoded in the following snippet:

function distance(x,y){
     // axes symmetry 
     x = Math.abs(x);
     y = Math.abs(y);
     // diagonal symmetry 
     if (x < y) {
        t = x;x = y; y = t;
     }
     // 2 corner cases
     if(x==1 && y == 0){
        return 3;
     }
     if(x==2 && y == 2){
        return 4;
     }
    
    // main formula
    var delta = x-y;
		if(y>delta){
  		return delta - 2*Math.floor((delta-y)/3);
  	}
  	else{
  		return delta - 2*Math.floor((delta-y)/4);
  	}
}


$body = $("body");
var html = "";
for (var y = 20; y >= 0; y--){
	html += '<tr>';
	for (var x = 0; x <= 20; x++){
  	html += '<td style="width:20px; border: 1px solid #cecece" id="'+x+'_'+y+'">'+distance(x,y)+'</td>';
  }
  html += '</tr>';
}

html = '<table>'+html+'</table>';
$body.append(html);

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

Note: The jQuery used for only illustration, for code see distance function.

Projectionist

@OlegAbrazhaev The "distance" function is an analytical function and can compute number of steps for given (x, y) position in O(1) time. Basically in this formula we don't depend on board (I guess by "infinite board" you mean that property), hence it will work. – Projectionist

@Projectionist Can someone explain the main formula please? I´m finding difficult to be able to explain it with simple words – Cassey

@Cassey - by saying "explain it with simple words" do you mean mathematical proof of formula or something else? – Projectionist

@Projectionist basically I don´t fully understand why if y > delta you divide by 3 and if y < delta you divide by 4 – Cassey

@Cassey If we near y=x line we can decrease x+y by 3 in every move by staying near y=x line. If we near to y=0 line we can decrease x by 2 in every move by staying near y=0 line. That is why we have 2 cases, more precisely here what I mean by saying near to particular line: 1. By near y=x line I mean section restricted by y=x and y=x/2 lines (y>x/2). 2. By near y=0 line I mean section restricted by y=0 and y=x/2 lines (y<x/2). Taking all above mentioned and if we remove Math.floor and simplify main formula we will get following formula: if ( y>x/2 ) then {return (x+y)/3} else { return x/2} – Projectionist

@Projectionist great, that makes it more clear...ty for your time :) – Cassey

just in case, the BAPC2017 contest also had a question named Knight's Marathon on an infinite board that this formula perfectly solves it. 2017.bapc.eu/files/preliminaries_problems.pdf – Thalweg

landed from leetcode to here, your visualization deserve +1 – Equation

Answer 5

Yes, Dijkstra and BFS will get you the answer, but I think the chess context of this problem provides knowledge that can yield a solution that is much faster than a generic shortest-path algorithm, especially on an infinite chess board.

For simplicity, let's describe the chess board as the (x,y) plane. The goal is to find the shortest path from (x0,y0) to (x1,y1) using only the candidate steps (+-1, +-2), (+-2, +-1), and (+-2, +-2), as described in the question's P.S.

Here is the new observation: draw a square with corners (x-4,y-4), (x-4,y+4), (x+4,y-4), (x+4,y+4). This set (call it S4) contains 32 points. The shortest path from any of these 32 points to (x,y) requires exactly two moves.

The shortest path from any of the 24 points in the set S3 (defined similarly) to (x,y) requires at least two moves.

Therefore, if |x1-x0|>4 or |y1-y0|>4, the shortest path from (x0,y0) to (x1,y1) is exactly two moves greater than the shortest path from (x0,y0) to S4. And the latter problem can be solved quickly with straightforward iteration.

Let N = max(|x1-x0|,|y1-y0|). If N>=4, then the shortest path from (x0,y0) to (x1,y1) has ceil(N/2) steps.

Pudendas

Is it just me who is confused about this answer? "draw a square with corners (x-4,y-4), (x-4,y+4), (x+4,y-4), (x+4,y+4). This set (call it S4) contains 32 points". No it doesn't, it contains 81 as it's a 9x9 square? Also, "Let N = max(|x1-x0|,|y1-y0|). If N>=4, then the shortest path from (x0,y0) to (x1,y1) has ceil(N/2) steps." That's not true, take for example x0=0, y0=0, x1=4, y1=4, the shortest path is 4, not 2 like that formula suggests. – Choanocyte

(1) The set only refers to the points on the boundary of the square itself. That has 32 points/locations. (2) When you take into account the poster's P.S. about supplementary moves (also see the comments in the original post), the minimum number of moves becomes two. – Pudendas

Thanks, that makes sense now :) – Choanocyte

what if a board is infinite? in this case only BFS will work well – Bootie

@SteveTjoa sorry, I can't understand why you mentioned (+-2, +-2) move, as it's impossible for a knight – Rosettarosette

Answer 6

The O(1) answer above [https://mcmap.net/q/203165/-knight-39-s-shortest-path-on-chessboard by Mustafa Serdar Şanlı] isn't really working. (Check (1,1) or (3,2) or (4,4), aside for the obvious edge cases of (1,0) or (2,2)).

Below is a much uglier solution (python), which does work (with added "tests"):

def solve(x,y):
        x = abs(x)
        y = abs(y)
        if y > x:
            temp=y
            y=x
            x=temp  
        if (x==2 and y==2):
            return 4
        if (x==1 and y==0):
            return 3

    if(y == 0 or float(y) / float(x) <= 0.5):
        xClass = x % 4
        if (xClass == 0):
            initX = x/2
        elif(xClass == 1):
            initX = 1 + (x/2)
        elif(xClass == 2):
            initX = 1 + (x/2)
        else:
            initX = 1 + ((x+1)/2)

        if (xClass > 1):
            return initX - (y%2)
        else:
            return initX + (y%2)
    else:
        diagonal = x - ((x-y)/2)
        if((x-y)%2 == 0):
            if (diagonal % 3 == 0):
                return (diagonal/3)*2
            if (diagonal % 3 == 1):
                return ((diagonal/3)*2)+2
            else:
                return ((diagonal/3)*2)+2
        else:
            return ((diagonal/3)*2)+1


def test():
    real=[
    [0,3,2,3,2,3,4,5,4,5,6,7,6,7],
    [3,2,1,2,3,4,3,4,5,6,5,6,7,8],
    [2,1,4,3,2,3,4,5,4,5,6,7,6,7],
    [3,2,3,2,3,4,3,4,5,6,5,6,7,8],
    [2,3,2,3,4,3,4,5,4,5,6,7,6,7],
    [3,4,3,4,3,4,5,4,5,6,5,6,7,8],
    [4,3,4,3,4,5,4,5,6,5,6,7,6,7],
    [5,4,5,4,5,4,5,6,5,6,7,6,7,8],
    [4,5,4,5,4,5,6,5,6,7,6,7,8,7],
    [5,6,5,6,5,6,5,6,7,6,7,8,7,8],
    [6,5,6,5,6,5,6,7,6,7,8,7,8,9],
    [7,6,7,6,7,6,7,6,7,8,7,8,9,8]]

    for x in range(12):
        for y in range(12):
            res = solve(x,y)
            if res!= real[x][y]:
                print (x, y), "failed, and returned", res, "rather than", real[x][y]
            else:
               print (x, y), "worked. Cool!"

test()

Prosecution

Referring to answers as above or below does not really work on SO. – Bollen

Here is my version in python 2/3. I've tried to simplify the solve function but it's not easy! gist.github.com/TimSC/8b9a80033f3a22a708a4b9741931c591 – Annabel

Answer 7

What you need to do is think of the possible moves of the knight as a graph, where every position on the board is a node and the possible moves to other position as an edge. There is no need for dijkstra's algorithm, because every edge has the same weight or distance (they are all just as easy or short to do). You can just do a BFS search from your starting point until you reach the end position.

Carper

+!, for this specific problem BFS is enough. – Mulholland

BFS could be enough, but a plain BST will blow up for many queries - you will need to cache which squares you have visited. And then BFS starts looking a bit like Dijkstra's algorithm... – Tinderbox

What would be the best way to track all the position we have already travelled so that the BFS tree only grows forward and when we discover nodes availaible from the a new point, we dont end up adding the older node again..and getting stuck in an infinite loop! – Bosquet

I here suppose that we can just do by storing our last knight position? – Bosquet

Answer 8

Solution from first principles in Python

I first encountered this problem in a Codility test. They gave me 30 minutes to solve it - it took me considerably longer than that to get to this result! The problem was: how many moves does it take for a knight to go from 0,0 to x,y using only legal Knight's moves. x and y were more-or-less unbounded (so we're not talking here about a simple 8x8 chessboard).

They wanted an O(1) solution. I wanted a solution where the program was clearly solving the problem (i.e. I wanted something more obviously right than Graeme's pattern - patterns have a habit of breaking down where you're not looking), and I really wanted not to have to rely on an unargued formula, as in Mustafa's solution

So, here's my solution, for what it's worth. Start, as others have, by noting the solution is symmetrical about the axes and diagonals, so we need to solve only for 0 >= y >= x. For simplicity of explanation (and code) I'm going to reverse the problem: the knight starts at x,y, and is aiming for 0,0.

Let's suppose we shrink the problem down to the vicinity of the origin. We'll get to what 'vicinty' actually means in due course, but for now, let's just write some solutions down in a cheatsheet (origin at bottom left):

2 1 4 3
3 2 1 2
0 3 2 3

So, given x,y on the grid, we can just read off the number of moves to the origin.

If we've started outside the grid, we have to work our way back to it. We introduce the 'midline', which is the line represented by y=x/2. Any knight at x,y on that line can work its way back to the cheatsheet using a series of 8 o'clock moves (that is: (-2,-1) moves). If x,y lies above the midline, then we'll need a succession of 8 o'clock and 7 o'clock moves, and if it lies below the midline, we'll need a succession of 8 o'clock and 10 o'clock moves. Two things to note here:

• These sequences are provably shortest paths. (Want me to prove it, or is it obvious?)
• We care only about the number of such moves. We can mix-and-match the moves in any order.

So, let's look at the above-midline moves. What we are claiming is that:

• (dx;dy) = (2,1 ; 1,2) (n8; n7) (matrix notation, without math typesetting - column vector (dx;dy) equals the square matrix multiplied by column vector (n8;n7) - the number of 8 o'clock moves and the number of 7 o'clock moves), and similarly;

• (dx;dy) = (2,2; 1,-1) (n8; n10)

I'm claiming that dx,dy will be roughly (x,y), so (x-dx, y-dy) will be in the vicinity of the origin (whatever 'vicinity' turns out to be).

The two lines in the code which compute these terms are the solution to these, but they're selected to have some useful properties:

• The above-midline formula moves (x,y) to one of (0,0), (1,1), or (2,2).
• The below-midline formula moves (x,y) to one of (0,0), (1,0), (2,0), or (1,1).

(Would you like proofs of these?) So, the Knight's distance will be the sum of n7, n8, n10 and cheatsheet [x-dx, y-dy], and our cheatsheet reduces to this:

. . 4
. 2 .
0 3 2

Now, this isn't quite the end of the story. Look at the 3 on the bottom row. The only ways we can reach this are either:

• We started there, or
• We moved there, by a sequence of 8 o'clock and 10 o'clock moves. But if the last move was an 8 o'clock (which it's entitled to be, since we can make our moves in any order), then we must have passed through (3,1), whose distance is actually 2 (as you can see from the original cheatsheet). So what we should do is back-track one 8 o'clock move, saving two moves in total.

There's a similar optimisation to be had with the 4 at top right. Apart from starting there, the only way to reach that is by an 8 o'clock move from (4,3). That's not on the cheatsheet, but if it were there, its distance would be 3, because we could have 7 o'clocked to (3,1) instead, which has a distance of only 2. So, we should back-track one 8-o'clock move, and then go forward one 7-o'clock.

So, we need to add one more number to the cheatsheet:

. . 4
. 2 . 2
0 3 2

(Note: there are a whole load of back-tracking optimisations from (0,1) and (0,2) but since the solver will never take us there, we don't need to worry about them.)

So here, then, is some Python code to evaluate this:

def knightDistance (x, y):
    # normalise the coordinates
    x, y = abs(x), abs(y)
    if (x<y): x, y = y, x
    # now 0 <= y <= x

    # n8 means (-2,-1) (8 o'clock), n7 means (-1,-2) (7 o'clock), n10 means (-2,+1) (10 o'clock)
    if (x>2*y):
        # we're below the midline.  Using 8- & 10-o'clock moves
        n7, n8, n10 = 0,  (x + 2*y)//4,  (x - 2*y + 1)//4
    else:
        # we're above the midline.  Using 7- and 8-o'clock moves
        n7, n8, n10 = (2*y - x)//3, (2*x - y)//3,  0
    x -= 2*n8 + n7 + 2*n10
    y -= n8 + 2*n7 - n10
    # now 0<=x<=2, and y <= x.  Also (x,y) != (2,1)

    # Try to optimise the paths.
    if (x, y)==(1, 0): # hit the  3.  Did we need to?
        if (n8>0): # could have passed through the 2 at 3,1.  Back-up
            x, y = 3, 1; n8-=1;
    if (x, y)==(2, 2): # hit the 4.  Did we need to?
        if (n8>0): # could have passed through a 3 at 4,3.  Back-up, and take 7 o'clock to 2 at 3,1
            x, y = 3, 1; n8-=1; n7+=1

    # Almost there.  Now look up the final leg
    cheatsheet = [[0, 3, 2], [2, None, 2], [4]]
    return n7 + n8 + n10 + cheatsheet [y][x-y]

Incidentally, if you want to know an actual route, then this algorithm provides that too: it is simply a succession of n7 7-o'clock moves, followed by (or interspersed with) n8 8-o'clock moves, n10 10-o'clock moves, and whatever dance is dictated by the cheatsheet (which, itself, can be in a cheatsheet).

Now: How to prove this is right. It's not enough just to compare these results with a table of right answers, because the problem itself is unbounded. But we can say that, if the Knight's distance of a square s is d, then if {m} is the set of legal moves from s, the Knight's distance of (s+m) must be either d-1 or d+1 for all m. (Do you need a proof of this?) Furthermore, there must be at least one such square whose distance is d-1, unless s is the origin. So, we can prove correctness by showing this property holds for every square. Thus:

def validate (n):

    def isSquareReasonable (x, y):
        d, downhills = knightDistance (x, y), 0
        moves = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1,  2)]
        for dx, dy in moves:
            dd = knightDistance (x+dx,  y+dy)
            if (dd == d+1): pass
            elif (dd== d-1): downhills += 1
            else: return False;
        return (downhills>0) or (d==0)

    for x in range (0,  n+1):
        for y in range (0,  n+1):
            if not isSquareReasonable (x,  y): raise RuntimeError ("Validation failed")

Alternatively, we can prove the correctness of any one square s by chasing the route from s downhill to the origin. First, check s for reasonableness as above, then select any s+m such that distance (s+m) == d-1. Repeat until we reach the origin.

Howzat?

Lyre

Answer 9

/*
This program takes two sets of cordinates on a 8*8 chessboard, representing the
starting and ending points of a knight's path.
The problem is to print the cordinates that the knight traverses in between, following
the shortest path it can take.
Normally this program is to be implemented using the Djikstra's algorithm(using graphs)
but can also be implemented using the array method.
NOTE:Between 2 points there may be more than one shortest path. This program prints
only one of them.
*/

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

int m1=0,m2=0;

/*
This array contains three columns and 37 rows:
The rows signify the possible coordinate differences.
The columns 1 and 2 contains the possible permutations of the row and column difference 
between two positions on a chess board;
The column 3 contains the minimum number of steps involved in traversing the knight's 
path with the given permutation*/

int arr[37][3]={{0,0,0},{0,1,3},{0,2,2},{0,3,3},{0,4,2},{0,5,3},{0,6,4},{0,7,5},    {1,1,2},{1,2,1},{1,3,2},{1,4,3},{1,5,4},{1,6,3},{1,7,4},{2,2,4},{2,3,3},{2,4,2},
            {2,5,3},{2,6,3},{2,7,5},{3,3,2},{3,4,3},{3,5,4},{3,6,3},{3,7,4},{4,4,4},{4,5,3},{4,6,4},{4,7,5},{5,5,4},{5,6,5},{5,7,4},{6,6,5},{6,7,5},{7,7,6}};

void printMoves(int,int,int,int,int,int);
void futrLegalMove(int,int,int,int);
main()
{
  printf("KNIGHT'S SHORTEST PATH ON A 8*8 CHESSBOARD :\n");
  printf("------------------------------------------");
  printf("\nThe chessboard may be treated as a 8*8 array here i.e. the (1,1) ");
  printf("\non chessboard is to be referred as (0,0) here and same for (8,8) ");
  printf("\nwhich is to be referred as (7,7) and likewise.\n");
  int ix,iy,fx,fy;
  printf("\nEnter the initial position of the knight :\n");
  scanf("%d%d",&ix,&iy);
  printf("\nEnter the final position to be reached :\n");
  scanf("%d%d",&fx,&fy);
  int px=ix,py=iy;
  int temp;
  int tx,ty;
  printf("\nThe Knight's shortest path is given by :\n\n");
  printf("(%d, %d)",ix,iy);
  futrLegalMove(px,py,m1,m2);
  printMoves(px,py,fx,fy,m1,m2);
   getch();
} 

/*
  This method checkSteps() checks the minimum number of steps involved from current
  position(a & b) to final position(c & d) by looking up in the array arr[][].
*/

int checkSteps(int a,int b,int c,int d)
{  
    int xdiff, ydiff;
    int i, j;
    if(c>a)
        xdiff=c-a;
    else
        xdiff=a-c;
    if(d>b)
        ydiff=d-b;
    else
        ydiff=b-d;
    for(i=0;i<37;i++)
        {
            if(((xdiff==arr[i][0])&&(ydiff==arr[i][1])) || ((xdiff==arr[i][1])&& (ydiff==arr[i] [0])))
            {
                j=arr[i][2];break;
            }
        }

        return j;
}   

/*
This method printMoves() prints all the moves involved.
*/

void printMoves(int px,int py, int fx, int fy,int a,int b)
{    
 int temp;
 int tx,ty;
 int t1,t2;
  while(!((px==fx) && (py==fy)))
  {   
      printf(" --> ");
      temp=checkSteps(px+a,py+b,fx,fy);
      tx=px+a;
      ty=py+b;
      if(!(a==2 && b==1))
      {if((checkSteps(px+2,py+1,fx,fy)<temp) && checkMove(px+2,py+1))
      {temp=checkSteps(px+2,py+1,fx,fy);
       tx=px+2;ty=py+1;}}
      if(!(a==2 && b==-1))
      {if((checkSteps(px+2,py-1,fx,fy)<temp) && checkMove(px+2,py-1))
      {temp=checkSteps(px+2,py-1,fx,fy);
       tx=px+2;ty=py-1;}}
      if(!(a==-2 && b==1))
      {if((checkSteps(px-2,py+1,fx,fy)<temp) && checkMove(px-2,py+1))
      {temp=checkSteps(px-2,py+1,fx,fy);
       tx=px-2;ty=py+1;}}
      if(!(a==-2 && b==-1))
      {if((checkSteps(px-2,py-1,fx,fy)<temp) && checkMove(px-2,py-1))
      {temp=checkSteps(px-2,py-1,fx,fy);
       tx=px-2;ty=py-1;}}
      if(!(a==1 && b==2))
      {if((checkSteps(px+1,py+2,fx,fy)<temp) && checkMove(px+1,py+2))
      {temp=checkSteps(px+1,py+2,fx,fy);
       tx=px+1;ty=py+2;}}
      if(!(a==1 && b==-2))
      {if((checkSteps(px+1,py-2,fx,fy)<temp) && checkMove(px+1,py-2))
      {temp=checkSteps(px+1,py-2,fx,fy);
       tx=px+1;ty=py-2;}}
      if(!(a==-1 && b==2))
      {if((checkSteps(px-1,py+2,fx,fy)<temp) && checkMove(px-1,py+2))
      {temp=checkSteps(px-1,py+2,fx,fy);
       tx=px-1;ty=py+2;}}
      if(!(a==-1 && b==-2))
      {if((checkSteps(px-1,py-2,fx,fy)<temp) && checkMove(px-1,py-2))
      {temp=checkSteps(px-1,py-2,fx,fy);
       tx=px-1;ty=py-2;}}
       t1=tx-px;//the step taken in the current move in the x direction.
       t2=ty-py;//" " " " " " " " " " " " " " " " " " " " " y " " " " ".
       px=tx;
       py=ty;
       printf("(%d, %d)",px,py);
       futrLegalMove(px,py,t1,t2);
       a=m1;
       b=m2;
   }

} 

/*
The method checkMove() checks whether the move in consideration is beyond the scope of
board or not.
*/   

int checkMove(int a, int b)
{
    if(a>7 || b>7 || a<0 || b<0)
        return 0;
    else
        return 1;
}

/*Out of the 8 possible moves, this function futrLegalMove() sets the valid move by
  applying the following constraints
      1. The next move should not be beyond the scope of the board.
      2. The next move should not be the exact opposite of the previous move.
  The 1st constraint is checked by sending all possible moves to the checkMove() 
  method;
  The 2nd constraint is checked by passing as parameters(i.e. a and b) the steps of the 
  previous move and checking whether or not it is the exact opposite of the current move.
*/

void futrLegalMove(int px,int py,int a,int b)
{
     if(checkMove(px+2,py+1) && (a!=-2 && b!=-1))
         m1=2,m2=1;
     else
     {
         if(checkMove(px+2,py-1)&& (a!=-2 && b!=1))
             m1=2,m2=-1;
     else
     {
         if(checkMove(px-2,py+1)&& (a!=2 && b!=-1))
              m1=-2,m2=1;
     else
     {
         if(checkMove(px-2,py-1)&& (a!=2 && b!=1))
               m1=-2,m2=-1;
     else
     {
         if(checkMove(px+1,py+2)&& (b!=-2 && a!=-1))
               m2=2,m1=1;
     else
     {
         if(checkMove(px+1,py-2)&& (a!=-1 && b!=2))
               m2=-2,m1=1;
     else
     {
         if(checkMove(px-1,py+2)&& (a!=1 && b!=-2))
               m2=2,m1=-1;
     else
     {
         if(checkMove(px-1,py-2)&& (a!=1 && b!=2))
               m2=-2,m1=-1;
     }}}}}}}
}

//End of Program.

I haven't studied graphs yet..as per the problem of implementing it through simply arrays, I could not derive any solution other than this. I treated the positions not as ranks and files(The usual chess notation), but as array indices. FYI, this is for a 8*8 chessboard only. Any improvement advice is always welcomed.

*The comments should suffice for your understanding of the logic. However, you may always ask.

*Checked on DEV-C++ 4.9.9.2 compiler(Bloodshed Software).

Hays

Answer 10

I think that this might also help you..

NumWays(x,y)=1+min(NumWays(x+-2,y-+1),NumWays(x+-1,y+-2)); 

and using Dynamic Programming to get the solution.

P.S: It kinda uses the BFS without having to take the trouble of declaring the nodes and edges of the graph.

Faithfaithful

Answer 11

Here is a solution for this particular problem implemented in Perl. It will show one of the shortest paths - there might be more than one in some cases.

I didn't use any of the algorithms described above - but it would be nice to compare it to other solutions.

#!/usr/local/bin/perl -w

use strict;

my $from = [0,0];
my $to   = [7,7];

my $f_from = flat($from);
my $f_to   = flat($to);

my $max_x = 7;
my $max_y = 7;
my @moves = ([-1,2],[1,2],[2,1],[2,-1],[1,-2],[-1,-2],[-2,-1],[-2,1]);
my %squares = ();
my $i = 0;
my $min = -1;

my @s = ( $from );

while ( @s ) {

   my @n = ();
   $i++;

   foreach my $s ( @s ) {
       unless ( $squares{ flat($s) } ) {
            my @m = moves( $s );
            push @n, @m;
            $squares{ flat($s) } = { i=>$i, n=>{ map {flat($_)=>1} @m }, };

            $min = $i if $squares{ flat($s) }->{n}->{$f_to};
       }
   }

   last if $min > -1;
   @s = @n;
}

show_path( $f_to, $min );

sub show_path {
    my ($s,$i) = @_;

    return if $s eq $f_from;

    print "$i => $f_to\n" if $i == $min;

    foreach my $k ( keys %squares ) {
       if ( $squares{$k}->{i} == $i && $squares{$k}->{n}->{$s} ) {
            $i--;
            print "$i => $k\n";
            show_path( $k, $i );
            last;
       }
    }
}

sub flat { "$_[0]->[0],$_[0]->[1]" }

sub moves {
    my $c = shift;
    my @s = ();

    foreach my $m ( @moves ) {
       my $x = $c->[0] + $m->[0];
       my $y = $c->[1] + $m->[1];

       if ( $x >= 0 && $x <=$max_x && $y >=0 && $y <=$max_y) {
           push @s, [$x, $y];
       }
    }
    return @s;
}

__END__

Wadsworth

Answer 12

public class Horse {

    private int[][] board;
    private int[] xer = { 2, 1, -1, -2, -2, -1, 1, 2 };
    private int[] yer = { 1, 2, 2, 1, -1, -2, -2, -1 };
    private final static int A_BIG_NUMBER = 10000;
    private final static int UPPER_BOUND = 64;


    public Horse() {
        board =  new int[8][8];
    }

    private int solution(int x, int y, int destx, int desty, int move) {

        if(move == UPPER_BOUND) {
            /* lets put an upper bound to avoid stack overflow */
            return A_BIG_NUMBER;
        }

        if(x == 6 && y ==5) {
            board[6][5] = 1;
            return 1;
        }
        int min = A_BIG_NUMBER;
        for (int i = 0 ; i < xer.length; i++) {
            if (isMoveGood(x + xer[i], y + yer[i])) {
                if(board[x + xer[i]][y + yer[i]] != 0) {
                    min = Integer.min(min, 1 + board[x +xer[i]] [y +yer[i]]);                   
                } else {
                    min = Integer.min(min, 1 + solution(x + xer[i], y + yer[i], destx, desty, move + 1));   
                }                   
            }
        }   
        board[x][y] = min;
        return min;
    }


    private boolean isMoveGood(int x, int y) {
        if (x >= 0 && x < board.length && y >= 0 && y < board.length)
            return true;
        return false;
    }


    public static void main(String[] args) {

        int destX = 6;
        int destY = 7;
        final Horse h = new Horse();
        System.out.println(h.solution(0, 0, destX, destY, 0));
    }
}

Uprise

Answer 13

Just ruby code from Graeme Pyle's answer's jsfiddle above, striped all extra code and converted remaining to ruby just to get solution by his algorithm, seems like working. Still testing though:

def getBoardOffset(board)
  return board.length / 2
end

def setMoveCount(x, y, count, board)
  offset = getBoardOffset(board)
  board[y + offset][x + offset] = count
end

def getMoveCount(x, y, board)
    offset = getBoardOffset(board)
    row = board[y + offset]
    return row[x + offset]
end

def isBottomOfVerticalCase(x, y)
    return (y - 2 * x) % 4 == 0
end

def isPrimaryDiagonalCase(x, y)
    return (x + y) % 2 == 0
end

def isSecondaryDiagonalCase(x, y)
    return (x + y) % 2 == 1
end

def simplifyBySymmetry(x, y)
    x = x.abs
    y = y.abs
    if (y < x)
      t = x
      x = y
      y = t
    end
    return {x: x, y: y}
end

def getPrimaryDiagonalCaseMoveCount(x, y)
    var diagonalOffset = y + x
    var diagonalIntersect = diagonalOffset / 2
    return ((diagonalIntersect + 2) / 3).floor * 2
end

def getSpecialCaseMoveCount(x, y)
    specials = [{
            x: 0,
            y: 0,
            d: 0
        },
        {
            x: 0,
            y: 1,
            d: 3
        },
        {
            x: 0,
            y: 2,
            d: 2
        },
        {
            x: 0,
            y: 3,
            d: 3
        },
        {
            x: 2,
            y: 2,
            d: 4
        },
        {
            x: 1,
            y: 1,
            d: 2
        },
        {
            x: 3,
            y: 3,
            d: 2
        }
    ];
    matchingSpecial=nil
    specials.each do |special|
      if (special[:x] == x && special[:y] == y)
        matchingSpecial = special
      end
    end
    if (matchingSpecial)
      return matchingSpecial[:d]
    end
end

def isVerticalCase(x, y)
  return y >= 2 * x
end

def getVerticalCaseMoveCount(x, y)
    normalizedHeight = getNormalizedHeightForVerticalGroupCase(x, y)
    groupIndex = (normalizedHeight/4).floor
    groupStartMoveCount = groupIndex * 2 + x
    return groupStartMoveCount + getIndexInVerticalGroup(x, y)
end

def getIndexInVerticalGroup(x, y)
    return getNormalizedHeightForVerticalGroupCase(x, y) % 4
end

def getYOffsetForVerticalGroupCase(x) 
    return x * 2
end

def getNormalizedHeightForVerticalGroupCase(x, y)
    return y - getYOffsetForVerticalGroupCase(x)
end

def getSecondaryDiagonalCaseMoveCount(x, y)
    diagonalOffset = y + x
    diagonalIntersect = diagonalOffset / 2 - 1
    return ((diagonalIntersect + 2) / 3).floor * 2 + 1
end

def getMoveCountO1(x, y)
    newXY = simplifyBySymmetry(x, y)
    x = newXY[:x]
    y = newXY[:y]
    specialMoveCount = getSpecialCaseMoveCount(x ,y)
    if (specialMoveCount != nil)
      return specialMoveCount
    elsif (isVerticalCase(x, y))
      return getVerticalCaseMoveCount(x ,y)
    elsif (isPrimaryDiagonalCase(x, y))
      return getPrimaryDiagonalCaseMoveCount(x ,y)
    elsif (isSecondaryDiagonalCase(x, y))
      return getSecondaryDiagonalCaseMoveCount(x ,y)
    end
end

def solution(x ,y)
  return getMoveCountO1(x, y)
end


puts solution(0,0)

Only intention is to save someone some time converting code if anyone needs full code.

Tine

Answer 14

here's the PHP version of Jules May's function

function knightDistance($x, $y)
{
    $x = abs($x);
    $y = abs($y);

    if($x < $y)
    {
        $tmp = $x;
        $x = $y;
        $y = $tmp;
    }

    if($x > 2 * $y)
    {
        $n7 = 0;
        $n8 = floor(($x + 2*$y) / 4);
        $n10 = floor(($x - 2*$y +1) / 4);
    }
    else
    {
        $n7 = floor((2*$y - $x) / 3);
        $n8 = floor((2*$x - $y) / 3);
        $n10 = 0;
    }

    $x -= 2 * $n8 + $n7 + 2 * $n10;
    $y -= $n8 + 2 * $n7 - $n10;

    if($x == 1 && $y == 0)
    {
        if($n8 > 0)
        {
            $x = 3;
            $y = 1;
            $n8--;
        }
    }
    if($x == 2 && $y == 2)
    {
        if($n8 > 0)
        {
            $x = 3;
            $y = 1;
            $n8--;
            $n7++;
        }
    }

    $cheatsheet = [[0, 3, 2], [2, 0, 2], [4]];

    return $n7 + $n8 + $n10 + $cheatsheet [$y][$x-$y];
}

Hitt

Answer 15

Here is a C version based on Mustafa Serdar Şanlı code that works for a finit board:

#include <stdio.h>
#include <math.h>

#define test(x1, y1, x2, y2) (sx == x1 && sy == y1 &&tx == x2 &&ty == y2) || (sx == x2 && sy == y2 && tx == x1 && ty==y1)

int distance(int sx, int sy, int tx, int ty) {
    int x, y, t;
    double delta;

    // special corner cases 
    if (test(1, 1, 2, 2) || 
        test(7, 7, 8, 8) || 
        test(7, 2, 8, 1) || 
        test(1, 8, 2, 7))
        return 4;

    // axes symmetry 
    x = abs(sx - tx);
    y = abs(sy - ty);

    // diagonal symmetry 
    if (x < y) {
        t = x;
        x = y;
        y = t;
    }

    // 2 corner cases
    if (x == 1 && y == 0)
        return 3;
    if (x == 2 && y == 2)
        return 4;

    // main
    delta = x - y;
    if (y > delta) {
        return (int)(delta - 2 * floor((delta - y) / 3));
    }
    else {
        return (int)(delta - 2 * floor((delta - y) / 4));
    }
}

Test it here with proof against a recursive solution

Certifiable

Testing a finite number of cases is not a proof. – Piecrust

Answer 16

Here is my program. This is not a perfect solution. There are lots of changes to make in the recursion function. But this end result is perfect. I tried to optimize a bit.

public class KnightKing2 {
    private static int tempCount = 0;

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        int ip1 = Integer.parseInt(in.nextLine().trim());
        int ip2 = Integer.parseInt(in.nextLine().trim());
        int ip3 = Integer.parseInt(in.nextLine().trim());
        int ip4 = Integer.parseInt(in.nextLine().trim());
        in.close();
        int output = getStepCount(ip1, ip2, ip3, ip4);
        System.out.println("Shortest Path :" + tempCount);

    }

    // 2 1 6 5 -> 4
    // 6 6 5 5 -> 2

    public static int getStepCount(int input1, int input2, int input3, int input4) {
        return recurse(0, input1, input2, input3, input4);

    }

    private static int recurse(int count, int tx, int ty, int kx, int ky) {

        if (isSolved(tx, ty, kx, ky)) {
            int ccount = count+1;
            System.out.println("COUNT: "+count+"--"+tx+","+ty+","+ccount);
            if((tempCount==0) || (ccount<=tempCount)){
                tempCount = ccount;
            }
            return ccount;
        }

            if ((tempCount==0 || count < tempCount) && ((tx < kx+2) && (ty < ky+2))) {
                if (!(tx + 2 > 8) && !(ty + 1 > 8)) {
                    rightTop(count, tx, ty, kx, ky);

                }
                if (!(tx + 2 > 8) && !(ty - 1 < 0)) {
                    rightBottom(count, tx, ty, kx, ky);
                }
                if (!(tx + 1 > 8) && !(ty + 2 > 8)) {
                    topRight(count, tx, ty, kx, ky);
                }
                if (!(tx - 1 < 0) && !(ty + 2 > 8)) {
                    topLeft(count, tx, ty, kx, ky);
                }
                if (!(tx + 1 > 8) && !(ty - 2 < 0)) {
                     bottomRight(count, tx, ty, kx, ky);
                }
                if (!(tx - 1 < 0) && !(ty - 2 < 0)) {
                     bottomLeft(count, tx, ty, kx, ky);
                }
                if (!(tx - 2 < 0) && !(ty + 1 > 8)) {
                    leftTop(count, tx, ty, kx, ky);
                }
                if (!(tx - 2 < 0) && !(ty - 1 < 0)) {
                    leftBottom(count, tx, ty, kx, ky);
                }
            }

        return count;

    }

    private static int rightTop(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx + 2, ty + 1, kx, ky);

    }

    private static int topRight(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx + 1, ty + 2, kx, ky);
    }

    private static int rightBottom(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx + 2, ty - 1, kx, ky);
    }

    private static int bottomRight(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx + 1, ty - 2, kx, ky);
    }

    private static int topLeft(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx - 1, ty + 2, kx, ky);
    }

    private static int bottomLeft(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx - 1, ty - 2, kx, ky);
    }

    private static int leftTop(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx - 2, ty + 1, kx, ky);
    }

    private static int leftBottom(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx - 2, ty - 1, kx, ky);
    }

    private static boolean isSolved(int tx, int ty, int kx, int ky) {
        boolean solved = false;
        if ((tx == kx) && (ty == ky)) {
            solved = true;
        } else if ((tx + 2 == kx) && (ty + 1 == ky)) { // right top
            solved = true;
        } else if ((tx + 2 == kx) && (ty - 1 == ky)) { // right bottom
            solved = true;
        } else if ((ty + 2 == ky) && (tx + 1 == kx)) {// top right
            solved = true;
        } else if ((ty + 2 == ky) && (tx - 1 == kx)) {// top left
            solved = true;
        } else if ((tx - 2 == kx) && (ty + 1 == ky)) { // left top
            solved = true;
        } else if ((tx - 2 == kx) && (ty - 1 == ky)) {// left bottom
            solved = true;
        } else if ((ty - 2 == ky) && (tx + 1 == kx)) { // bottom right
            solved = true;
        } else if ((ty - 2 == ky) && (tx - 1 == kx)) { // bottom left
            solved = true;
        }

        return solved;
    }

}

Showalter

It can be further optimized to avoid duplicates. – Showalter

Answer 17

Here's Another working Python solution (from Johan du Toit):

Input:

1<=sx,sy,tx,ty<=8

def knightDistance( sx,  sy,  tx,  ty):

    def test(x1, y1, x2, y2):
      return (sx == x1 and sy == y1 and tx == x2 and ty == y2) or (sx == x2 and sy == y2 and tx == x1 and ty==y1)

    # special corner cases 
    if (test(1, 1, 2, 2) or
        test(7, 7, 8, 8) or 
        test(7, 2, 8, 1) or 
        test(1, 8, 2, 7)):
            return 4

    # axes symmetry 
    x = abs(sx - tx)
    y = abs(sy - ty)

    # diagonal symmetry 
    if (x < y):
        x,y = y,x

    # 2 corner cases
    if (x == 1 and y == 0):
        return 3
    if (x == 2 and y == 2):
        return 4

    # main
    delta = x - y;
    if (y > delta) :
        return int(delta - 2 * ((delta - y) // 3))
    else:
        return int(delta - 2 * ((delta - y) // 4))

Outrelief

Answer 18

I'd like to contribute to this question with my version in Javascript. My algorithm find the collection of shortest paths to a target.

Cheers!

  static size = 8;

  targetPos = [];
  targetToken = 't';
  moveToken = 'a';

  static isOutOfBoundaries(x,y){
    if(x>Board.size-1||x<0)
      return true;
    else if(y>Board.size-1||y<0)
      return true;
    else
      return false;
  }

  constructor(){
    this.tiles = Array.from(Array(Board.size), ()=>Array.from(Array(Board.size), tile=>'·')); 
  }

  visualize(){
    this.tiles.forEach(row=>console.log(row.join(' ')));
  }

  placeItem(position, token){
    if(Board.isOutOfBoundaries(position[0],position[1]))
      throw new Error(`Piece/Target is out board boundaries`);
    else
      this.tiles[position[1]][position[0]] = token;
  }
  
  markPieceMoves(piece){
    for(let i = 0; i<piece.moves.length; ++i)
      this.tiles[piece.moves[i][1]][piece.moves[i][0]] = this.moveToken;
  }

}

class MovesTree{
  constructor(position){
    
    this.pos = position;

    // -
    //|
    //|
    this.uur = null; 
    
    //  |
    //--
    this.rru = null;

    //--
    //  |
    this.rrd = null;

    //|
    //|
    // -
    this.ddr = null;

    // |
    // |
    //-
    this.ddl = null;

    // --
    //|
    this.lld = null;

    //|
    // --
    this.llu = null;

    //-
    // |
    // |
    this.uul = null;

  }

  static getMoves(node){
    const twoSteps = 2;
    const oneStep = 1;
    // -
    //|
    //|
    if(!Board.isOutOfBoundaries(node.pos[0]+oneStep,node.pos[1]-twoSteps))
      node.uur=new MovesTree([node.pos[0]+oneStep,node.pos[1]-twoSteps]);

    //  |
    //--
    if(!Board.isOutOfBoundaries(node.pos[0]+twoSteps,node.pos[1]-oneStep))
      node.rru=new MovesTree([node.pos[0]+twoSteps,node.pos[1]-oneStep]);
    //--
    //  |
    if(!Board.isOutOfBoundaries(node.pos[0]+twoSteps,node.pos[1]+oneStep))
      node.rrd=new MovesTree([node.pos[0]+twoSteps,node.pos[1]+oneStep]);
    //|
    //|
    // -
    if(!Board.isOutOfBoundaries(node.pos[0]+oneStep,node.pos[1]+twoSteps))
      node.ddr=new MovesTree([node.pos[0]+oneStep,node.pos[1]+twoSteps]);
    // |
    // |
    //-
    if(!Board.isOutOfBoundaries(node.pos[0]-oneStep,node.pos[1]+twoSteps))
      node.ddl=new MovesTree([node.pos[0]-oneStep,node.pos[1]+twoSteps]);
    // --
    //|
    if(!Board.isOutOfBoundaries(node.pos[0]-twoSteps,node.pos[1]+oneStep))
      node.lld=new MovesTree([node.pos[0]-twoSteps,node.pos[1]+oneStep]);
    //|
    // --
    if(!Board.isOutOfBoundaries(node.pos[0]-twoSteps,node.pos[1]-oneStep))
      node.llu=new MovesTree([node.pos[0]-twoSteps,node.pos[1]-oneStep]);
    //-
    // |
    // |
    if(!Board.isOutOfBoundaries(node.pos[0]-oneStep,node.pos[1]-twoSteps))
      node.uul=new MovesTree([node.pos[0]-oneStep,node.pos[1]-twoSteps]);

  }    

  BFS(func,target){
    let queue = [this];
    while(queue.length>0){
      if(target.toString()!==queue[0].pos.toString()){
        MovesTree.getMoves(queue[0])
        queue.push(...func(queue[0]));
      }
      else
        return; 
      queue.shift();
    }
  }

  DFS(node, target, path){

    let visited; 
    path === undefined ? visited = [node.pos]: visited = this.mergePath(path, node.pos);
    if(node.pos.toString()===target.toString()){
      visited.reverse();
      console.log(visited);
      return;
    }
    else{
      if(node.uur!==null)
        this.DFS(node.uur, target, visited);
      if(node.rru!==null)
        this.DFS(node.rru, target, visited);
      if(node.rrd!==null)
        this.DFS(node.rrd, target, visited);
      if(node.ddr!==null)
        this.DFS(node.ddr, target, visited);
      if(node.ddl!==null)
        this.DFS(node.ddl, target, visited);
      if(node.lld!==null)
        this.DFS(node.lld, target, visited);
      if(node.llu!==null)
        this.DFS(node.llu, target, visited);
      if(node.uul!==null)
        this.DFS(node.uul, target, visited);
    }
  }

  toArray(node){

    let array = [];

    if(node.uur!==null)
      array.push(node.uur);
    if(node.rru!==null)
      array.push(node.rru);
    if(node.rrd!==null)
      array.push(node.rrd);
    if(node.ddr!==null)
      array.push(node.ddr);
    if(node.ddl!==null)
      array.push(node.ddl);
    if(node.lld!==null)
      array.push(node.lld);
    if(node.llu!==null)
      array.push(node.llu);
    if(node.uul!==null)
      array.push(node.uul);
    return array;
  }

  mergePath(path, current){
    let merged = [];
    merged.push(current);
    path.forEach(step=>{
      merged.push(step)
    });
    return merged;
  }
}
class Knight{
  token = 'k';
  constructor(row,col){
    this.position = [row,col];
    this.moves = new MovesTree(this.position,this);
  }
}
const board = new Board();
board.targetPos = [6,0];
const knight = new Knight(0,7);
board.placeItem(knight.position, knight.token);
board.placeItem(board.targetPos, board.targetToken)

knight.moves.BFS(knight.moves.toArray, board.targetPos);
knight.moves.DFS(knight.moves, board.targetPos)
board.visualize();

Culprit

Answer 19

I thought I would provide an intuitive greedy solution (O(max(horizontal distance, vertical distance))) that is easier to understand than the constant time one but much faster than a searching algorithm. This is in the context of an infinite chess board.

The gist of this solution is studying the geometry and realizing that for everything greater than two knight moves away you can simply take the path that gets you closer to the end point.

1. While you are greater than two knight moves away move towards (x, y) by taking 2 steps in the direction of whichever coordinate is farther and 1 step to whichever is closer.
2. Once you are within two knight moves consult the lookup table.

  int minKnightMoves(int x, int y) {
    vector<vector<int>> table = {{4, 3, 2, 3, 2, 3, 2, 3, 4},
                                 {3, 2, 3, 2, 3, 2, 3, 2, 3},
                                 {2, 3, 4, 1, 2, 1, 4, 3, 2},
                                 {3, 2, 1, 2, 3, 2, 1, 2, 3},
                                 {2, 3, 2, 3, 0, 3, 2, 3, 2},
                                 {3, 2, 1, 2, 3, 2, 1, 2, 3},
                                 {2, 3, 4, 1, 2, 1, 4, 3, 2},
                                 {3, 2, 3, 2, 3, 2, 3, 2, 3},
                                 {4, 3, 2, 3, 2, 3, 2, 3, 4}};
    int x0 = 0, y0 = 0, x1 = x, y1 = y;
    int x_dist = x1, y_dist = y1, max_dist = table.size() / 2, moves = 0;
    while (abs(x_dist) > max_dist || abs(y_dist) > max_dist) {
      if (abs(x_dist) > abs(y_dist)) {
        x0 += (x_dist > 0) ? 2 : -2;
        y0 += (y_dist > 0) ? 1 : -1;
      } else {
        x0 += (x_dist > 0) ? 1 : -1;
        y0 += (y_dist > 0) ? 2 : -2;
      }
      x_dist = x1 - x0, y_dist = y1 - y0;
      moves++;
    }
    return moves + table[x_dist + 4][y_dist + 4];
  }

Westberry