کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10328700 | 684868 | 2005 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Optimal algorithms for constructing knight's tours on arbitrary nÃm chessboards
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
The knight's tour problem is an ancient puzzle whose goal is to find out how to construct a series of legal moves made by a knight so that it visits every square of a chessboard exactly once. In previous works, researchers have partially solved this problem by offering algorithms for subsets of chessboards. For example, among prior studies, Parberry proposed a divided-and-conquer algorithm that can build a closed knight's tour on an nÃn, an nÃ(n+1) or an nÃ(n+2) chessboard in O(n2) (i.e., linear in area) time on a sequential processor. In this paper we completely solve this problem by presenting new methods that can construct a closed knight's tour or an open knight's tour on an arbitrary nÃm chessboard if such a solution exists. Our algorithms also run in linear time (O(nm)) on a sequential processor.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 146, Issue 3, 15 March 2005, Pages 219-232
Journal: Discrete Applied Mathematics - Volume 146, Issue 3, 15 March 2005, Pages 219-232
نویسندگان
Shun-Shii Lin, Chung-Liang Wei,