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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные примеры

Позволять ${\mathcal {S}}=\{N,O,P,E\}$ быть совокупностью подмножеств множества $X=\{1,2,3,4\}$ такой, что:

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

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

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

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

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

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

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

Пусть 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}; и
$F$ = { 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$ имеет общие с $D$ элементы 3 и 6 . Тогда $F$ — единственное оставшееся подмножество, а поднабор { $B$ , $D$ , $F$ } действительно является точным покрытием. См. пример в статье «Алгоритм Кнута X» , где представлена матричная версия этого аргумента.

Представительства

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

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

В общем, $Р$ ^Т ограничено $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$ знак равно { $d$ , $е$ }
$IV$ знак равно { $а$ , б , $с$ }
$V$ знак равно { $c$ , $d$ }
$VI$ знак равно { $d$ , $е$ }
$VII$ знак равно { $а$ , $c$ , $е$ , $ж$ }

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

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

$а$ € $I$ , $IV$ , $VII$ ;
$б$ € $I$ , $IV$ ;
$c$ ∈ $IV$ , $V$ , $VII$ ;
$d$ ∈ $III$ , $V$ , $VI$ ;
$е$ ∈ $II$ , $III$ , $VI$ , $VII$ ; и
$€$ ж $II$ , $VII$ .

Матрица заболеваемости

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

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

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

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

	1	2	3	4	5	6	7
$А$	1	0	0	1	0	0	1
$Б$	1	0	0	1	0	0	0
$С$	0	0	0	1	1	0	1
$Д$	0	0	1	0	1	1	0
$И$	0	1	1	0	0	1	1
$Ф$	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$ , соединена ровно с одной выбранной вершиной, как ясно видно из выделения.

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

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

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

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

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

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

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

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

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

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

Плитка пентамино

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

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

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. ^[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}
{V, 68, 78, 86, 87, 88}
{И, 74, 82, 83, 84, 85}

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

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

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

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

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

Судоку

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

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

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

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

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

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

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

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

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

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

В стандартном варианте судоку 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, общий характер матрицы можно увидеть из нескольких снимков:

**Ограничения строк и столбцов**
	Р1 С1	Р1 С2	…
R1C1#1	1	0	⋯
R1C1#2	1	0	⋯
R1C1#3	1	0	⋯
R1C1#4	1	0	⋯
R1C1#5	1	0	⋯
R1C1#6	1	0	⋯
R1C1#7	1	0	⋯
R1C1#8	1	0	⋯
R1C1#9	1	0	⋯
R1C2#1	0	1	⋯
R1C2#2	0	1	⋯
R1C2#3	0	1	⋯
R1C2#4	0	1	⋯
R1C2#5	0	1	⋯
R1C2#6	0	1	⋯
R1C2#7	0	1	⋯
R1C2#8	0	1	⋯
R1C2#9	0	1	⋯
⋮	⋮	⋮	⋱

**Ограничения количества строк**
	Р1 #1	Р1 #2	…
R1C1#1	1	0	⋯
R1C1#2	0	1	⋯
⋮	⋮	⋮	⋱
R1C2#1	1	0	⋯
R1C2#2	0	1	⋯
⋮	⋮	⋮	⋱
R1C3#1	1	0	⋯
R1C3#2	0	1	⋯
⋮	⋮	⋮	⋱
R1C4#1	1	0	⋯
R1C4#2	0	1	⋯
⋮	⋮	⋮	⋱
R1C5#1	1	0	⋯
R1C5#2	0	1	⋯
⋮	⋮	⋮	⋱
R1C6#1	1	0	⋯
R1C6#2	0	1	⋯
⋮	⋮	⋮	⋱
R1C7#1	1	0	⋯
R1C7#2	0	1	⋯
⋮	⋮	⋮	⋱
R1C8#1	1	0	⋯
R1C8#2	0	1	⋯
⋮	⋮	⋮	⋱
R1C9#1	1	0	⋯
R1C9#2	0	1	⋯
⋮	⋮	⋮	⋱

**Ограничения количества столбцов**
	С1 #1	С1 #2	…
R1C1#1	1	0	⋯
R1C1#2	0	1	⋯
⋮	⋮	⋮	⋱
Р2С1#1	1	0	⋯
Р2С1#2	0	1	⋯
⋮	⋮	⋮	⋱
R3C1#1	1	0	⋯
R3C1#2	0	1	⋯
⋮	⋮	⋮	⋱
R4C1#1	1	0	⋯
R4C1#2	0	1	⋯
⋮	⋮	⋮	⋱
R5C1#1	1	0	⋯
R5C1#2	0	1	⋯
⋮	⋮	⋮	⋱
R6C1#1	1	0	⋯
R6C1#2	0	1	⋯
⋮	⋮	⋮	⋱
R7C1#1	1	0	⋯
R7C1#2	0	1	⋯
⋮	⋮	⋮	⋱
R8C1#1	1	0	⋯
R8C1#2	0	1	⋯
⋮	⋮	⋮	⋱
R9C1#1	1	0	⋯
R9C1#2	0	1	⋯
⋮	⋮	⋮	⋱

**Ограничения количества ящиков**
	Б1 #1	Б1 #2	⋯
R1C1#1	1	0	⋯
R1C1#2	0	1	⋯
⋮	⋮	⋮	⋱
R1C2#1	1	0	⋯
R1C2#2	0	1	⋯
⋮	⋮	⋮	⋱
R1C3#1	1	0	⋯
R1C3#2	0	1	⋯
⋮	⋮	⋮	⋱
Р2С1#1	1	0	⋯
Р2С1#2	0	1	⋯
⋮	⋮	⋮	⋱
Р2С2#1	1	0	⋯
Р2С2#2	0	1	⋯
⋮	⋮	⋮	⋱
Р2С3#1	1	0	⋯
Р2С3#2	0	1	⋯
⋮	⋮	⋮	⋱
R3C1#1	1	0	⋯
R3C1#2	0	1	⋯
⋮	⋮	⋮	⋱
R3C2#1	1	0	⋯
Р3С2#2	0	1	⋯
⋮	⋮	⋮	⋱
Р3С3#1	1	0	⋯
Р3С3#2	0	1	⋯
⋮	⋮	⋮	⋱

Полную матрицу размером 729×324 можно получить у Роберта Хэнсона. ^[8]

Обратите внимание, что набор возможностей 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 представляет собой «полосу» возможностей размером 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]

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

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

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

