کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875480 | 1441957 | 2018 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A simple proof that the (n2â¯ââ¯1)-puzzle is hard
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
The 15 puzzle is a classic reconfiguration puzzle with fifteen uniquely labeled unit squares within a 4Ã4 board in which the goal is to slide the squares (without ever overlapping) into a target configuration. By generalizing the puzzle to an nÃn board with n2â1 squares, we can study the computational complexity of problems related to the puzzle; in particular, we consider the problem of determining whether a given end configuration can be reached from a given start configuration via at most a given number of moves. This problem was shown NP-complete in [1]. We provide an alternative simpler proof of this fact by reduction from the rectilinear Steiner tree problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 732, 7 July 2018, Pages 80-84
Journal: Theoretical Computer Science - Volume 732, 7 July 2018, Pages 80-84
نویسندگان
Erik D. Demaine, Mikhail Rudoy,