По математике , учитывая сборникиз подмножеств некоторого множества X , точное покрытие является поднабором из так что каждый элемент в содержится ровно в одном подмножестве в. Говорят, что каждый элемент в покрывается ровно одним подмножеством в. Точная обложка - это своего рода обложка .
В информатике , то точная проблема покрытия является проблемой решения , чтобы определить , есть ли точная крышка существует. Проблема точного покрытия является NP-полной [1] и является одной из 21 NP-полных проблем Карпа . [2] Проблема точного покрытия - это своего рода проблема удовлетворения ограничений .
Проблема точного покрытия может быть представлена матрицей инцидентности или двудольным графом .
Алгоритм Кнута X - это алгоритм, который находит все решения точной проблемы покрытия. DLX - это имя, данное алгоритмукогда это эффективно реализовано с использованием техники Дональда Кнута « Танцующие ссылки» на компьютере. [3]
Стандартную задачу о точном покрытии можно немного обобщить, включив в нее не только «ровно одно» ограничение, но также «не более одного».
Нахождение мозаик Пентамино и решение судоку - достойные внимания примеры задач с точным покрытием. Проблема n ферзей - это слегка обобщенная проблема точных покрытий.
Формальное определение
Учитывая коллекцию из подмножеств некоторого множества, точное покрытие это подколлекция из который удовлетворяет двум условиям:
- Пересечение любых двух различных подмножеств вявляется пустым , т.е. подмножестваявляются попарно не пересекаются . Другими словами, каждый элемент всодержится не более чем в одном подмножестве в.
- Объединение подмножеств в является , т. е. подмножества в покрытие . Другими словами, каждый элемент всодержится хотя бы в одном подмножестве в.
Короче говоря, точное покрытие является «точным» в том смысле, что каждый элемент в содержится ровно в одном подмножестве в.
Эквивалентно точное покрытие это подколлекция из эти перегородки .
Для точного покрытия для существования необходимо, чтобы:
- Объединение подмножеств в является . Другими словами, каждый элемент в содержится хотя бы в одном подмножестве в .
Если пустое множество ∅ содержится в, то не имеет значения, находится ли он в какой-либо конкретной обложке. Таким образом, типично предположить, что:
- Пустого набора нет в . Другими словами, каждое подмножество в содержит хотя бы один элемент.
Основные примеры
Пусть S = { N , O , P , E } набор подмножеств множества X = {1, 2, 3, 4} такой, что:
- N = {},
- О = {1, 3},
- P = {2, 3} и
- E = {2, 4}.
Поднаборка { O , E } является точным покрытием X , поскольку подмножества O = {1, 3} и E = {2, 4} не пересекаются и их объединение равно X = {1, 2, 3, 4}.
Поднабор { Н , О , Е } также точная крышка X . Включение пустого множества N = {} не имеет значения, поскольку оно не пересекается со всеми подмножествами и не меняет объединение.
Поднабор { Е , Р } не является точным крышка X . Пересечение подмножеств E и P , {2}, не пусто: подмножества E и P не пересекаются. Более того, объединение подмножеств E и P , {2, 3, 4}, не является X = {1, 2, 3, 4}: ни E, ни P не покрывают элемент 1.
С другой стороны, не существует точного покрытия - более того, даже покрытия - для Y = {1, 2, 3, 4, 5}, потому чтоявляется собственным подмножеством Y : Ни одно из подмножеств в S не содержит элемент 5.
Подробный пример
Пусть S = { A , B , C , D , E , F } набор подмножеств множества X = {1, 2, 3, 4, 5, 6, 7} такой, что:
- А = {1, 4, 7};
- B = {1, 4};
- С = {4, 5, 7};
- D = {3, 5, 6};
- E = {2, 3, 6, 7}; а также
- F = {2, 7}.
Тогда подколлекция S * = { B , D , F } является точным покрытием, поскольку каждый элемент в X содержится ровно в одном из подмножеств:
- B = {1, 4};
- D = {3, 5, 6}; или же
- F = {2, 7}.
Более того, { B , D , F } - единственное точное покрытие, как показывает следующий аргумент: поскольку A и B - единственные подмножества, содержащие 1, точное покрытие должно содержать A или B , но не оба. Если точная крышка содержит А , то она не содержит B , C , E или F , так как каждый из этих подмножеств имеет элемент общего с A . Тогда D является единственным оставшимся подмножеством, но набор { , D } не покрывает элемент 2. В заключении, нет точной крышки , содержащей A . С другой стороны, если точная крышка содержит B , то она не содержит A или C , так как каждый из этих подмножеств имеет элемент общего с B . Поскольку D - единственное оставшееся подмножество, содержащее 5, D должно быть частью точного покрытия. Если точная крышка содержит D , то она не содержит Е , а Е имеет элемент общего с D . Тогда F - единственное оставшееся подмножество, и набор { B , D , F } действительно является точным покрытием. См. Пример в статье об алгоритме Кнута X для матричной версии этого аргумента.
Представления
Точная проблема , крышка определяются бинарным отношением «содержит» между подмножествами в S и элементами в X . Существуют различные эквивалентные способы представления этого отношения.
Стандартное представление
Стандартный способ представить отношение «содержит» - это перечислить элементы в каждом подмножестве.
Например, в приведенном выше подробном примере используется это стандартное представление:
- А = {1, 4, 7};
- B = { 1 , 4 };
- С = {4, 5, 7};
- D = { 3 , 5 , 6 };
- E = {2, 3, 6, 7}; а также
- F = { 2 , 7 }.
Опять же, подколлекция S * = { B , D , F } является точной обложкой, поскольку каждый элемент содержится ровно в одном выбранном подмножестве, как видно из выделения.
Обратное представление
Отношение «содержит» между подмножествами и элементами можно преобразовать , перечислив подмножества, в которых содержится каждый элемент.
Например, отношение «содержит» в подробном примере выше может быть представлено перечислением подмножеств, в которых содержится каждый элемент:
- 1 - элемент A , B ;
- 2 - элемент E , F ;
- 3 - элемент D , E ;
- 4 - элемент A , B , C ;
- 5 - элемент C , D ;
- 6 - элемент D , E ; а также
- 7 представляет собой элемент A , C , E , F .
Опять же, подколлекция S * = { B , D , F } является точной обложкой, поскольку каждый элемент содержится ровно в одном выбранном подмножестве, как видно из выделения.
При решении задачи точного покрытия часто бывает полезно переключаться между стандартным и обратным представлениями.
Представления матриц и гиперграфов
Отношение «содержит» может быть представлено матрицей инцидентности .
Матрица включает одну строку для каждого подмножества S и один столбец для каждого элемента в X . Запись в конкретной строке и столбце равна 1, если соответствующее подмножество содержит соответствующий элемент, и 0 в противном случае. Поскольку каждая строка представляет элементы, содержащиеся в соответствующем подмножестве, а каждый столбец представляет подмножества, содержащие соответствующий элемент, матрица инцидентности эффективно обеспечивает как стандартное, так и обратное представление.
В матричном представлении точное покрытие - это такой набор строк, в котором каждый столбец содержит 1 ровно в одной выбранной строке.
Например, отношение «содержит» в подробном примере выше может быть представлено матрицей инцидентности 6 × 7: [4]
1 2 3 4 5 6 7 А 1 0 0 1 0 0 1 B 1 0 0 1 0 0 0 C 0 0 0 1 1 0 1 D 0 0 1 0 1 1 0 E 0 1 1 0 0 1 1 F 0 1 0 0 0 0 1
Опять же, подколлекция S * = { B , D , F } является точной обложкой, поскольку каждый элемент содержится ровно в одном выбранном подмножестве, то есть каждый столбец содержит 1 ровно в одной выбранной строке, как видно из выделения.
См. Пример в статье об алгоритме Кнута X для матричного решения подробного примера выше.
В свою очередь, матрицу инцидентности можно также рассматривать как описание гиперграфа . Гиперграф включает по одному узлу для каждого элемента в X и по одному ребру для каждого подмножества в S ; каждый узел входит ровно в одну из кромок, образующих крышку.
Графическое представление
Отношение «содержит» может быть представлено двудольным графом .
Вершины графа разделены на два множества не пересекаются, одной представляющей подмножества в S , а другой , представляющий элементы в X . Если подмножество содержит элемент, ребро соединяет соответствующие вершины в графе.
В представлении графа точное покрытие - это набор вершин, соответствующих подмножествам, таким образом, что каждая вершина, соответствующая элементу, соединена ровно с одной выбранной вершиной.
Например, отношение «содержит» в приведенном выше подробном примере может быть представлено двудольным графом с 6 + 7 = 13 вершинами:
Опять же, подколлекция S * = { B , D , F } является точным покрытием, поскольку каждый элемент содержится ровно в одном выбранном подмножестве, т. Е. Вершина, соответствующая каждому элементу в X , соединена ровно с одной выбранной вершиной, поскольку выделение проясняет.
Эквивалентные проблемы
Хотя каноническая проблема точного покрытия включает набор S подмножеств множества X , логика не зависит от наличия подмножеств, содержащих элементы. «Абстрактная проблема точного покрытия» возникает всякий раз, когда существует неоднородное отношение между двумя наборами P и Q, и цель состоит в том, чтобы выбрать подмножество P * из P так , чтобы каждый элемент в Q был связан ровно с одним элементом в P * . В общем, элементы P представляют выбор, а элементы Q представляют собой «ровно одно» ограничение на этот выбор.
Более формально, учитывая бинарное отношение R ⊆ P × Q между множествами P и Q , можно назвать подмножество P * из P «абстрактным точным покрытием» Q, если каждый элемент в Q является R T -связанным ровно с одним элементом в P * . Здесь Р Т представляет собой обратное из R .
В общем, R T ограничено до Q × P * является функцией от Q до P * , который отображает каждый элемент в Q с уникальным элементом в Р * , который является Р о связанных с этим элементом в Q . Эта функция на , если P * не содержит «пустое множество» , то есть, элемент , который не является R о связанном с каким - либо элементом в Q .
В канонической задаче точного покрытия P - это набор S подмножеств X , Q - это множество X , R - бинарное отношение, «содержащее» между подмножествами и элементами, и R T, ограниченное до Q × P *, - это функция содержится в "от элементов к выбранным подмножествам.
Набор точных ударов
В математике , учитывая набор S подмножеств множества X , точное совпадение множества X * - это подмножество X, такое, что каждое подмножество в S содержит ровно один элемент в X * . Говорят, что в каждое подмножество S попадает ровно один элемент в X * .
В информатике , то точное ударять Поставленная задача является проблемой решение найти точный набор удара или же определить его не существует.
Проблема точного набора совпадений является абстрактной проблемой точного покрытия. В обозначениях выше , Р есть множество Х , Q представляет собой набор S подмножеств X , R представляет собой бинарное отношение «содержится в» между элементами и подмножествами, и R -1 ограничивается Q × P * является функцией " содержит "от подмножеств до выбранных элементов.
В то время как проблема точного покрытия включает в себя выбор подмножеств, а отношение «содержит» от подмножеств к элементам, задача точного совпадения включает выбор элементов, а отношение «содержится в» от элементов к подмножествам. В некотором смысле проблема точного совпадения множества является обратной проблемой точного покрытия, включающей тот же самый набор и набор подмножеств.
Пример набора точных ударов
Как и в подробном примере точной обложки выше, пусть S = { A , B , C , D , E , F } будет набором подмножеств множества X = {1, 2, 3, 4, 5, 6, 7} такой, что:
- А = { 1 , 4, 7};
- B = { 1 , 4};
- С = {4, 5 , 7};
- D = {3, 5 , 6};
- E = { 2 , 3, 6, 7}; а также
- F = { 2 , 7}.
Тогда X * = {1, 2, 5} - это точное совпадение, поскольку каждое подмножество в S содержит ровно один элемент в X * , как видно из выделения.
Более того, {1, 2, 5} - это единственный точный набор совпадений, как демонстрирует следующий аргумент: поскольку 2 и 7 - единственные элементы, которые попадают в F , точный набор совпадений должен содержать 2 или 7, но не оба. Если точный набор совпадений содержит 7, то он не содержит 1, 2, 3, 4, 5 или 6, поскольку каждый из этих элементов содержится в некотором подмножестве, также содержащем 7. Тогда больше нет оставшихся элементов, но {7} не является точно поражая множество, так как он не попал B или D . В заключение, не существует точного набора совпадений, содержащего 7. С другой стороны, если точное множество совпадений содержит 2, то оно не содержит 3, 6 или 7, поскольку каждый из этих элементов содержится в некотором подмножестве, также содержащем 2. Из - 5 остается единственным элементом , который попадает D , точный набор удара должен содержать 5. Если точный набор содержит 5 удара, то она не содержит 4, так как и хит C . Поскольку 1 - единственный оставшийся элемент, который попадает в A , точный набор совпадений должен содержать 1. Тогда больше нет оставшихся элементов, и {1, 2, 5} действительно является точным множеством совпадений.
Хотя этот пример включает тот же набор подмножеств, что и приведенный выше подробный пример точной обложки, по сути, это другая проблема. В некотором смысле проблема точного набора совпадений является обратной (или транспонированной, или обратной) соответствующей задачи точного покрытия выше, как ясно из матричного представления:
А B C D E F 1 1 1 0 0 0 0 2 0 0 0 0 1 1 3 0 0 0 1 1 0 4 1 1 1 0 0 0 5 0 0 1 1 0 0 6 0 0 0 1 1 0 7 1 0 1 0 1 1
Двойной пример
Но есть еще одна проблема с точным попаданием в набор, которая по существу такая же, как и в приведенном выше подробном примере с точной обложкой , в котором пронумерованные элементы становятся подмножествами, а подмножества, отмеченные буквами, становятся элементами, эффективно инвертируя отношения между подмножествами и элементом.
Например, поскольку подмножество B содержит элементы 1 и 4 в задаче точного покрытия, подмножества I и IV содержат элемент b в двойной задаче о точном множестве совпадений.
В частности, пусть S = { I , II , III , IV , V , VI , VII } набор подмножеств множества X = { a , b , c , d , e , f } такой, что:
- I = { a , b }
- II = { e , f }
- III = { d , e }
- IV = { a , b , c }
- V = { c , d }
- VI = { d , e }
- VII = { a , c , e , f }
Тогда X * = { b , d , f } является точным множеством совпадений, поскольку каждое подмножество в S содержит (попадает) ровно один элемент в X * , как видно из выделения.
Точное множество совпадений X * = { b , d , f } здесь по существу такое же, как точное покрытие S * = { B , D , F } выше, как ясно из матричного представления:
я II III IV V VI VII а 1 0 0 1 0 0 1 б 1 0 0 1 0 0 0 c 0 0 0 1 1 0 1 d 0 0 1 0 1 1 0 е 0 1 1 0 0 1 1 ж 0 1 0 0 0 0 1
Поиск решений
Алгоритм X - это название, которое Дональд Кнут назвал «наиболее очевидным методом проб и ошибок» для поиска всех решений проблемы точного покрытия. [3] Технически, алгоритм Х является рекурсивным , недетерминирован , в глубине , возвраты алгоритма .
Когда алгоритм X эффективно реализуется с использованием техники Donald Knuth 's Dancing Links на компьютере, Кнут называет его DLX. DLX использует матричное представление проблемы, реализованное в виде серии двусвязных списков единиц матрицы: каждый элемент 1 имеет ссылку на следующую 1 выше, ниже, слева и справа от себя. (Технически, поскольку списки круговые, это образует тор). Поскольку проблемы с точным прикрытием обычно редки, такое представление обычно намного эффективнее как по размеру, так и по времени обработки. Затем DLX использует технику танцующих связей для быстрого выбора перестановок строк в качестве возможных решений и для эффективного отслеживания (отмены) ошибочных предположений. [3]
Обобщения
В стандартной задаче точного покрытия каждое ограничение должно выполняться ровно один раз. Это простое обобщение, позволяющее немного ослабить это требование и учесть возможность того, что некоторые «первичные» ограничения должны удовлетворяться только одним выбором, а другие «вторичные» ограничения могут быть удовлетворены не более чем одним выбором.
Как объясняет Кнут, обобщенную задачу о точном покрытии можно преобразовать в эквивалентную задачу о точном покрытии, просто добавив одну строку для каждого вторичного столбца, содержащую одну единицу в этом столбце. [5] Если в конкретном возможном решении удовлетворяется конкретный вторичный столбец, то добавленная строка не нужна. Но если вторичный столбец не удовлетворяет требованиям, как это разрешено в обобщенной задаче, но не в стандартной задаче, то можно выбрать добавленную строку, чтобы гарантировать соответствие столбца.
Но Кнут продолжает объяснять, что лучше работать с обобщенной проблемой напрямую, потому что обобщенный алгоритм проще и быстрее: простое изменение его алгоритма X позволяет напрямую обрабатывать вторичные столбцы.
Задача N ферзей является примером обобщенной задачи точного покрытия, поскольку ограничения, соответствующие диагоналям шахматной доски, имеют максимум, а не точное количество ферзей .
Примечательные примеры
Благодаря своей NP-полноте, любая проблема в NP может быть сведена к задачам точного покрытия, которые затем могут быть решены с помощью таких методов, как Dancing Links. Однако для некоторых хорошо известных проблем сокращение особенно прямое. Например, и задача выложить доску плиткой с пентамино , и решение судоку могут рассматриваться как проблемы с точным прикрытием.
Пентамино черепица
Как объясняет Дональд Кнут в своей статье «Танцующие звенья», задача выложить плиткой доску из 60 квадратов 12 различными свободными пентамино - это пример точной задачи с укрытием . [3]
Например, рассмотрим задачу о мозаике пентамино на шахматной доске 8 × 8 с удаленными 4 центральными квадратами:
11 12 13 14 15 16 17 18 21 год 22 23 24 25 26 год 27 28 год 31 год 32 33 34 35 год 36 37 38 41 год 42 43 год 46 47 48 51 52 53 56 57 год 58 61 62 63 64 65 66 67 68 71 72 73 74 75 76 77 78 81 год 82 83 84 85 86 87 88
Проблема включает в себя два вида ограничений:
- Пентамино: для каждого из 12 пентамино существует ограничение, заключающееся в том, что оно должно быть размещено ровно один раз. Назовите эти ограничения после соответствующих пентамино: FILPNTUVWXY Z. [6]
- Квадрат: для каждого из 60 квадратов существует ограничение: он должен быть покрыт пентамино ровно один раз. Назовите эти ограничения после соответствующих квадратов на доске: ij , где i - это ранг, а j - файл.
Таким образом, всего существует 12 + 60 = 72 ограничений.
Поскольку оба вида ограничений представляют собой «ровно одно» ограничение, проблема является проблемой точного покрытия.
Задача включает в себя множество вариантов, по одному для каждого способа размещения пентамино на доске. Удобно рассматривать каждый выбор как удовлетворяющий набору из 6 ограничений: 1 ограничение для размещаемого пентамино и 5 ограничений для пяти квадратов, на которых оно размещается.
В случае шахматной доски 8 × 8 с удаленными 4 центральными квадратами существует 1568 таких вариантов, например:
- {F, 12, 13, 21, 22, 32}
- {F, 13, 14, 22, 23, 33}
- …
- {I, 11, 12, 13, 14, 15}
- {I, 12, 13, 14, 15, 16}
- …
- {L, 11, 21, 31, 41, 42}
- {L, 12, 22, 32, 42, 43}
- …
Одним из многих решений этой проблемы точного покрытия является следующий набор из 12 вариантов:
- {I, 11, 12, 13, 14, 15}
- {N, 16, 26, 27, 37, 47}
- {L, 17, 18, 28, 38, 48}
- {U, 21, 22, 31, 41, 42}
- {X, 23, 32, 33, 34, 43}
- {W, 24, 25, 35, 36, 46}
- {P, 51, 52, 53, 62, 63}
- {F, 56, 64, 65, 66, 75}
- {Z, 57, 58, 67, 76, 77}
- {Т, 61, 71, 72, 73, 81}
- {V, 68, 78, 86, 87, 88}
- {Y, 74, 82, 83, 84, 85}
Этот набор вариантов соответствует следующему решению проблемы мозаики пентамино:
Проблема мозаики пентамино более естественно рассматривается как проблема точного покрытия, чем проблема точного попадания в множество, потому что более естественно рассматривать каждый выбор как набор ограничений, чем каждое ограничение как набор вариантов.
Каждый выбор связан всего с 6 ограничениями, которые легко перечислить. С другой стороны, каждое ограничение относится ко многим вариантам, которые труднее перечислить.
Независимо от того, рассматривается ли это как проблема точного покрытия или проблема с точным попаданием в набор, матричное представление одно и то же: 1568 строк соответствуют вариантам выбора, а 72 столбца соответствуют ограничениям. Каждая строка содержит одну единицу в столбце, идентифицирующем пентамино, и пять единиц в столбцах, определяющих квадраты, покрытые пентамиино.
Используя матрицу, компьютер может относительно быстро находить все решения, например, используя Dancing Links .
Судоку
Основные статьи: судоку , математика судоку , алгоритмы решения судоку
Проблема в судоку состоит в том, чтобы присвоить числа (или цифры, значения, символы) ячейкам (или квадратам) в сетке, чтобы удовлетворить определенные ограничения.
В стандартном варианте судоку 9 × 9 есть четыре вида ограничений:
- Строка-столбец: каждое пересечение строки и столбца, т. Е. Каждая ячейка, должно содержать ровно одно число.
- Номер строки : каждая строка должна содержать каждое число ровно один раз.
- Номер столбца : каждый столбец должен содержать каждое число ровно один раз.
- Номер ящика : каждое поле должно содержать каждое число ровно один раз.
Хотя первое ограничение может показаться тривиальным, оно, тем не менее, необходимо, чтобы на каждую ячейку приходилось только одно число. Интуитивно понятно, что размещение числа в ячейке запрещает размещение этого числа в любой другой ячейке, имеющей тот же столбец, строку или поле, а также запрещает размещение любого другого числа в уже занятой ячейке.
Решение судоку - это точная проблема прикрытия.
Точнее, решение судоку - это проблема с точным совпадением множества , которая эквивалентна задаче с точным покрытием, если рассматривать ее как проблему выбора возможностей, так что каждый набор ограничений содержит (т. Е. Затрагивается) ровно одну выбранную возможность. В приведенных выше обозначениях для (обобщенной) задачи точного покрытия X - это набор возможностей, Y - это набор наборов ограничений, а R - бинарное отношение «содержится в».
Каждое возможное присвоение определенного номера определенной ячейке является возможностью (или кандидатом). Когда в судоку играют карандашом и бумагой, такие возможности часто называют карандашными отметками.
В стандартном варианте судоку 9 × 9, в котором каждой из ячеек 9 × 9 присваивается одно из 9 номеров, существует 9 × 9 × 9 = 729 возможностей. Используя очевидные обозначения для строк, столбцов и чисел, возможности можно обозначить
- R1C1 # 1, R1C1 # 2,…, R9C9 # 9.
Тот факт, что каждый вид ограничения включает в себя ровно одно из чего-то, делает судоку задачей с точным совпадением множества. Ограничения могут быть представлены наборами ограничений . Проблема состоит в том, чтобы выбрать такие возможности, чтобы каждый набор ограничений содержал (т. Е. Затрагивал) только одну выбранную возможность.
В стандартном варианте судоку 9 × 9 существует четыре вида наборов ограничений, соответствующих четырем видам ограничений:
- Строка-столбец: Набор ограничений строка-столбец содержит все возможности для пересечения конкретной строки и столбца, т. Е. Для ячейки. Например, набор ограничений для строки 1 и столбца 1, который можно обозначить как R1C1, содержит 9 возможностей для строки 1 и столбца 1, но разные числа:
- R1C1 = {R1C1 # 1, R1C1 # 2, R1C1 # 3, R1C1 # 4, R1C1 # 5, R1C1 # 6, R1C1 # 7, R1C1 # 8, R1C1 # 9}.
- Номер строки : набор ограничений количества строк содержит все возможности для конкретной строки и номера. Например, набор ограничений для строки 1 и номера 1, который можно обозначить как R1 # 1, содержит 9 возможностей для строки 1 и номера 1, но разные столбцы:
- R1 # 1 = {R1C1 # 1, R1C2 # 1, R1C3 # 1, R1C4 # 1, R1C5 # 1, R1C6 # 1, R1C7 # 1, R1C8 # 1, R1C9 # 1}.
- Номер столбца : набор ограничений номера столбца содержит все возможности для определенного столбца и номера. Например, набор ограничений для столбца 1 и номера 1, который можно обозначить как C1 # 1, содержит 9 возможностей для столбца 1 и номер 1, но разные строки:
- C1 # 1 = {R1C1 # 1, R2C1 # 1, R3C1 # 1, R4C1 # 1, R5C1 # 1, R6C1 # 1, R7C1 # 1, R8C1 # 1, R9C1 # 1}.
- Номер ящика : набор ограничений количества ящиков содержит все возможности для конкретного ящика и номера. Например, набор ограничений для поля 1 (в верхнем левом углу) и номера 1, который можно обозначить как B1 # 1, содержит 9 возможностей для ячеек в поле 1 и номере 1:
- B1 # 1 = {R1C1 # 1, R1C2 # 1, R1C3 # 1, R2C1 # 1, R2C2 # 1, R2C3 # 1, R3C1 # 1, R3C2 # 1, R3C3 # 1}.
Поскольку имеется 9 строк, 9 столбцов, 9 блоков и 9 чисел, имеется 9 × 9 = 81 набор ограничений для номеров строк, 9 × 9 = 81 набор ограничений для номеров строк, 9 × 9 = 81 набор ограничений для номеров столбцов, и 9 × 9 = 81 набор ограничений для количества блоков: всего 81 + 81 + 81 + 81 = 324 набора ограничений.
Вкратце, стандартный вариант судоку 9 × 9 - это задача точного набора совпадений с 729 возможностями и 324 наборами ограничений. Таким образом, проблема может быть представлена матрицей 729 × 324.
Хотя представить всю матрицу 729 × 324 сложно, общий характер матрицы можно увидеть на нескольких снимках:
|
|
|
|
Полную матрицу 729 × 324 можно получить у Роберта Хэнсона. [7]
Обратите внимание, что набор возможностей R x C y # z может быть расположен как куб 9 × 9 × 9 в трехмерном пространстве с координатами x , y и z . Тогда каждая строка R x , столбец C y или номер # z представляет собой «срез» возможностей 9 × 9 × 1; каждый ящик B w представляет собой «трубку» возможностей 9x3x3; каждый набор ограничений строка-столбец R x C y , набор ограничений количества строк R x # z или набор ограничений количества столбцов C y # z представляет собой «полосу» 9x1x1; каждый набор ограничений количества ящиков B w # z представляет собой «квадрат» возможностей 3x3 × 1; и каждая возможность R x C y # z представляет собой «кубик» размером 1 x 1 x 1, состоящий из единственной возможности. Более того, каждый набор ограничений или возможность является пересечением наборов компонентов. Например, R1C2 # 3 = R1 ∩ C2 ∩ # 3, где ∩ обозначает пересечение множеств.
Хотя другие варианты судоку имеют разное количество строк, столбцов, чисел и / или разные виды ограничений, все они включают в себя возможности и наборы ограничений и, таким образом, могут рассматриваться как проблемы с точным совпадением набора.
Задача N ферзей
Проблема N ферзей является примером обобщенной проблемы точного покрытия. [3] Проблема включает четыре вида ограничений:
- Ранг: для каждого из N рангов должна быть ровно одна королева.
- Файл: для каждого из N файлов должна быть ровно одна королева.
- Диагонали: Для каждой из 2 N - 1 диагоналей должно быть не более одного ферзя.
- Обратные диагонали: на каждой из 2 N - 1 обратных диагоналей должно быть не более одного ферзя.
Обратите внимание, что 2 N ограничения рангового файла и файла образуют первичные ограничения, в то время как диагональные и обратные диагонали 4 N - 2 образуют вторичные ограничения. Кроме того, поскольку каждая из первой и последней диагональных и обратных диагоналей включает только один квадрат на шахматной доске, их можно опустить, и, таким образом, можно уменьшить количество вторичных ограничений до 4 N - 6. Тогда матрица для задачи N ферзей будет иметь N 2 строки и 6 N - 6 столбцов, каждая строка для возможного размещения ферзя на каждом квадрате на шахматной доске и каждый столбец для каждого ограничения.
Смотрите также
- Проблема удовлетворения ограничений
- Танцы Links
- Алгоритм карты различий
- Набор ударов
- 21 NP-полная задача Карпа
- Алгоритм Кнута X
- Список NP-полных задач
- Идеальное совпадение и трехмерное совпадение являются частными случаями задачи точного покрытия.
Рекомендации
- ^ MR Garey ; Д.С. Джонсон (1979). Компьютеры и непоколебимость: руководство по теории NP-полноты . Нью-Йорк: WH Freeman. ISBN 0-7167-1045-5.Эта классическая книга развивает теорию, а затем каталогизирует многие NP-Complete задачи.
- ^ Ричард М. Карп (1972). « Сводимость комбинаторных задач ». В RE Miller; Дж. У. Тэтчер (ред.). Сложность компьютерных вычислений . Proc. Symp. по сложности компьютерных вычислений. Нью-Йорк: Пленум. С. 85–103. ISBN 0-3063-0707-3.
- ^ а б в г д Кнут, Дональд (2000). «Танцующие звенья». arXiv : cs / 0011047 .
- ^ Дональд Кнут в своей статье «Танцующие связи» приводит этот пример в виде уравнения (3) только с переупорядоченными строками.
- ^ Дональд Кнут объясняет это простое обобщение в своей статье «Танцующие связи», в частности, в объяснениизадачтетрастика и N ферзей .
- ^ Голомб, Соломон В. (1994). Полимино: головоломки, узоры, задачи и упаковки (2-е изд.). Принстон, Нью-Джерси: Издательство Принстонского университета. п. 7 . ISBN 0-691-02444-8.
- ^ Хэнсон, Роберт М. "Проблема точного покрытия" . www.stolaf.edu . Колледж Святого Олафа . Проверено 20 августа 2020 .
Внешние ссылки
- Реализация решателя Exact Cover в C в свободном программном обеспечении - использует алгоритм X и Dancing Links. Включает примеры судоку и головоломок с логической сеткой.
- Решатель Exact Cover в Golang - использует алгоритм X и Dancing Links. Включает примеры судоку и n-queens.
- Точная обложка - Справочный проект по математике