骑士移动到任何给定所需的最大移动量 space

Max amount of moves it would take knight to move to any give space

你好,我是一名 11 年级的学生,正在使用 12 年级的计算机 class 在 python 中编码。我试图计算出一个骑士在 8 x 8 网格上从任何给定的 space 捕获国王需要多少步。我已经编写了使用递归解决问题的代码,但现在我遇到了从任何给定方块获得的最大移动量的问题,因为它运行得较慢,我必须检查移动案例。我在堆栈溢出上发现了类似的问题,但没有回答我的问题。如果您想查看代码,请询问。感谢您的任何回复,我们将不胜感激。这是我要解决的问题:

  1. 在象棋游戏中,有一种棋子叫做马。骑士在 L 路径上移动,在一个方向上移动两个 space,然后在 90O 方向移动一个 space。
    一个 8x8 的棋盘可以定义为左上角为 (1,1),右下角为 (8,8) 的二维列表。

在这道题中,您将得到一个文本文件 knight.txt,其中包含六行信息。第一行包含国王在棋盘上的位置。接下来的五行包含骑士在棋盘上的位置。你的任务是计算出骑士俘获国王所需的步数。 例如,如果文本文件 knight.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]+"."

希望评论对您有所帮助。抱歉,如果它有点混乱或难以阅读。 Ps。谢谢大家的回复 这是我第一次提问。

这是我的尝试,但没有得到很好的优化:

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)