Точное покрытие

Совокупность подмножеств, такая, что каждый элемент исходного множества содержится ровно в одном подмножестве

В математической области комбинаторики , если задана коллекция подмножеств множества , точное покрытие — это подколлекция из , такая, что каждый элемент из содержится ровно в одном подмножестве в . Говорят, что каждый элемент из покрыт ровно одним подмножеством в . ^[1] Точное покрытие — это вид покрытия . Оно является недетерминированным за полиномиальное время (NP) и имеет множество приложений, начиная от оптимизации расписаний рейсов авиакомпаний, облачных вычислений и проектирования электронных схем . ^[2] ${\displaystyle {\mathcal {S}}}$ ${\displaystyle X}$ ${\displaystyle {\mathcal {S}}^{*}}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle X}$ ${\displaystyle {\mathcal {S}}^{*}}$ ${\displaystyle X}$ ${\displaystyle {\mathcal {S}}^{*}}$

Другими словами, представляет собой раздел , состоящий из подмножеств, содержащихся в . ${\displaystyle {\mathcal {S}}^{*}}$ ${\displaystyle X}$ ${\displaystyle {\mathcal {S}}}$

Задача точного покрытия для нахождения точного покрытия является своего рода задачей удовлетворения ограничений . Элементы представляют выборы, а элементы представляют ограничения. ${\displaystyle {\mathcal {S}}}$ ${\displaystyle X}$

Задача точного покрытия включает отношение contains между подмножествами и элементами. Но задача точного покрытия может быть представлена ​​любым гетерогенным отношением между набором выборов и набором ограничений. Например, задача точного покрытия эквивалентна задаче точного попадания , матрице инцидентности или двудольному графу .

В информатике задача точного покрытия — это задача принятия решения , чтобы определить, существует ли точное покрытие. Задача точного покрытия является NP-полной ^[3] и является одной из 21 NP-полных задач Карпа . ^[4] Она является NP-полной, даже если каждое подмножество в S содержит ровно три элемента; эта ограниченная задача известна как точное покрытие 3-множествами , часто сокращенно X3C. ^[3]

Алгоритм X Кнута — это алгоритм , который находит все решения задачи точного покрытия. DLX — это название, данное алгоритму X, когда он эффективно реализован с использованием техники Dancing Links Дональда Кнута на компьютере. ^[5]

Проблему точного покрытия можно немного обобщить, включив в нее не только ограничения «точно один раз» , но и ограничения « не более одного раза» .

Нахождение мозаик пентамино и решение судоку являются примечательными примерами задач на точное покрытие. Задача о n ферзях является обобщенной задачей на точное покрытие.

Формальное определение

Если задана совокупность подмножеств множества , то точное покрытие — это подсовокупность , удовлетворяющая двум условиям: ${\displaystyle {\mathcal {S}}}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle {\mathcal {S}}^{*}}$ ${\displaystyle {\mathcal {S}}}$

• Пересечение любых двух различных подмножеств в пусто , т.е. подмножества в попарно не пересекаются . Другими словами, каждый элемент в содержится не более чем в одном подмножестве в . ${\displaystyle {\mathcal {S}}^{*}}$ ${\displaystyle {\mathcal {S}}^{*}}$ ${\displaystyle X}$ ${\displaystyle {\mathcal {S}}^{*}}$
• Объединение подмножеств в есть , т.е. подмножества в покрывают . Другими словами, каждый элемент в содержится по крайней мере в одном подмножестве в . ${\displaystyle {\mathcal {S}}^{*}}$ ${\displaystyle X}$ ${\displaystyle {\mathcal {S}}^{*}}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle {\mathcal {S}}^{*}}$

Короче говоря, точное покрытие является точным в том смысле, что каждый элемент в содержится ровно в одном подмножестве в . ${\displaystyle X}$ ${\displaystyle {\mathcal {S}}^{*}}$

Эквивалентно , точное покрытие является подколлекцией этого раздела . ${\displaystyle X}$ ${\displaystyle {\mathcal {S}}^{*}}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle X}$

Для существования точного покрытия необходимо, чтобы: ${\displaystyle X}$

• Объединение подмножеств в равно . Другими словами, каждый элемент в содержится по крайней мере в одном подмножестве в . ${\displaystyle {\mathcal {S}}}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle {\mathcal {S}}}$

Если пустое множество содержится в , то не имеет значения, находится ли оно в каком-либо точном покрытии. Таким образом, типично предполагать, что: ${\displaystyle \emptyset }$ ${\displaystyle {\mathcal {S}}}$

