骑士的最短path棋问题

我一直在为即将到来的编程大赛练习，而我偶然发现了一个我完全不解的问题。 但是，我觉得这是一个我现在应该学习的概念，而不是交叉我的手指，它永远不会出现。

基本上，它处理棋盘上的骑士棋子。 给你两个input：开始位置和结束位置。 目标是计算并打印骑士可以到达目标位置的最短path。

我从来没有处理过最短path的事情，我甚至不知道从哪里开始。 我用什么逻辑来解决这个问题？

PS如果它有任何相关性，他们希望你补充骑士的正常移动能力，同时允许它移动到骑士的移动path创build的广场的四个angular落，如果在董事会的中心。

这里有一个图表，其中所有可用的移动被连接（值= 1），并且不可用的移动被断开（值= 0），稀疏matrix将如下所示： 

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

图中两点的最短path可以使用http://en.wikipedia.org/wiki/Dijkstra's_algorithm

来自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[]

编辑：

  1. 作为白痴，说使用http://en.wikipedia.org/wiki/A*_algorithm可以更快。;
  2. 最快的方法是预先计算所有距离并将其保存为8×8全matrix。 好吧，我会称之为作弊，只是因为问题很小才起作用。 但有时比赛会检查你的程序运行速度。
  3. 主要的一点是，如果你正在准备一个编程竞赛，你必须知道常用的algorithm，包括Dijkstra的。 一个好的起点是阅读Introduction to Algorithms ISBN 0-262-03384-4。 或者你可以尝试维基百科， http://en.wikipedia.org/wiki/List_of_algorithms

编辑： 看到西蒙的答案 ，他在哪里固定这里提出的公式。

其实有一个O（1）公式

这是我用来形象化的一个图像（骑士可以在第 N 步移动的区域涂上相同的颜色）。 骑士的移动

你能注意到这里的模式吗？

虽然我们可以看到模式，但很难find函数f( x , y ) ，它返回从平方( 0 , 0 )到平方( x , y )所需的移动次数。

但是当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 ); }

注意：这个问题在SACO 2007第1天被询问
解决scheme在这里

这是一个正确的O（1）解决scheme，但是对于骑士只能像一个象棋骑士一样移动的情况，以及在一个无限的棋盘上：

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

find这个的关键是要注意绘制板子时出现的模式。 在下图中，正方形中的数字是达到该平方所需的最小移动次数（可以使用广度优先search来查找）：

模式

因为解决scheme在轴和对angular线上是对称的，所以我只绘制了x> = 0和y> = x的情况。

左下方的块是起始位置，块中的数字表示达到这些块的最小移动次数。

有三种模式需要注意：

  • 增加蓝色垂直组4
  • “主要”红色对angular线（它们从左上到右下，如反斜线）
  • “次要”绿色对angular线（与红色方向相同）

（确保你将两组对angular线看作是左上angular到右下angular，它们有一个不变的移动计数，左下angular的右上对angular线要复杂得多。）

你可以导出每个公式。 黄色块是特殊情况。 所以解决scheme变成： 

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

最难的是垂直组织： 

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

其他情况请看小提琴。

也许有更简单或更优雅的模式，我错过了？ 如果是这样，我很乐意看到他们。 特别是，我注意到蓝色垂直情况下的一些对angular线模式，但我没有探究它们。 无论如何，这个解决scheme仍然满足O（1）约束。

是的，Dijkstra和BFS会给你答案，但我认为这个问题的象棋背景提供的知识可以产生比通用最短pathalgorithm快得多的解决scheme，特别是在无限的棋盘上。

为了简单起见，我们将棋盘描述为（x，y）平面。 我们的目标是仅仅使用候选步（+ -1，+ -2），（+ -2，+ -1）和（+ -2）来find从（x0，y0）到（x1，y1）的最短path，+ – 2），如问题的PS中所述

（x-4，y-4），（x-4，y + 4），（x + 4，y-4），（x + 4，y + 4） 。 这个集合（称为S4）包含32个点。 从这32点到（x，y）的最短path只需要两步 。

从集合S3（同样定义）中的24个点中的任何点到（x，y）的最短path需要至less两个移动 。

