|
В книге "Вычислительные машины и труднорешаемые задачи" в главе А8 игры и головоломки, на стр. 331, задача ИГ14, написано:
УСЛОВИЕ: Заданы конечное множество слов W принадлежащие Е(Сигма) и матрица А из нулей и единиц размером nxn.
ВОПРОС: Можно ли составить кроссворд размером nxn из слов множества W так, что бы слова записывались в клетки, соответствующие 0 в А? Другими словами, если Е-это множество пар (i,j), таких что Аij=0, то существует ли отображение f: E->E(сигма), такое что буквы, приписываемые любой горизонтальной или вертикальной последовательности (максимальной длины) элементов из Е, образуют слово из W?
К таккой задаче сводится ТП-3 (номер задачи из этой же книги).
Комментарий. Задача остается NP-полной, даже если все элементы матрицы А есть нули.
====Конец цитаты из книги====
Из чего следует что кроссворд это все же NP-полная задача.
|
12.08.2009, 16:37 