• Пустое множество не входит в . Другими словами, каждое подмножество в содержит хотя бы один элемент. ${\displaystyle {\mathcal {S}}^{*}}$ ${\displaystyle {\mathcal {S}}^{*}}$

Простые примеры

Пусть будет набором подмножеств множества, таким что: ${\displaystyle {\mathcal {S}}=\{N,O,P,E\}}$ ${\displaystyle X=\{1,2,3,4\}}$

• ${\displaystyle N=\{\}}$,
• ${\displaystyle O=\{1,3\}}$,
• ${\displaystyle P=\{1,2,3\}}$, и
• ${\displaystyle E=\{2,4\}}$.

Подмножество является точным покрытием , поскольку подмножества и не пересекаются, а их объединение равно . ${\displaystyle \{O,E\}}$ ${\displaystyle X}$ ${\displaystyle O=\{1,3\}}$ ${\displaystyle E=\{2,4\}}$ ${\displaystyle X=\{1,2,3,4\}}$

Подмножество также является точным покрытием . Включение пустого множества не имеет значения, поскольку оно не пересекается со всеми подмножествами и не изменяет объединение. ${\displaystyle \{N,O,E\}}$ ${\displaystyle X}$ ${\displaystyle N=\{\}}$

Подмножество не является точным покрытием . Несмотря на то, что объединение подмножеств и равно , пересечение подмножеств и , , не пусто. Следовательно, подмножества и не удовлетворяют требованию непересекаемости точного покрытия. ${\displaystyle \{E,P\}}$ ${\displaystyle X}$ ${\displaystyle E}$ ${\displaystyle P}$ ${\displaystyle \{1,2,3,4\}=X}$ ${\displaystyle E}$ ${\displaystyle P}$ ${\displaystyle \{2\}}$ ${\displaystyle E}$ ${\displaystyle P}$

Подколлекция также не является точным покрытием . Несмотря на то, что и не пересекаются, их объединение не является , поэтому они не удовлетворяют требованию покрытия . ${\displaystyle \{N,P\}}$ ${\displaystyle X}$ ${\displaystyle N}$ ${\displaystyle P}$ ${\displaystyle X}$

С другой стороны, не существует точного покрытия — на самом деле, даже покрытия — для , поскольку является собственным подмножеством : ни одно из подмножеств в не содержит элемент 5. ${\displaystyle Y=\{1,2,3,4,5\}}$ ${\displaystyle \bigcup {\mathcal {S}}=\{1,2,3,4\}}$ ${\displaystyle Y}$ ${\displaystyle {\mathcal {S}}}$

Подробный пример

Изображение подробного примера.

Пусть S = { A , B , C , D , E , F } — это набор подмножеств множества X = {1, 2, 3, 4, 5, 6, 7}, такой что:

• А = {1, 4, 7};
• В = { 1 , 4 };
• С = {4, 5, 7};
• Д = { 3 , 5 , 6 };
• Е = {2, 3, 6, 7}; и
• Ф = { 2 , 7 }.

Подмножество S ^* = { B , D , F } является точным покрытием, поскольку каждый элемент покрывается (содержится) ровно одним выбранным подмножеством, как видно из выделения.

Более того, { B , D , F } является единственным точным покрытием, как показывает следующий аргумент: Поскольку A и B являются единственными подмножествами, содержащими элемент 1, точное покрытие должно содержать A или B , но не оба. Если точное покрытие содержит A , то оно не содержит B , C , E или F , так как каждое из этих подмножеств имеет элемент 1, 4 или 7, общий с A. Тогда D является единственным оставшимся подмножеством, но подколлекция { A , D } не покрывает элемент 2. В заключение, нет точного покрытия, содержащего A. С другой стороны, если точное покрытие содержит B , то оно не содержит A или C , так как каждое из этих подмножеств имеет элемент 1 или 4, общий с B. Поскольку D является единственным оставшимся подмножеством, содержащим элемент 5, D должно быть частью точного покрытия. Если точное покрытие содержит D , то оно не содержит E , так как E имеет элементы 3 и 6 , общие с D . Тогда F — единственное оставшееся подмножество, и подколлекция { B , D , F } действительно является точным покрытием. См. пример в статье об алгоритме Кнута X для матричной версии этого аргумента.

Представления

Задача точного покрытия определяется неоднородным отношением contains между набором подмножеств S и набором элементов X. Но в подмножествах и элементах нет ничего фундаментального.

