DAY 29
1
Software Development

## Day29- 經典騎士漫步問題

`````` 1  4 27 42 53  6  9 12
26 43  2  5 46 11 52  7
3 28 45 54 41  8 13 10
44 25 58 61 64 47 40 51
29 60 55 48 57 50 63 14
24 19 22 59 62 37 34 39
21 30 17 56 49 32 15 36
18 23 20 31 16 35 38 33
``````

(我們只想找一組解，不想窮舉所有解)

# 遞迴思路

``````dirs = [(1, 2), (2, 1), (-1, 2), (-2, 1), (1, -2), (2, -1), (-1, -2), (-2, -1)] # 馬步的八個方向
find = False #全域變數，當find=True時停止搜索
chessboard = [[0]*8 for i in range(8)] #二維列表表示一個西洋棋的棋盤
chessboard[0][0]=1 #初始條件

# 默認參數curstep表示現在第幾步
def Move(pos, curstep=1):
chessboard[pos[0]][pos[1]]=curstep  #設定棋步
if curstep==64: #一旦找到一組解，印出解答並設find=True
for i in range(8):
print(' '.join([f"{chessboard[i][j]:2d}" for j in range(8)]))
global find
find = True
else:
for d in dirs: #檢查下一步我可以走的八個方向
nextPos = [pos[0]+d[0], pos[1]+d[1]]
if not find and 0<=nextPos[0]<=7 and 0<=nextPos[1]<=7 and chessboard[nextPos[0]][nextPos[1]]==0:
Move(nextPos, curstep+1)
chessboard[pos[0]][pos[1]]=0 #撤銷棋步

iniPos = (0,0) #初始座標
Move(iniPos)
``````

`````` 1  0 49  0 23  0  0 26
50  0  2 47 42 25 22  0
0 48 43 24  3 18 27 20
0  0 46 41 28 21  4  9
0 40 29 44 17 10 19 12
0 45 36 33 30 13  8  5
39 34 31 16 37  6 11 14
0  0 38 35 32 15  0  7
``````

# 技巧: 角落的格子優先走

``````dirs = [(1, 2), (2, 1), (-1, 2), (-2, 1), (1, -2), (2, -1), (-1, -2), (-2, -1)] # 馬步的八個方向
find = False #全域變數，當find=True時停止搜索
chessboard = [[0]*8 for i in range(8)] #二維列表表示一個西洋棋的棋盤
chessboard[0][0]=1 #初始條件

# 判斷一個座標是否可走
def valid(pos):
return 0<=pos[0]<=7 and 0<=pos[1]<=7 and chessboard[pos[0]][pos[1]]==0

# 計算一個格子座標的「邊緣分數」
def value(pos):
return min(pos[0],7-pos[0])+min(pos[1],7-pos[1])

# 默認參數curstep表示現在第幾步
def Move(pos, curstep=1):
chessboard[pos[0]][pos[1]]=curstep  #設定棋步
if curstep==64: #一旦找到一組解，印出解答並設find=True
for i in range(8):
print(' '.join([f"{chessboard[i][j]:2d}" for j in range(8)]))
global find
find = True
else:
#nextPos是下一步可以走的座標位置，依「邊緣分數」排序
nextPos = [[pos[0]+d[0], pos[1]+d[1]] for d in dirs]
nextPos = sorted(filter(lambda x: valid(x), nextPos), key= lambda x: value(x))
for p in nextPos: #檢查下一步我可以走的八個方向
if not find:
Move(p, curstep+1)
chessboard[pos[0]][pos[1]]=0 #撤銷棋步

iniPos = (0,0) #初始座標
Move(iniPos)
``````

`````` 1  4 27 42 53  6  9 12
26 43  2  5 46 11 52  7
3 28 45 54 41  8 13 10
44 25 58 61 64 47 40 51
29 60 55 48 57 50 63 14
24 19 22 59 62 37 34 39
21 30 17 56 49 32 15 36
18 23 20 31 16 35 38 33
``````

# 推廣: 解nxm棋盤的馬踏棋盤問題

``````class HorseWalk:

def __init__(self, r, c):
self.r = r
self.c = c
self.board = [[0]*c for i in range(r)] #二維列表表示一個西洋棋的棋盤
self.dirs = [(1, 2), (2, 1), (-1, 2), (-2, 1), (1, -2), (2, -1), (-1, -2), (-2, -1)] # 馬步的八個方向
self.find = False #全域變數，當find=True時停止搜索

# 判斷一個座標是否可走
def valid(self, pos):
return 0<=pos[0]<=self.r-1 and 0<=pos[1]<=self.c-1 and self.board[pos[0]][pos[1]]==0

# 計算一個格子座標的「邊緣分數」
def value(self, pos):
return min(pos[0],self.r-pos[0]-1)+min(pos[1],self.c-pos[1]-1)

# 默認參數curstep表示現在第幾步
def Move(self, pos, curstep=1):
self.board[pos[0]][pos[1]]=curstep  #設定棋步
if curstep==self.r * self.c: #一旦找到一組解，印出解答並設find=True
for i in range(self.r):
print(' '.join([f"{self.board[i][j]:2d}" for j in range(self.c)]))
self.find = True
else:
#nextPos是下一步可以走的座標位置，依「邊緣分數」排序
nextPos = [[pos[0]+d[0], pos[1]+d[1]] for d in self.dirs]
nextPos = sorted(filter(lambda x: self.valid(x), nextPos), key= lambda x: self.value(x))
for p in nextPos: #檢查下一步我可以走的八個方向
if not self.find:
self.Move(p, curstep+1)
self.board[pos[0]][pos[1]]=0 #撤銷棋步

iniPos = (0,0) #初始座標
solver = HorseWalk(6,6)
solver.Move(iniPos)
``````

`````` 1  4  7 10 43 86 63 36 41 38
8 11  2  5 62 75 42 39 64 35
3  6  9 44 85 78 87 74 37 40
12 45 58 61 80 83 76 89 34 65
57 60 81 84 77 88 79 68 73 90
46 13 56 59 82 69 72 31 66 33
19 16 49 70 55 52 67 28 25 30
14 47 18 21 50 71 54 23 32 27
17 20 15 48 53 22 51 26 29 24
``````

### 1 則留言

0
rex1206
iT邦新手 5 級 ‧ 2021-09-07 21:35:32
``````def next_possible(i, j, step, sort=True):
next_poss = []
for k in [(1,2), (1,-2), (-1,2), (-1,-2), (2,1), (2,-1), (-2,1), (-2,-1)]:
if 0 <= i + k[0] <= 7 and 0 <= j + k[1] <= 7 and not ((i + k[0]),(j + k[1])) in step : next_poss.append(((i + k[0]),(j + k[1])))
if sort: #第二個迴圈就不用排列
next_poss = sorted(next_poss, key = lambda x : len(next_possible(x[0],x[1],step, False)))
return next_poss

def steps(i=0,j=0, step = []):
step.append((i,j)) #step為走過的列表
if len(step) == 64: #列表長度為64，即為全部走完
for i in range(8):
print(' '.join([f"{step.index((i,j)):2d}" for j in range(8)]))
return True
for i, j in next_possible(i, j, step):
if steps(i,j,step): return True # 迴圈的結果為True：返回上一層函數，結果為False：next_possible的下一個可能
step.pop() # 刪除最後一步
return False #所有 next_possible 都是死路，返回上一層函數

steps()
``````