ナイトの移動で作ってみました。
import random import copy #舞台を作る mp=[[" " for x in range(8)] for y in range(8)]#map #障害物を置く for i in range(40): mp[random.randint(0,7)][random.randint(0,7)]="#" #開始位置と終了位置 startPos=(0,0)#Position endPos=(7,7) #開始位置と終了位置の障害撤去 mp[0][0]=" " mp[7][7]=" " #ナイトの移動できる位置 dx=[-1, 1, -2, 2,-2, 2,-1, 1] dy=[-2,-2, -1,-1, 1, 1, 2, 2] #移動できるか判定 def checkMove(x,y): if x<0 or y<0 or x>7 or y>7:return False return mp[y][x]==" " #答えを探す旅 searchPos=[(startPos,0,[startPos])]#検索位置、回数、移動した位置 checkEndPos=[(0,0)]#検索済みが入る answerPath=[] #検索位置がなくなるまで続ける while len(searchPos)>0: #移動方向検索 for dr in range(8):#direction pos,moveCount,pp=searchPos[0] posPath=copy.deepcopy(pp) sx,sy=pos tx=sx+dx[dr] ty=sy+dy[dr] #検索済みは対象外 if (tx,ty) in checkEndPos: continue if checkMove(tx,ty): posPath+=[(tx,ty)] if (tx,ty)==endPos:#ゴールにたどり着いていて新記録なら塗り替え if len(answerPath)==0 or len(answerPath)>len(posPath): answerPath=copy.deepcopy(posPath) else: checkEndPos+=[(tx,ty)] searchPos+=[( (tx,ty),moveCount+1,posPath )]#追加検索位置、回数+1、移動した位置を追加 del searchPos[0] #結果を舞台に繁栄 for i in range(len(answerPath)): x,y=answerPath[i] mp[y][x]=str(i) if answerPath==[]: print("残念ながら到達できません") #舞台を表示 for i in mp: print(" ".join(i))
実行例
0 # # # #
# 1 # 3 #
# # # # # #
# 2 # 4 #
# # # # #
# # 5 #
# # #
# # 6
0 # # #
# # 1 # #
2 # # #
3 # #
# # # # # #
# 4 # #
# # # 5 #
# # # # # 6
0 # # # 4 # #
# # 2 # # 5 #
# 1 # # 3 #
# # 6 #
# # # # #
# # 7 # #
# # 9
# 8 # 10
