Python-騎士旅程（擴充版）

(本篇文章利用Python實作)

這篇文章是昨天文章的小小延伸
如果有同學還沒看過的
推薦先看看昨天那一篇喔：
https://datascienceicwang.blogspot.com/2019/08/python.html

而昨天所做的棋盤大小是8*8
今天讓我們來擴充棋盤的大小吧

先預設個最大棋盤大小為30*30
其實要多大都可以
我們要讓使用者可以自行輸入值
也順便把移動的方向寫入

n = input('請輸入棋盤大小(一個數字)(介於8~30):')
n = int(n)
while n < 8 or n > 30:
    n = input('請輸入棋盤大小(一個數字)(介於8~30):')
    n = int(n)
    
## 8個移動方位
dx = [-2, -1, 1, 2, -2, -1, 1, 2]
dy = [1, 2, 2, 1, -1, -2, -2, -1]

接著我們的degree map在昨天是直接給各位
但現在由於無法預先知道大小
所以degree map需要自行產出
因此我們先寫一個放入0的degree map吧

## 產生初始degree map
degree_map = [[0 for x in range(n)] for y in range(n)] # chessboard
degree_map

接著degree map的概念其實就是上篇文章的available path的概念
也就是有多少格可以走到這個位置
因此我們把此概念寫進來

## 產生degree map
for i in range(0,n):
    for j in range(0,n):
        available_path = []
        for k in range(0,8):
            if i+dx[k] >= 0 and i+dx[k] <= n-1 and j+dy[k] >= 0 and j+dy[k] <= n-1:
                available_path.append([dx[k], dy[k]])
            else:
                continue
                
        degree_map[i][j] = len(available_path)

degree_map

首先要讓迴圈跑棋盤大小的n^2次
接著檢查是否有超出棋盤
就可以找出有幾個可行路徑走到該格了
而其長度便是degree
我們把它輸出來看看

這邊我是使用12*12為例

接著下面的程式碼就都一樣了
我一樣附出來
有興趣的同學可以參考一下囉

## 輸入初始位置
input_num = input('請輸入位置(介在0~你輸入的值-1)(用空格隔開):')
input_num = list(input_num.split())
[a, b] = [int(input_num[0]), int(input_num[1])]

while a < 0 or a > n-1 or b < 0 or b > n-1:
    input_num = input('請輸入位置(介在0~你輸入的值-1)(用空格隔開):')
    input_num = list(input_num.split())
    [a, b] = [int(input_num[0]), int(input_num[1])]

## 產生棋盤
cb = [[0 for x in range(n)] for y in range(n)] # chessboard

## 路徑及搜尋
for i in range(0, n*n):
    degree_map[a][b] = 0
    cb[a][b] = i+1
    
    ## 在最後一步不跳出error
    if cb[a][b] == n*n:
        break
    
    ## 找出合法路徑
    available_path = []
    for j in range(0,8):
        if a+dx[j] >= 0 and a+dx[j] <= n-1 and b+dy[j] >= 0 and b+dy[j] <= n-1:
            available_path.append([dx[j], dy[j]])
        else:
            continue

    ## 減去可行路徑的degree(dynamic)
    possible_path = []
    possible_path_degree = []
    for k in range(0, len(available_path)):
        degree_map[a+available_path[k][0]][b+available_path[k][1]] -= 1
        possible_path.append([available_path[k][0], available_path[k][1]])
        possible_path_degree.append(degree_map[a+available_path[k][0]][b+available_path[k][1]])
    
    while min(possible_path_degree) < 0:
        min_index = possible_path_degree.index(min(possible_path_degree))
        del possible_path[min_index]
        del possible_path_degree[min_index]
    
    min_index = possible_path_degree.index(min(possible_path_degree))
    move = possible_path[min_index]
        
    a += move[0]
    b += move[1]

for i in range(0, len(cb)):
    for j in range(0, len(cb[i])):
        print('%4d' % cb[i][j], end='')
    print('\n')

這就是當棋盤從8*8擴充到無限大時的方法
其實就是把degree map的產生方法寫出來
而這也歸功於原先的程式碼寫的方向就有考慮到未來的擴充性
但當要考慮擴充性時 就勢必要犧牲一些效能
所以如何在兩者間取捨
就端看各位的想法囉

所以今天學到的有：
產生degree map
複習騎士旅程
也期待未來有更多作品可以繼續跟各位分享~