棋盘上骑士的最短路径

小开

最佳答案

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:

as moron, said using the http://en.wikipedia.org/wiki/A*_algorithm can be faster.
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.
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

小开

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.

小开

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.

小开

/*
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).

小开

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 ). 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

小开

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.

小开

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__

小开

The O(1) answer above [https://stackoverflow.com/a/8778592/4288232 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()

小开

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));
}
}

小开

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.

小开

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.

小开

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?

小开

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.

小开

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];
}

小开

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

小开

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;
}


}

小开

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))