骑士移动到任何给定所需的最大移动量 space
Max amount of moves it would take knight to move to any give space
你好,我是一名 11 年级的学生,正在使用 12 年级的计算机 class 在 python 中编码。我试图计算出一个骑士在 8 x 8 网格上从任何给定的 space 捕获国王需要多少步。我已经编写了使用递归解决问题的代码,但现在我遇到了从任何给定方块获得的最大移动量的问题,因为它运行得较慢,我必须检查移动案例。我在堆栈溢出上发现了类似的问题,但没有回答我的问题。如果您想查看代码,请询问。感谢您的任何回复,我们将不胜感激。这是我要解决的问题:
- 在象棋游戏中,有一种棋子叫做马。骑士在 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)
你好,我是一名 11 年级的学生,正在使用 12 年级的计算机 class 在 python 中编码。我试图计算出一个骑士在 8 x 8 网格上从任何给定的 space 捕获国王需要多少步。我已经编写了使用递归解决问题的代码,但现在我遇到了从任何给定方块获得的最大移动量的问题,因为它运行得较慢,我必须检查移动案例。我在堆栈溢出上发现了类似的问题,但没有回答我的问题。如果您想查看代码,请询问。感谢您的任何回复,我们将不胜感激。这是我要解决的问题:
- 在象棋游戏中,有一种棋子叫做马。骑士在 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)