我一直在为即将举行的编程比赛练习，我偶然发现了一个让我完全困惑的问题。然而，我觉得这是一个我现在应该学习的概念，而不是指望它永远不会出现。
基本上，它处理棋盘上的骑士棋子。您有两个输入：起始位置和结束位置。目标是计算并打印骑士到达目标位置的最短路径。
我从来没有处理过最短路径的事情，我什至不知道从哪里开始。我采用什么逻辑来解决这个问题？
PS如果有任何相关性，他们希望您通过允许骑士移动到由骑士可以进行的（可能）八个动作形成的广场的四个角落来补充骑士的正常动作，因为广场的中心是骑士的位置。
问问题
90531 次
17 回答
56
编辑： 请参阅 simon 的答案，他在其中修复了此处提供的公式。
实际上有一个 O(1) 公式
这是我为使其可视化而制作的图像（骑士在第 N次移动时可以到达的方块涂有相同的颜色）。
你能注意到这里的模式吗？
虽然我们可以看到模式，但真的很难找到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 天
提出的
，解决方案在这里
于 2012-01-08T15:09:17.227 回答
47
这是一个正确的 O(1) 解决方案，但对于骑士像国际象棋骑士一样移动的情况，并且在无限棋盘上：
https://jsfiddle.net/graemian/5qgvr1ba/11/
找到这一点的关键是注意画板时出现的图案。在下图中，方格中的数字是到达该方格所需的最小移动次数（您可以使用广度优先搜索来找到它）：
因为解决方案在轴和对角线上是对称的，所以我只绘制了 x >= 0 和 y >= x 的情况。
左下角的方块是起始位置，方块中的数字代表到达这些方块的最小移动次数。
有 3 种模式需要注意：
- 递增的蓝色垂直组 4
- “主要”红色对角线（它们从左上角到右下角，就像一个反斜杠）
- “次要”绿色对角线（与红色方向相同）
（确保你看到两组对角线都是从左上到右下。它们有一个恒定的移动计数。左下角和右上角的对角线要复杂得多。）
您可以为每个派生公式。黄色块是特殊情况。所以解决方案变成：
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);
}
有关其他情况，请参见小提琴。
也许我错过了更简单或更优雅的模式？如果是这样，我很想见到他们。特别是，我注意到蓝色垂直案例中的一些对角线图案，但我没有探索过它们。无论如何，这个解决方案仍然满足 O(1) 约束。
于 2016-03-13T09:33:19.293 回答
28
您在这里有一个图表，其中所有可用的移动都已连接（值 = 1），并且不可用的移动已断开连接（值 = 0），稀疏矩阵将如下所示：
(a1,b3)=1,
(a1,c2)=1,
.....
并且可以使用http://en.wikipedia.org/wiki/Dijkstra's_algorithm找到图中两点的最短路径
来自维基百科页面的伪代码：
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[]
编辑：
- 正如白痴所说，使用 http://en.wikipedia.org/wiki/A*_algorithm 可以更快。
- 最快的方法是预先计算所有距离并将其保存到 8x8 完整矩阵中。好吧，我称之为作弊，并且仅因为问题很小而起作用。但有时比赛会检查你的程序运行速度。
- 要点是，如果你正在准备一场编程比赛，你必须知道包括 Dijkstra 在内的常用算法。一个好的起点是阅读
Introduction to AlgorithmsISBN 0-262-03384-4。或者你可以试试维基百科，http ://en.wikipedia.org/wiki/List_of_algorithms
于 2010-02-26T02:30:52.070 回答
26
我最近遇到的一个非常有趣的问题。在查看了一些解决方案后，我试图恢复SACO 2007 第 1 天解决方案O(1) time and space complexity中给出的分析公式 () 。
首先，我要感谢Graeme Pyle非常好的可视化，它帮助我修复了公式。
出于某种原因（可能是为了简化或美观或只是一个错误），他们将minussign 移到flooroperator 中，结果他们得到了错误的 formula floor(-a) != -floor(a) for any a。
下面是正确的解析公式：
var delta = x-y;
if (y > delta) {
return delta - 2*Math.floor((delta-y)/3);
} else {
return delta - 2*Math.floor((delta-y)/4);
}
该公式适用于所有 (x,y) 对（在应用轴和对角对称之后），除了 (1,0) 和 (2,2) 极端情况，它们不满足模式并在以下代码段中硬编码：
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>注意：jQuery 仅用于说明，代码见distance函数。
于 2017-01-17T18:08:09.240 回答
19
是的，Dijkstra 和 BFS 会给你答案，但我认为这个问题的国际象棋上下文提供的知识可以产生比通用最短路径算法快得多的解决方案，尤其是在无限棋盘上。
为简单起见，让我们将棋盘描述为 (x,y) 平面。目标是仅使用候选步骤 (+-1, +-2)、(+-2, +-1) 和 (+-2) 找到从 (x0,y0) 到 (x1,y1) 的最短路径, +-2)，如问题的 PS 中所述
这是新的观察：画一个有角的正方形 (x-4,y-4), (x-4,y+4), (x+4,y-4), (x+4,y+4) . 这组（称为 S4）包含 32 个点。从这 32 个点中的任何一个到 (x,y) 的最短路径恰好需要两次移动。
从集合 S3（定义类似）中的任何 24 个点到 (x,y) 的最短路径至少需要两次移动。
因此，如果 |x1-x0|>4 或 |y1-y0|>4，则从 (x0,y0) 到 (x1,y1) 的最短路径正好比从 (x0,y0) 到 (x0,y0) 到S4。后一个问题可以通过简单的迭代快速解决。
令 N = max(|x1-x0|,|y1-y0|)。如果 N>=4，则从 (x0,y0) 到 (x1,y1) 的最短路径有ceil(N/2)步。
于 2010-02-26T04:29:33.923 回答
12
上面的 O(1) 答案 [ https://stackoverflow.com/a/8778592/4288232 by Mustafa Serdar Şanlı] 并没有真正起作用。（检查 (1,1) 或 (3,2) 或 (4,4)，除了 (1,0) 或 (2,2) 的明显边缘情况）。
下面是一个更丑陋的解决方案（python），它确实有效（添加了“测试”）：
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()
于 2014-11-12T14:05:24.867 回答
9
您需要做的是将马可能的移动视为一个图形，其中棋盘上的每个位置都是一个节点，而可能移动到其他位置的可能是一条边。不需要 dijkstra 算法，因为每条边都具有相同的权重或距离（它们都一样容易或短）。您可以从起点进行 BFS 搜索，直到到达终点。
于 2010-02-26T03:17:07.280 回答
7
Python中第一原理的解决方案
我第一次遇到这个问题是在 Codility 测试中。他们给了我 30 分钟的时间来解决它——我花了比这更长的时间来得到这个结果！问题是：只使用合法的骑士动作，骑士从 0,0 到 x,y 需要多少步。x 和 y 或多或少是无界的（所以我们在这里不是在谈论一个简单的 8x8 棋盘）。
他们想要一个 O(1) 的解决方案。我想要一个程序清楚地解决问题的解决方案（即，我想要比 Graeme 的模式更明显正确的东西——模式习惯于在你不看的地方分解），我真的不想依赖无争议的公式，如穆斯塔法的解决方案
所以，这是我的解决方案，值得。和其他人一样，首先要注意解是关于轴和对角线对称的，所以我们只需要求解 0 >= y >= x。为了解释（和代码）的简单起见，我将扭转问题：骑士从 x,y 开始，目标是 0,0。
假设我们将问题缩小到原点附近。我们将在适当的时候了解“vicinty”的实际含义，但现在，让我们在备忘单中写下一些解决方案（起源于左下角）：
2 1 4 3
3 2 1 2
0 3 2 3
因此，给定网格上的 x,y，我们可以读取到原点的移动次数。
如果我们从网格之外开始，我们必须努力回到它。我们引入“中线”，即 y=x/2 表示的线。该线上 x,y 处的任何骑士都可以使用一系列 8 点钟移动（即：(-2,-1) 移动）回到备忘单。如果 x,y 位于中线上方，那么我们需要连续 8 点和 7 点移动，如果它位于中线下方，我们需要连续 8 点和 10 点移动'时钟移动。这里需要注意两点：
- 这些序列可证明是最短路径。（要我证明，还是很明显？）
- 我们只关心此类移动的数量。我们可以以任何顺序混合和匹配这些动作。
所以，让我们看看中线以上的动作。我们声称的是：
(dx;dy) = (2,1 ; 1,2) (n8; n7) （矩阵表示法，没有数学排版 - 列向量 (dx;dy) 等于方阵乘以列向量 (n8;n7) - 8 点钟移动的次数和 7 点钟的移动次数），同理；
(dx;dy) = (2,2; 1,-1) (n8; n10)
我声称 dx,dy 将大致为 (x,y)，因此 (x-dx, y-dy) 将在原点附近（无论“附近”是什么）。
计算这些项的代码中的两行是这些项的解决方案，但它们被选择为具有一些有用的属性：
- 上中线公式将 (x,y) 移动到 (0,0)、(1,1) 或 (2,2) 之一。
- 下中线公式将 (x,y) 移动到 (0,0)、(1,0)、(2,0) 或 (1,1) 之一。
（你想要这些的证明吗？）所以，骑士的距离将是 n7、n8、n10 和备忘单 [x-dx, y-dy] 的总和，我们的备忘单简化为：
. . 4
. 2 .
0 3 2
现在，这还不是故事的结局。看看最下面一行的 3。我们可以达到这一点的唯一方法是：
- 我们从那里开始，或者
- 我们搬到那里，按 8 点钟和 10 点钟的顺序移动。但是如果最后一步是 8 点钟（这是它的权利，因为我们可以按任何顺序进行移动），那么我们一定已经通过 (3,1)，它的距离实际上是 2（你可以请参阅原始备忘单）。所以我们应该做的是回溯8点的一招，一共节省两招。
右上角的 4 也有类似的优化。除了从那里开始之外，到达那里的唯一方法是从 (4,3) 移动 8 点钟。那不在备忘单上，但如果它在那里，它的距离将是 3，因为我们可以将 7 点钟指向 (3,1)，而它的距离只有 2。所以，我们应该回溯一个8 点移动，然后前进一个 7 点。
因此，我们需要在备忘单上再添加一个数字：
. . 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][x-y]
顺便说一句，如果你想知道一条实际的路线，那么这个算法也提供了：它只是一个连续的 n7 个 7 点钟动作，然后是（或穿插）n8 个 8 点钟动作，n10 10-点移动，以及由备忘单规定的任何舞蹈（其本身可以在备忘单中）。
现在：如何证明这是正确的。仅将这些结果与正确答案表进行比较是不够的，因为问题本身是无界的。但是我们可以说，如果马与方格 s 的距离是 d，那么如果 {m} 是从 s 开始的合法移动的集合，那么马在 (s+m) 的距离必须是 d-1 或 d+1对于所有 m。（你需要证明吗？）此外，必须至少有一个这样的正方形，其距离为 d-1，除非 s 是原点。因此，我们可以通过显示该属性对每个正方形都成立来证明正确性。因此：
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")
或者，我们可以通过追逐从 s 下坡到原点的路线来证明任何一个正方形 s 的正确性。首先，如上所述检查 s 的合理性，然后选择任何 s+m 使得距离 (s+m) == d-1。重复直到我们到达原点。
怎么样？
于 2016-12-19T15:18:59.223 回答
2
我认为这也可能对您有所帮助..
NumWays(x,y)=1+min(NumWays(x+-2,y-+1),NumWays(x+-1,y+-2));
并使用动态规划来获得解决方案。
PS：它有点使用 BFS，而不必费心声明图的节点和边。
于 2012-11-06T10:41:28.950 回答
2
/*
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.
我还没有研究过图表..根据通过简单数组实现它的问题，除此之外我无法得出任何解决方案。我不将位置视为等级和文件（通常的国际象棋符号），而是作为数组索引。仅供参考，这仅适用于 8*8 棋盘。任何改进建议总是受欢迎的。
*评论应该足以让您理解逻辑。但是，您可能总是会问。
*检查 DEV-C++ 4.9.9.2 编译器（流血软件）。
于 2011-10-07T12:17:56.263 回答
1
这是在 Perl 中实现的这个特定问题的解决方案。它将显示最短路径之一——在某些情况下可能不止一条。
我没有使用上述任何算法 - 但将它与其他解决方案进行比较会很好。
#!/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__
于 2013-12-31T19:04:21.493 回答
1
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));
}
}
于 2015-09-17T17:04:24.037 回答
0
只是来自Graeme Pyle's answer's answer's jsfiddle above 的ruby 代码，剥离了所有额外的代码并将剩余的代码转换为 ruby 只是为了通过他的算法获得解决方案，似乎工作正常。虽然仍在测试：
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)
如果有人需要完整的代码，唯一的目的是为某人节省一些时间来转换代码。
于 2016-11-14T07:49:17.143 回答
0
这是 Jules May 函数的 PHP 版本
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];
}
于 2017-03-13T14:38:57.210 回答
0
这是我的程序。这不是一个完美的解决方案。递归函数有很多变化。但是这个最终结果是完美的。我试着优化了一下。
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;
}
}
于 2017-05-21T23:25:23.293 回答
0
这是另一个有效的 Python 解决方案（来自 Johan du Toit）：
输入：
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))
于 2021-01-03T06:00:45.767 回答
0
这是一个基于 Mustafa Serdar Şanlı 代码的 C 版本，适用于有限板：
#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));
}
}
在这里用递归解决方案的证明来测试它
于 2017-05-19T10:49:58.150 回答