01-6. 勇者之旅

https://teachinglondoncomputing.org/resources/inspiring-unplugged-classroom-activities/the-knights-tour-activity/

Computer Science activities with a sense of fun: night’s Tour V1.1, 14 Dec 2014

Created by Paul Curzon, Queen Mary University of London for Teaching London Computing: http://teachinglondoncomputing.org

Adapted from an idea by Maciej Syslo.& Anna Beata Kwiatkowska, Nicolaus Copernicus University

本教材以創用CC 3.0 姓名標示-非商業性-相同方式分享釋出(creative commons 3.0 BY-NC-SA) https://creativecommons.org/licenses/by-nc-sa/3.0/deed.zh_TW

遊戲說明:

1. 每個人需要一份移動規則表、一張空白迷宮方格圖以及一張已經畫好的圖形迷宮圖、一個「勇者卡片」、兩張路線記錄表（一張空白及一張路線說明）以及一支筆。

2. 跟旅遊嚮導活動一樣，先在一般圖形上設計勇者的探索路線。用紅筆標示想走的路線，起點的編號為１，最終必須造訪過所有12個房間，然後回到迷宮的起點。

3. 接下來，使用空白的迷宮方格，以及發下去的移動規則表，起點設在方格編號１的位置。勇者移動時必須按照移動規則表來進行，最後的目標一樣是要讓勇者踏遍所有的12個房間，再回到起點。

4. 任意與同學交換你設計出來的造訪步驟，必須讓別人也能按照你的設計完成目標，這才是一份有效的設計。

5. 思考一下，你覺得圖形的表示法比較容易協助你解決問題，還是迷宮方格比較容易？其實，如果把最後的終點一樣設成要回到編號１的房間，無論是旅遊嚮導或是勇者之旅，其實兩者是差不多的問題（這個動作稱為一般化generalise）。

6. 試著按照拿到的移動規則表，用「圖形」的方式設計出探索路線圖。每個房間設定成一個節點，就算房間原本是放置在隔壁的，按照規則重畫之後它將不見得還是會放在隔壁。路線連接之後的結果可能是任意形狀與大小，每個人的設計可能不見得一樣。

7. 舉個例子，按照移動規則表，１號房間之後的移動選擇可能是９號房間，而到達９號房間之後可以擇退回１號或是前進３號房間，如此即可完成一張圖形。但是進行第一步驟時，１號房間可能選擇走到７號，如此接下來繪製的圖形將會完全不同。

8. 等圖形完成之後，再試著完成路線設計表，看看有沒有變得比較簡單了。

1. 移動規則表

2. 空白迷宮圖

3. 圖形迷宮圖

4. 空白記錄表

參考解法：

運算思維:

除了在旅遊嚮導活動中學到的思維之外，在這裡我們學到了模式匹配(pattern matching)的概念。在重新繪製勇者移動的圖形之後，我們會發現其實它跟上一個活動的城市圖形是一模一樣的，只是把景點的名稱替換成阿拉伯數字的編號罷了。

另外，應用在規劃路線的方式，就是一直往尚未走過的房間前進，稱為深先搜尋(depth-first search)。而另一種策略稱為廣度優先搜尋(breadth-first search)，像是先將所有從１號房間通往９號房間的可能路線先畫出來，接著畫出所有通往６號房間的路線。這兩者都是圖形遍歷演算法(graph traversal algorithms)的一種。