Представление задачи точного покрытия возникает всякий раз, когда существует неоднородное отношение R ⊆ S × X между множеством выборов S и множеством ограничений X , и цель состоит в том, чтобы выбрать подмножество S ^* из S таким образом, чтобы каждый элемент в X был связан R T ^ровно с одним элементом в S ^* . Здесь R ^T является обратным R.

В общем случае, R ^T, ограниченное X × S ^*, является функцией из X в S ^* , которая отображает каждый элемент в X в уникальный элемент в S ^* , который связан R -образом с этим элементом в X . Эта функция относится к , если только S ^* не содержит элемент (подобный пустому множеству), который не связан R -образом ни с одним элементом в X .

Представления задачи точного покрытия включают задачу точного попадания, матрицу инцидентности и двудольный граф.

Точный ударный набор

В математике , если задано множество S и совокупность X подмножеств S , точное попадание множества S ^* — это подмножество S , такое, что каждое подмножество в X содержит ровно один элемент из S ^* . Говорят, что каждое подмножество в X попадает ровно в один элемент из S ^* .

Задача о точном множестве попаданий представляет собой представление задачи о точном покрытии, включающей отношение содержится в , а не содержит .

Например, пусть S = { a , b , c , d , e , f } — множество, а X = { I , II , III , IV , V , VI , VII } — совокупность подмножеств S , таких что:

• Я = { а , б }
• II = { е , ф }
• III = { д , е }
• IV = { а , б , в }
• V = { c , d }
• VI = { d , e }
• VII = { а , в , д , е }

Тогда S ^* = { b , d , f } является точным попадающим множеством, поскольку каждое подмножество в X попадает (содержит) ровно один элемент в S ^* , как ясно из выделения.

Этот точный пример множества попаданий по сути такой же, как и подробный пример выше. Отображение отношения , содержащегося в (∈) от элементов к подмножествам, ясно показывает, что мы просто заменили буквенные подмножества элементами, а нумерованные элементы подмножествами:

• а ∈ I , IV , VII ;
• б ∈ I , IV ;
• в ∈ IV , V , VII ;
• г ∈ III , V , VI ;
• е ∈ II , III , VI , VII ; и
• f ∈ II , VII .

Матрица инцидентности

Отношение содержит может быть представлено матрицей инцидентности .

Матрица включает одну строку для каждого подмножества в S и один столбец для каждого элемента в X. Запись в конкретной строке и столбце равна 1, если соответствующее подмножество содержит соответствующий элемент, и равна 0 в противном случае.

В матричном представлении точное покрытие — это выбор строк, такой, что каждый столбец содержит 1 ровно в одной выбранной строке. Каждая строка представляет выбор, а каждый столбец — ограничение.

Например, отношение, содержащееся в подробном примере выше, может быть представлено матрицей инцидентности 6×7:

Опять же, подколлекция S ^* = { B , D , F } является точным покрытием, поскольку каждый столбец содержит 1 ровно в одной выбранной строке, как видно из выделения.

См. пример в статье об алгоритме Кнута X для решения на основе матрицы подробного примера выше.

Гиперграф

В свою очередь, матрицу инцидентности можно рассматривать также как описание гиперграфа . Гиперграф включает один узел для каждого элемента в X и одно ребро для каждого подмножества в S ; каждый узел включен ровно в одно из ребер, образующих покрытие.

Двудольный граф

Отношение contains может быть представлено двудольным графом .

Вершины графа делятся на два непересекающихся множества, одно из которых представляет подмножества в S , а другое — элементы в X. Если подмножество содержит элемент, ребро соединяет соответствующие вершины в графе.

В графовом представлении точное покрытие представляет собой выборку вершин, соответствующих подмножествам, такую, что каждая вершина, соответствующая элементу, соединена ровно с одной выбранной вершиной.

Например, отношение, содержащееся в подробном примере выше, может быть представлено двудольным графом с 6+7 = 13 вершинами:

Опять же, подмножество S ^* = { B , D , F } является точным покрытием, поскольку вершина, соответствующая каждому элементу в X , соединена ровно с одной выбранной вершиной, как видно из выделения.

Поиск решений

Алгоритм X — это название, которое Дональд Кнут дал «самому очевидному подходу проб и ошибок» для поиска всех решений задачи точного покрытия. ^[5] Технически, алгоритм X — это рекурсивный , недетерминированный , глубинный , возвратный алгоритм .