（x0，y0）到（x1，y1）的最短path正好是从S4。 而后一个问题可以通过直接迭代快速解决。

令N = max（| x1-x0 |，| y1-y0 |）。 如果N> = 4，则从（x0，y0）到（x1，y1）的最短path具有单元（N / 2）步。

我最近遇到的非常有趣的问题。 在寻找一些解决scheme后，我试图恢复SACO 2007第1天 解决scheme中给出的分析公式（ O(1) time and space complexity ）。

首先，我想欣赏格雷姆派尔非常好的可视化，帮助我修复公式。

由于某种原因（可能是为了简化或美观，或者只是一个错误），他们将minus号移到了floor操作员身上，结果他们得到了错误的公式floor(-a) != -floor(a) for any a 。

这是正确的分析公式： 

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

公式适用于除了（1,0）和（2,2）个angular落案例之外的所有（x，y）对（在应用轴和对angular线对称之后），这些案例不满足于模式，并在以下片段中进行硬编码： 

 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 = xy; 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>

上面的O（1）答案[Mustafa SerdarŞanlı] [ https://stackoverflow.com/a/8778592/4288232 ]是不是真的工作。 （除了（1,0）或（2,2）的明显边缘情况外，检查（1,1）或（3,2）或（4,4））。

下面是一个更加丑陋的解决scheme（python），它可以工作（添加了“testing”）： 

 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 - ((xy)/2) if((xy)%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()

你需要做的是把骑士可能的移动看作一个graphics，棋盘上的每个位置都是一个节点，可能移动到其他位置作为边缘。 没有必要使用dijkstraalgorithm，因为每条边都具有相同的权重或距离（它们都是一样简单或短小）。 您可以从您的起点开始进行BFSsearch，直到您到达最终位置。

从Python的第一原则的解决scheme

我在一个Codilitytesting中第一次遇到这个问题。 他们给了我30分钟的时间来解决这个问题 – 我花了很长时间才得到这个结果！ 问题是：骑士从0,0到x，y只需要采取合法骑士的动作需要多less动作。 x和y或多或less是无界的（所以我们不是在这里谈论一个简单的8×8棋盘）。

他们想要一个O（1）解决scheme。 我想要一个解决scheme，明确解决问题的scheme（即我想要比Graeme的模式更明显的东西 – 模式有打破你不看的地方的习惯），我真的不想依靠如在穆斯塔法的解决scheme中一样

所以，这是我的解决scheme，它是值得的。 开始，像其他人一样，注意到解的关于轴和对angular线是对称的，所以我们只需求解0> = y> = x。 为了简单的解释（和代码），我将扭转这个问题：骑士从x，y开始，瞄准0,0。

假设我们把问题缩小到原点附近。 在适当的时候，我们将会得到“vicinty”实际上意味着什么，但是现在，我们只需要在一个cheatsheet中写下一些解决scheme（原点在左下angular）： 

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

所以，给定网格上的x，y，我们可以读出移动到原点的数量。

如果我们已经开始在电网之外，我们必须回到它的方式。 我们引入“中线”，即由y = x / 2表示的线。 任何位于该行的x，y上的骑士都可以使用一系列8点动作（即：（-2，-1）移动）返回到cheatsheet。 如果x，y位于中线上方，那么我们需要8点和7点的连续动作，如果它位于中线的下方，我们需要连续的8点和10点时钟移动。 这里要注意两点：

  • 这些序列是可certificate的最短path。 （要我certificate，还是显而易见？）
  • 我们只关心这样的动作的数量。 我们可以以任何顺序混合和匹配这些动作。

所以，让我们看看上面的中线移动。 我们所声称的是：

  • （dx; dy）=（2,1; 1,2）（n8; n7）（matrix表示法，无math排版 – 列向量（dx; dy）等于matrix乘以列向量（n8; n7） – 8点移动的数量和7点的移动数量），以及类似的;

  • （dx; dy）=（2,2; 1，-1）（n8; n10）

我声称dx，dy将大致为（x，y），所以（x-dx，y-dy）将在原点附近（无论“附近”原来是什么）。

计算这些术语的代码中的两行是解决这些问题的方法，但是它们被select为具有一些有用的属性：

  • 上述中线公式将（x，y）移动到（0,0），（1,1）或（2,2）中的一个。
  • 下面的中线公式将（x，y）移动到（0,0），（1,0），（2,0）或（1,1）之一。

（你想要certificate这些吗？）所以，骑士的距离将是n7，n8，n10和cheatsheet [x-dx，y-dy]的总和，我们的cheatsheet简化为： 

 . . 4 . 2 . 0 3 2

现在，这不是故事的结尾。 看看底部的3。 我们能做到的唯一途径是：

  • 我们从那里开始，或者
  • 我们搬到了那里，按照8点和10点的顺序移动。 但是如果最后一步是8点（这是有权利的，因为我们可以按照任何顺序进行），那么我们一定经过了（3,1），其距离实际上是2从原始的cheatsheet看）。 所以我们应该做的是回溯一个8点动作，总共节省两个动作。

右上angular的4有一个类似的优化。 除了从那里出发，唯一的办法就是从（4,3）的8点开始。 这不是在cheatsheet，但如果它在那里，它的距离将是3，因为我们可以有7点到（3,1），而只有2的距离。所以，我们应该回到一个8点动，然后前进7点。

所以，我们需要添加一个更多的数字到cheatsheet： 

 . . 4 . 2 . 2 0 3 2

（注意：（0,1）和（0,2）有一个完整的反向跟踪优化负载，但是由于求解器永远不会把它带到那里，所以我们不需要担心它们。）

那么在这里，是一些Python代码来评估这个： 

 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][xy]

顺便说一句，如果你想知道一个实际的路线，那么这个algorithm也提供了这个：它只是一个七点七点的移动，随后是（或穿插）n8 8点移动，n10 10点移动，随时可以移动，而且任何跳舞都可以通过cheatsheet（本身可以在cheatsheet中）来决定。

现在：如何certificate这是正确的。 仅仅将这些结果与正确答案进行比较是不够的，因为问题本身是无边界的。 但是我们可以这样说，如果骑士的平方距离是d，那么如果{m}是s的合法移动集合，那么骑士的（s + m）距离必须是d-1或者d + 1所有的米。 （你需要certificate这一点吗？）另外，至less有一个这样的正方形的距离是d-1，除非s是原点。 所以，我们可以通过显示这个属性为每个方块来certificate正确性。 从而： 

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

或者，我们可以通过追踪从下坡到原点的路线来certificate任何一个正方形的正确性。 首先，检查s的合理性如上，然后select任何s + m，使距离（s + m）== d-1。 重复，直到我们到达原点。

Howzat？ 

 /* 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 ie 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=ca; else xdiff=ac; if(d>b) ydiff=db; else ydiff=bd; 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(ie 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.

我还没有研究过图表。由于通过简单的数组实现它的问题，我不能得出任何解决scheme，除此之外。 我把这些职位视为队伍和文件（通常的国际象棋符号），而不是数组索引。 仅供参考，这仅适用于8 * 8的棋盘。 任何改进build议总是欢迎。

*评论应该足以让你理解这个逻辑。 但是，你可能总是问。

*检查DEV-C ++ 4.9.9.2编译器（Bloodshed Software）。

我认为这也可以帮助你 

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

并使用dynamic编程来获得解决scheme。

PS：它有点使用BFS，而不必费力地声明图的节点和边。

这是Perl中实现的这个特殊问题的解决scheme。 它将显示最短path之一 – 在某些情况下可能会有多个path。

我没有使用上述任何algorithm – 但将其与其他解决scheme进行比较将是一件好事。 

 #!/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__ 
 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)); } }

从上面的Graeme Pyle的答案的jsfiddle ruby代码，条纹所有额外的代码，并转换成ruby只是为了得到他的algorithm的解决scheme，似乎工作。 仍在testing： 

 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.

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

    开发国际象棋程序时初始化方向数组的意义是什么？

    程序员谜题：在整个游戏中编写一个棋盘状态

    有一个完美的国际象棋algorithm吗？

    实现一个象棋引擎有多难？