Ранг: Для каждого из 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-полных задач
Раздел набора
Совершенное паросочетание и трехмерное паросочетание являются частными случаями задачи точного покрытия.

Ссылки

^ Решение точных случаев укрытий с помощью сетевых биовычислений на основе молекулярных двигателейПрадхибха Сурендиран, Кристоф Роберт Мейнеке, Асим Сальхотра, Георг Хельдт, Цзинъюань Чжу, Альф Монссон, Стефан Диес, Дэнни Ройтер, Гиллель Куглер, Хайнер Линке и Тилль Кортен2022 2 (5), 396-403DOI: 10.1021/acsnanoscienceau.2c00013.
^ Кортен, Тилль; Диц, Стефан; Линке, Хайнер; Николау, Дэн В.; Куглер, Гилель (1 августа 2021 г.). «Разработка сетевых биовычислительных схем для решения задачи точного покрытия» . Новый журнал физики . 23 (8): 085004. doi : 10.1088/1367-2630/ac175d . ISSN 1367-2630 .
^ Jump up to: ^а ^б г-н Гэри ; Д.С. Джонсон (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Нью-Йорк: WH Freeman. ISBN 0-7167-1045-5 . Эта книга представляет собой классику, в которой развивается теория, а затем каталогизируется множество NP-полных проблем.
^ Ричард М. Карп (1972). «Сводимость комбинаторных задач» (PDF) . В Р.Э. Миллере; Дж. Тэтчер (ред.). Сложность компьютерных вычислений . Учеб. Симп. о сложности компьютерных вычислений. Нью-Йорк: Пленум. стр. 85–103. ISBN 0-3063-0707-3 . Архивировано из оригинала (PDF) 29 июня 2011 г. Проверено 27 июня 2008 г.
^ Jump up to: ^а ^б ^с ^д ^и Кнут, Дональд (2000). «Танцевальные звенья». arXiv : cs/0011047 .
^ Дональд Кнут объясняет это простое обобщение в своей статье «Танцующие связи», в частности, объясняя проблемы тетрастика и 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 ферзей.
Точная обложка - Справочный проект по математике

[1] Решение точных случаев укрытий с помощью сетевых биовычислений на основе молекулярных двигателейПрадхибха Сурендиран, Кристоф Роберт Мейнеке, Асим Сальхотра, Георг Хельдт, Цзинъюань Чжу, Альф Монссон, Стефан Диес, Дэнни Ройтер, Гиллель Куглер, Хайнер Линке и Тилль Кортен2022 2 (5), 396-403DOI: 10.1021/acsnanoscienceau.2c00013.

[2] Кортен, Тилль; Диц, Стефан; Линке, Хайнер; Николау, Дэн В.; Куглер, Гилель (1 августа 2021 г.). «Разработка сетевых биовычислительных схем для решения задачи точного покрытия» . Новый журнал физики . 23 (8): 085004. doi : 10.1088/1367-2630/ac175d . ISSN 1367-2630 .

[:0-3] Jump up to: ^а ^б г-н Гэри ; Д.С. Джонсон (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Нью-Йорк: WH Freeman. ISBN 0-7167-1045-5 . Эта книга представляет собой классику, в которой развивается теория, а затем каталогизируется множество NP-полных проблем.

[4] Ричард М. Карп (1972). «Сводимость комбинаторных задач» (PDF) . В Р.Э. Миллере; Дж. Тэтчер (ред.). Сложность компьютерных вычислений . Учеб. Симп. о сложности компьютерных вычислений. Нью-Йорк: Пленум. стр. 85–103. ISBN 0-3063-0707-3 . Архивировано из оригинала (PDF) 29 июня 2011 г. Проверено 27 июня 2008 г.

[knuth-5] Jump up to: ^а ^б ^с ^д ^и Кнут, Дональд (2000). «Танцевальные звенья». arXiv : cs/0011047 .

[6] Дональд Кнут объясняет это простое обобщение в своей статье «Танцующие связи», в частности, объясняя проблемы тетрастика и N ферзей .

[7] Голомб, Соломон В. (1994). Полимино: головоломки, закономерности, проблемы и упаковки (2-е изд.). Принстон, Нью-Джерси: Издательство Принстонского университета. п. 7 . ISBN 0-691-02444-8 .

[8] Хэнсон, Роберт М. «Задача о точном покрытии» . www.stolaf.edu . Колледж Святого Олафа . Проверено 20 августа 2020 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]