以線性時間在10 × n及其衍生之矩形棋盤上建構(1, 4)-開放騎士路徑之演算法

Abstract

騎士路徑問題(knight’s tour problem)已經被研究很長的一段時間，它的目的為在一棋盤上要找出一條路徑讓騎士能走過棋盤上的每一個格子恰好一次。2005年，此問題被林順喜教授和研究生魏仲良完全破解。2005年，Chia和Ong提出一般化的(a, b)-騎士路徑問題。2009年，Huang和Bai將一般化的(a, b)-騎士路徑問題簡化為 (1, k)-騎士路徑問題，並且找出了部份盤面的(1, k)-開放騎士路徑。而在本篇論文中，我們提出一個新的方法可以找出盤面的某一邊長為10，另一邊長為任意大小或者盤面某一邊長為10r，另一邊長為8s+10t的(1, k)-開放騎士路徑。而且此演算法在建構(1, k)-開放騎士路徑所需的執行時間為線性的，可以達到成本最佳化。

The knight’s tour problem has been studied for a very long period of time. The main purpose of the knight’s tour problem is to find out a series of moves made by a knight visiting every square of a chessboard exactly once. The knight’s tour problem has been solved completely by Lin and Wei in 2005. Chia and Ong have presented the generalized (a, b)-knight’s tours problem for the first time. Huang and Bai have simplified the generalized knight’s tours problem to the (1, k)-knight’s tour problem, and have solved it partly. In this thesis, we propose a new algorithm to solve the (1, k)-open knight’s tour problem where the size of one side of the chessboard is equal to 10 and the size of the other side is arbitrary, or the size of the chessboard is equal to 10r and the size of the other side is equal to 8s+10t. Our algorithm runs in linear time on a sequential processor.