کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648182 | 1342397 | 2012 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The Sudoku completion problem with rectangular hole pattern is NP-complete
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The sudoku completion problem is a special case of the latin square completion problem and both problems are known to be NP-complete. However, in the case of a rectangular hole pattern–i.e. each column (or row) is either full or empty of symbols–it is known that the latin square completion problem can be solved in polynomial time. Conversely, we prove in this paper that the same rectangular hole pattern still leaves the sudoku completion problem NP-complete.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 22, 28 November 2012, Pages 3306–3315
Journal: Discrete Mathematics - Volume 312, Issue 22, 28 November 2012, Pages 3306–3315
نویسندگان
Ramón Béjar, Cèsar Fernández, Carles Mateu, Magda Valls,