骑士移动到任何指定目标所需的最大移动量

Question

你好，我是一个11年级的学生，在12年级的电脑课上用python编码。我想知道一个骑士在8乘8的格子上从任何给定的空间里捕捉国王需要多少步。我已经编写了使用递归来解决这个问题的代码，但是现在我一直在思考从任何给定的正方形中获得的最大移动量是多少，因为它比我要检查的移动情况运行得慢。我在堆栈溢出上也发现了类似的问题，但没有找到答案。如果你想看代码，请直接问。非常感谢您的回复。这就是我要解决的问题：

1. 在国际象棋比赛中，有一个棋子叫骑士。骑士沿着L形路径移动，在一个方向移动两个空格，然后在90°方向移动一个空格。
   8x8棋盘可以定义为二维列表，其中左上角为（1,1），右下角为（8,8）。在

在这个问题中，给你一个文本文件，骑士.txt，包含六行信息。第一行包含国王在棋盘上的位置。接下来的五行是棋盘上骑士的位置。你的任务是计算出骑士俘获国王需要多少步。 例如，如果文本文件骑士.txt包含以下内容： （6,3） （4,4） （6,6） （4,1） （2,5） （5,7）

程序的输出可以如下所示：

骑士招式

在（4，4）处的骑士需要1次移动才能在（6,3）时俘获国王。在

在（6，6）处的骑士需要3次移动才能在（6,3）时俘获国王。在

在（4,1）处的骑士需要4次移动才能在（6,3）时俘获国王。在

在（2,5）处的骑士需要2次移动才能在（6,3）时俘获国王。在

在（5，7）时骑士需要3次移动才能在（6,3）时俘获国王。在

到目前为止我写的代码：

print "Knight Moves"
print "------------\n"
#This function will try to find the shortest route to the king usi
def findDaKing(knightX,knightY,moveNum):
    #Checks if the king and knight are on the same spot
    if knightX <0 or knightX >7 or knightY <0 or knightY >7:
        pass
    elif chessBoard[knightY][knightX] == 1:
        return moveNum
    #finds if it has moved 10 times so i doesnt hit max resuresion depth or waste time
    if moveNum == 6:

        return -1
    #moves the knight
    else:
        #uses resursion so because i don't know how else to do it :)
        #finds the shorts route for each path and compares them

        shortestRoute = findDaKing(knightX+2,knightY-1,moveNum+1)
        temp =findDaKing(knightX+2,knightY+1,moveNum+1)
        #checks if it found a route
        if temp == -1:
            pass
        elif temp==1 or shortestRoute ==1:
            return 1
        #checks if the first one found a path and if not temp must be a shorter route or if its bigger than temp
        elif shortestRoute == -1 or shortestRoute> temp:
            shortestRoute  = temp
        temp =findDaKing(knightX+1,knightY-2,moveNum+1)
        #checks if it found a route
        if temp == -1:
            pass
        elif temp == 1:
            return 1
        #checks if the first one found a path and if not temp must be a shorter route or if its bigger than temp
        elif shortestRoute == -1 or shortestRoute> temp:
            shortestRoute  = temp
        temp =findDaKing(knightX+1,knightY+2,moveNum+1)
        #checks if it found a route
        if temp == -1:
            pass
        elif temp == 1:
            return 1
        #checks if the first one found a path and if not temp must be a shorter route or if its bigger than temp
        elif shortestRoute == -1 or shortestRoute> temp:
            shortestRoute  = temp
        temp =findDaKing(knightX-1,knightY+2,moveNum+1)
        #checks if it found a route
        if temp == -1:
            pass
        elif temp == 1:
            return 1
        #checks if the first one found a path and if not temp must be a shorter route or if its bigger than temp
        elif shortestRoute == -1 or shortestRoute> temp:
            shortestRoute  = temp
        temp =findDaKing(knightX-2,knightY+1,moveNum+1)
        #checks if it found a route
        if temp == -1:
            pass
        elif temp == 1:
            return 1
        #checks if the first one found a path and if not temp must be a shorter route or if its bigger than temp
        elif shortestRoute == -1 or shortestRoute> temp:
            shortestRoute  = temp
        temp =findDaKing(knightX-2,knightY-1,moveNum+1)
        #checks if it found a route
        if temp == -1:
            pass
        elif temp == 1:
            return 1
        #checks if the first one found a path and if not temp must be a shorter route or if its bigger than temp
        elif shortestRoute == -1 or shortestRoute> temp:
            shortestRoute  = temp
        temp =findDaKing(knightX-1,knightY-2,moveNum+1)
        #checks if it found a route
        if temp == -1:
            pass
        elif temp == 1:
            return 1
        #checks if the first one found a path and if not temp must be a shorter route or if its bigger than temp
        elif shortestRoute == -1 or shortestRoute> temp:
            shortestRoute  = temp
        #returns the shortest Route
        return shortestRoute
#checks if the format is right
def checkFormat(string):
    #checks if its the right len
    if len(string) !=5:
        return True
    #checks if it has the right syntax
    elif string[0] != "(" and string[4] != ")" and string[2] == ",":
        return True
    #checks if they are numbers
    elif not(string[1].isdigit()) and not(string[3].isdigit()):
        return True
    #else returns false so I know that it is the right format.
    return False
#This will be used to check if the text file failed to open
textFileFail = False
#trys to read from the text file
try:
    chessTextFile = [line.rstrip("\n") for line in open("knight.txt")]
except:
    #Prints that the text file failed and set the program no to run
    print "The text file failed to open."
    textFileFail = True
#This will be the 2-d list that holds the board
chessBoard = [  [0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0]
                ]
if textFileFail == False:
    #runs through all the lines in the text file
    for line in range(0,len(chessTextFile),1):
        #checks the format of the chess point
        Format = checkFormat(chessTextFile[line])
        #if the format error is true it failed to read it
        if Format == True:
            #print that it didnt work and what line the error was on
            print "Sorry the format for line",line+1,"was incorrect."
            #If it happened on the first line the reset of the program wont work so it just breaks else it continues in hopes of some working
            if line == 0:
                break
            else:
                continue
        #if its the first one I know its the kings x and y
        if line == 0:
            #sets the x and y based on the string in the list
            chessBoard[int(chessTextFile[line][3])][int(chessTextFile[line][1])] = 1
        #Else I know its a starting point
        else:
            #prints how many moves it will take
            print "It takes",findDaKing(int(chessTextFile[line][1]),int(chessTextFile[line][3]),0),"moves for the knight at",chessTextFile[line],"to capture the king at",chessTextFile[0]+"."

我希望这些评论能有所帮助。抱歉，如果它有点混乱或难以阅读。 附言。谢谢你的回答这是我第一次问问题。在

Answer 1

这是我的尝试，但没有得到很好的优化：

king = [4,1]
knight = [[6,3]]
c = 0
while king not in knight:
    moves = []
    for i in range(len(knight)):
        for j in [-1,1]:
            for k in [-2,2]:
                for l in [0,1]:
                    if knight[i][l] + j>0 and knight[i][l] +j < 9 and knight[i][abs(l-1)] + k > 0 and knight[i][abs(l-1)] + k < 9:
                        moves.append([0,0])
                        moves[len(moves)-1][l] = knight[i][l] + j
                        moves[len(moves)-1][abs(l-1)] = knight[i][abs(l-1)] + k
    c += 1
    knight = list(moves)
print(c)