8x8 棋盤路徑解之一般化推廣

科展類別
臺灣國際科展
屆次
2008年
科別
數學科
學校名稱
臺北縣立福和國民中學
指導老師
鄭釧鋒
作者
李建慈
關鍵字
棋盤 對稱

摘要或動機

Abstract (一)、 In our study, we discuss a m×n chess and any beginning square p finding a directed path of chessman from p moving to an end square in which the chessman moves to adjacent squares including only three directions which are right move, up move and diagonal left down move. A m×n chess is ruled into m columns and n rows creating the number of (m×n) squares (二)、 A chess directed path moves from any beginning square to end square in a m×n chess and every other square is visited just once. In the view of the beginning squares, the chess paths are solvable paths in a mxn chess and the corresponding squares are solutions. (三)、 First, we find out that some beginning squares are located in a special area with no any solvable directed paths. We define the special area be no-solution area. (四)、 According the 3-color theorem, we determine more than two thirds of no-solution area. (五)、 Then, we derive properties of reversibility and symmetry in solvable paths. i.e. A solvable path exist another solvable path by reversibility and symmetry respectively. (六)、 Utilizing the generalization of no-solution area which is extended from the concept of no-solution area provides judgment for the next moves effectively. The judgment is defined as effective move principle. (七)、 Furthermore, using the other theorem called rules of shift Hamiltonian path gets augment solutions. (八)、 According to the effective move principle finding a number of solvable directed paths, use the reversibility and rules of shift Hamiltonian paths to get augment solutions. Finally, utilize symmetry to find out all solvable paths in the m×n chess. (一)、研究規則:在m×n 的格子中,任取一格A 當作「起點格」,在起點格上放一顆棋子,只能往「上」、往「右」、往「左下」的方向移動。(二)、定義:若棋子從「起點格」,按照上述規則能不重複的通過所有m×n 格子到達某一「終點格」,則對於「起點格」而言,此移動路徑稱為m×n 的「有解路徑」,其任4一「終點格」稱為「起點格」的「路徑解」。(三)、我們先研究出「基本無解區」。(四)、根據遊戲規則我們利用三種顏色將n × n 方格塗滿,並判斷出大部分的「無解起點格」。(五)、利用遊戲規則得到兩重要性質:(1)[可逆性性質] (2) [對稱性性質](六)、利用「廣義基本無解區」,當作我們[有效移動]的判斷,讓「有解路徑」快速的找出。(七)、利用本研究所稱的「平移哈式鏈」,得到[擴充解]。(八)、根據[有效移動]求出部分「路徑解」,再利用[可逆性性質]、 [擴充解] ,最後利用[對稱性性質]完成所有「路徑解」的尋找。


「為配合國家發展委員會「推動ODF-CNS15251為政府為文件標準格式實施計畫」,以及 提供使用者有文書軟體選擇的權利,本館檔案下載部分文件將公布ODF開放文件格式, 免費開源軟體可至LibreOffice 下載安裝使用,或依貴慣用的軟體開啟文件。」

檔案名稱 檔案大小 格式
8x8 棋盤路徑解之一般化推廣 774 KB Adobe Reader(Pdf)檔案