Когда алгоритм X эффективно реализуется с использованием техники Dancing Links Дональда Кнута на компьютере, Кнут называет его DLX. Он использует матричное представление задачи, реализованное как ряд дважды связанных списков единиц матрицы: каждый элемент 1 имеет ссылку на следующую 1 выше, ниже, слева и справа от себя. Поскольку задачи точного покрытия, как правило, разрежены, это представление обычно намного эффективнее как по размеру, так и по требуемому времени обработки. Затем DLX использует технику Dancing Links для быстрого выбора перестановок строк в качестве возможных решений и для эффективного отката (отмены) ошибочных догадок. ^[5]

Обобщенное точное покрытие

В стандартной задаче точного покрытия каждое ограничение должно быть удовлетворено ровно один раз. Это простое обобщение, чтобы немного ослабить это требование и допустить возможность того, что некоторые первичные ограничения должны быть удовлетворены ровно одним выбором, но другие вторичные ограничения могут быть удовлетворены максимум одним выбором.

Как объясняет Кнут, обобщенную задачу точного покрытия можно преобразовать в эквивалентную задачу точного покрытия, просто добавив одну строку для каждого вторичного столбца, содержащую одну 1 в этом столбце. ^[6] Если в конкретном решении-кандидате конкретный вторичный столбец удовлетворен, то добавленная строка не нужна. Но если вторичный столбец не удовлетворен, что допускается в обобщенной задаче, но не в стандартной задаче, то добавленная строка может быть выбрана, чтобы гарантировать, что столбец удовлетворен.

Однако Кнут продолжает объяснять, что лучше работать с обобщенной задачей напрямую, поскольку обобщенный алгоритм проще и быстрее: простое изменение его алгоритма X позволяет обрабатывать вторичные столбцы напрямую.

Задача об N ферзях является примером обобщенной задачи точного покрытия, поскольку ограничения, соответствующие диагоналям шахматной доски, имеют максимальное, а не точное количество ферзей.

Примечательные примеры

Благодаря своей NP-полноте любая задача из NP может быть сведена к задачам точного покрытия, которые затем могут быть решены с помощью таких методов, как Dancing Links. Однако для некоторых хорошо известных задач сведение является особенно прямым. Например, задача замощения доски пентамино и решение судоку могут рассматриваться как задачи точного покрытия.

Мозаика пентамино

Задача заполнения 60-клеточной доски 12 различными свободными пентамино является примером задачи точного покрытия, как объясняет Дональд Кнут в своей статье «Танец звеньев». ^[5]

Например, рассмотрим задачу замощения пентамино шахматной доски 8×8 с удаленными 4 центральными клетками:

Проблема включает в себя два вида ограничений:

Пентамино: Для каждого из 12 пентамино есть ограничение, что оно должно быть размещено ровно один раз. Назовите эти ограничения в честь соответствующих пентамино: FILPNTUVWXY Z. ^[7]

Квадрат: Для каждого из 60 квадратов есть ограничение, что он должен быть покрыт пентамино ровно один раз. Назовите эти ограничения по соответствующим квадратам на доске: ij , где i — ранг, а j — вертикаль.

Таким образом, всего имеется 12+60 = 72 ограничения.

Поскольку оба вида ограничений являются ограничениями «точно один раз» , задача представляет собой задачу точного покрытия.

Задача включает в себя множество вариантов, по одному для каждого способа размещения пентамино на доске. Удобно считать, что каждый вариант удовлетворяет набору из 6 ограничений: 1 ограничение для размещаемого пентамино и 5 ограничений для пяти квадратов, где он размещается.

В случае шахматной доски 8×8 с удаленными 4 центральными клетками существует 1568 таких вариантов, например:

• {Ж, 12, 13, 21, 22, 32}
• {Ж, 13, 14, 22, 23, 33}
• …
• {Я, 11, 12, 13, 14, 15}
• {Я, 12, 13, 14, 15, 16}
• …
• {Л, 11, 21, 31, 41, 42}
• {Л, 12, 22, 32, 42, 43}
• …

Одним из многих решений этой точной задачи о покрытии является следующий набор из 12 вариантов:

• {Я, 11, 12, 13, 14, 15}
• {Н, 16, 26, 27, 37, 47}
• {Л, 17, 18, 28, 38, 48}
• {У, 21, 22, 31, 41, 42}
• {Х, 23, 32, 33, 34, 43}
• {В, 24, 25, 35, 36, 46}
• {П, 51, 52, 53, 62, 63}
• {Ж, 56, 64, 65, 66, 75}
• {З, 57, 58, 67, 76, 77}
• {Т, 61, 71, 72, 73, 81}
• {В, 68, 78, 86, 87, 88}
• {Й, 74, 82, 83, 84, 85}

Этот набор вариантов соответствует следующему решению задачи о разбиении пентамино:

Задачу укладки пентамино более естественно рассматривать как задачу точного покрытия, чем задачу точного попадания в множество, поскольку более естественно рассматривать каждый выбор как набор ограничений, чем каждое ограничение как набор выборов.

Каждый выбор относится всего к 6 ограничениям, которые легко перечислить. С другой стороны, каждое ограничение относится ко многим выборам, которые сложнее перечислить.

Независимо от того, рассматривается ли это как задача точного покрытия или задача точного попадания, матричное представление одинаково, имея 1568 строк, соответствующих выборам, и 72 столбца, соответствующих ограничениям. Каждая строка содержит одну 1 в столбце, идентифицирующем пентамино, и пять 1 в столбцах, идентифицирующих квадраты, покрытые пентамино.

Используя матрицу, компьютер может относительно быстро найти все решения, например, с помощью Dancing Links .

Судоку

 Основные статьи: Судоку , Математика судоку , Алгоритмы решения судоку

Задача в судоку состоит в том, чтобы присвоить числа (или цифры, значения, символы) ячейкам (или квадратам) сетки таким образом, чтобы удовлетворять определенным ограничениям.

В стандартном варианте судоку 9×9 существует четыре вида ограничений:

Строка-Столбец: Каждое пересечение строки и столбца, т. е. каждая ячейка, должно содержать ровно одно число.

Номер строки: Каждая строка должна содержать каждое число ровно один раз.

Номер столбца: каждый столбец должен содержать каждое число ровно один раз.

Ящик-Номер: В каждом ящике каждое число должно встречаться ровно один раз.

Хотя первое ограничение может показаться тривиальным, оно, тем не менее, необходимо для того, чтобы гарантировать, что в ячейке находится только одно число. Естественно, размещение числа в ячейке запрещает размещение любого другого числа в занятой ячейке.

Решение судоку — это задача точного покрытия. Точнее, решение судоку — это задача точного попадания в множество , которая эквивалентна задаче точного покрытия, если рассматривать ее как задачу выбора возможностей таким образом, чтобы каждое ограничение содержало (т. е. попадало) ровно одну выбранную возможность.

Каждое возможное назначение определенного числа определенной ячейке является возможностью (или кандидатом). Когда судоку играют с карандашом и бумагой, возможности часто называют карандашными отметками.

В стандартном варианте судоку 9×9, в котором каждой из ячеек 9×9 присвоено одно из 9 чисел, существует 9×9×9=729 возможностей. Используя очевидную нотацию для строк, столбцов и чисел, возможности можно обозначить

Р1С1#1, Р1С1#2, …, Р9С9#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 }.

Column-Number: Набор ограничений column-number содержит все возможности для конкретного столбца и числа. Например, набор ограничений для столбца 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 }.

Box-Number: Набор ограничений box-number содержит все возможности для конкретного box и числа. Например, набор ограничений для box 1 (в верхнем левом углу) и числа 1, который может быть обозначен как B1#1, содержит 9 возможностей для ячеек в box 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 доступна у Роберта Хансона. ^[8]

Обратите внимание, что набор возможностей R x C y # z можно организовать в виде куба 9×9×9 в трехмерном пространстве с координатами x , y и z . Тогда каждая строка R x , столбец C y или число # z представляет собой "срез" возможностей 9×9×1; каждый ящик B w представляет собой "трубу" возможностей 9x3×3; каждый набор ограничений строка-столбец R x C y , набор ограничений строка-номер R x # z или набор ограничений столбец-номер C y # z представляет собой "полосу" возможностей 9x1×1; каждый набор ограничений ящик-номер B w # z представляет собой "квадрат" возможностей 3x3×1; и каждая возможность R x C y # z представляет собой "кубик" 1x1×1, состоящий из одной возможности. Более того, каждый набор ограничений или возможность представляет собой пересечение наборов компонентов. Например, R1C2#3 = R1 ∩ C2 ∩ #3, где ∩ обозначает пересечение множеств.

Хотя другие вариации судоку имеют разное количество строк, столбцов, чисел и/или различные виды ограничений, все они включают в себя наборы возможностей и ограничений и, таким образом, могут рассматриваться как задачи на точное попадание в заданное множество.

Проблема N ферзей

Задача N ферзей — это задача размещения n шахматных ферзей на шахматной доске n×n таким образом, чтобы никакие два ферзя не угрожали друг другу. Решение требует, чтобы никакие два ферзя не делили одну и ту же строку, столбец или диагональ. Это пример обобщенной задачи точного покрытия. ^[5]

Единственное симметричное решение головоломки восьми ферзей ( с точностью до поворота и отражения )

Проблема включает четыре вида ограничений:

Ранг: Для каждого из N рангов должна быть ровно одна королева.

Файл: В каждом из N файлов должен быть ровно один ферзь.

Диагонали: На каждой из 2 N  − 1 диагоналей должно быть не более одного ферзя.

Обратные диагонали: Для каждой из 2 N  − 1 обратных диагоналей должно быть не более одного ферзя.

Обратите внимание, что 2 N рядов и вертикалей образуют первичные ограничения, в то время как 4 N  − 2 диагонали и обратные диагонали образуют вторичные ограничения. Кроме того, поскольку каждая из первой и последней диагоналей и обратных диагоналей включает только одну клетку на шахматной доске, их можно опустить и, таким образом, можно сократить количество вторичных ограничений до 4 N  − 6. Матрица для задачи N ферзей тогда имеет N ² строк и 6 N  − 6 столбцов, каждая строка для возможного размещения ферзя на каждой клетке на шахматной доске, и каждый столбец для каждого ограничения.

Смотрите также

• Проблема удовлетворения ограничений
• Танцевальные ссылки
• Алгоритм карты различий
• 21 NP-полная задача Карпа
• Алгоритм Кнута X
• Список NP-полных задач
• Разделение множества
• Идеальное совпадение и трехмерное совпадение являются частными случаями задачи о точном покрытии.

Ссылки

1. Решение точных случаев укрытий с помощью сетевых биовычислений с молекулярно-моторным приводом Прадхибха Сурендиран, Кристоф Роберт Мейнеке, Асим Сальхотра, Георг Хельдт, Цзинъюань Чжу, Альф Монссон, Стефан Диес, Дэнни Рейтер, Гиллель Куглер, Хайнер Линке и Тилль Кортен 2022 2 (5), 396-403 DOI: 10.1021/acsnanoscienceau.2c00013
2. Кортен, Тилль; Диц, Стефан; Линке, Хайнер; Николау, Дэн В.; Куглер, Гилель (1 августа 2021 г.). «Разработка сетевых биовычислительных схем для решения задачи точного покрытия». Новый журнал физики . 23 (8): 085004. Бибкод : 2021NJPh...23h5004K. дои : 10.1088/1367-2630/ac175d . ISSN  1367-2630.
3. MR Garey ; DS Johnson (1979). Компьютеры и неразрешимость: Руководство по теории NP-полноты . Нью-Йорк: WH Freeman. ISBN 0-7167-1045-5. Эта книга является классикой, развивающей теорию, а затем каталогизирующей многие NP-полные задачи.
4. Ричард М. Карп (1972). "Сводимость среди комбинаторных задач" (PDF) . В RE Miller; JW Thatcher (ред.). Сложность компьютерных вычислений . Proc. of a Symp. on the Complexity of Computer Computations. New York: Plenum. стр. 85–103. ISBN 0-3063-0707-3. Архивировано из оригинала (PDF) 2011-06-29 . Получено 2008-06-27 .
5. Кнут, Дональд (2000). "Танцующие ссылки". arXiv : cs/0011047 .
6. Дональд Кнут объясняет это простое обобщение в своей статье «Танцующие звенья», в частности, при объяснении задач о тетрастике и N ферзях .
7. Голомб, Соломон В. (1994). Полимино: головоломки, узоры, проблемы и упаковки (2-е изд.). Принстон, Нью-Джерси: Princeton University Press. стр. 7. ISBN 0-691-02444-8.
8. Хансон, Роберт М. «Проблема точного покрытия». www.stolaf.edu . Колледж Св. Олафа . Получено 20 августа 2020 г. .

Внешние ссылки

• Бесплатная программная реализация решателя Exact Cover на языке C — использует Algorithm X и Dancing Links. Включает примеры для судоку и логических головоломок.
• Exact Cover Solver в Golang - использует Algorithm X и Dancing Links. Включает примеры для судоку и N ферзей.
• Точное покрытие - Справочный проект по математике