Точное покрытие - Exact cover

В математика, учитывая коллекцию S из подмножества набора Икс, точное покрытие это подколлекция S^* из S так что каждый элемент в Икс содержится в ровно один подмножество в S^*.One говорит, что каждый элемент в Икс покрывается ровно одно подмножество в S^*.Точная обложка - это своего рода обложка.

В Информатика, то проблема с точным покрытием это проблема решения чтобы определить, существует ли точное покрытие. НП-полный^[1]и является одним из 21 NP-полная задача Карпа.^[2]Проблема с точным покрытием - это своего рода проблема удовлетворения ограничений.

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

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

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

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

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

Учитывая коллекцию S из подмножества набора Икс, точное покрытие Икс это подколлекция S^* из S который удовлетворяет двум условиям:

• В пересечение любых двух различных подмножеств в S^* является пустой, т.е. подмножества в S^* находятся попарно непересекающиеся. Другими словами, каждый элемент в Икс содержится в максимум один подмножество в S^*.
• В союз подмножеств в S^* является Икс, т.е. подмножества в S^* обложка Икс. Другими словами, каждый элемент в Икс содержится в хотя бы один подмножество в S^*.

Короче говоря, точное покрытие является «точным» в том смысле, что каждый элемент в Икс содержится в ровно один подмножество в S^*.

Эквивалентно точное покрытие Икс это подколлекция S^* из S это перегородки Икс.

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

• Объединение подмножеств в S является Икс. Другими словами, каждый элемент в Икс содержится хотя бы в одном подмножестве в S.

Если пустой набор ∅ содержится в S, то не имеет значения, находится ли он в какой-либо конкретной обложке. Поэтому типично предположить, что:

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

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

Позволять S = {N, О, п, E} быть набором подмножеств множества Икс = {1, 2, 3, 4} такое, что:

• N = { },
• О = {1, 3},
• п = {2, 3} и
• E = {2, 4}.

Подколлекция {О, E} - точное покрытие Икс, поскольку подмножества О = {1, 3} и E = {2, 4} не пересекаются и их объединение Икс = {1, 2, 3, 4}.

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

Подколлекция {E, п} не является точной обложкой ИксПересечение подмножеств E и п, {2}, не пусто: подмножества E и п не являются непересекающимися. Более того, объединение подмножеств E и п, {2, 3, 4}, не является Икс = {1, 2, 3, 4}: Ни то, ни другое E ни п покрывает элемент 1.

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

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

Позволять S = {А, B, C, D, E, F} быть набором подмножеств набора Икс = {1, 2, 3, 4, 5, 6, 7} такое, что:

• А = {1, 4, 7};
• B = {1, 4};
• C = {4, 5, 7};
• D = {3, 5, 6};
• E = {2, 3, 6, 7}; и
• F = {2, 7}.

Тогда подколлекция S^* = {B, D, F} является точным покрытием, поскольку каждый элемент в Икс содержится ровно в одном из подмножеств:

• B = {1, 4};
• D = {3, 5, 6}; или
• F = {2, 7}.

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

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

Проблема точного покрытия определяется бинарное отношение "содержит" между подмножествами в S и элементы в Икс.Существуют различные эквивалентные способы представления этого отношения.

Стандартное представление

Стандартный способ представить отношение «содержит» - перечислить элементы в каждом подмножестве.

Например, подробный пример выше использует это стандартное представление:

• А = {1, 4, 7};
• B = {1, 4};
• C = {4, 5, 7};
• D = {3, 5, 6};
• E = {2, 3, 6, 7}; и
• F = {2, 7}.

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

Обратное представление

Отношение "содержит" между подмножествами и элементами может быть преобразованный, перечисляя подмножества, в которых содержится каждый элемент.

Например, отношение "содержит" в подробный пример выше может быть представлено перечислением подмножеств, в которых содержится каждый элемент:

• 1 является элементом А, B;
• 2 является элементом E, F;
• 3 является элементом D, E;
• 4 является элементом А, B, C;
• 5 является элементом C, D;
• 6 является элементом D, E; и
• 7 является элементом А, C, E, F.

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

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

Представления матриц и гиперграфов

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

Матрица включает по одной строке для каждого подмножества в S и по одному столбцу для каждого элемента в ИксЗапись в конкретной строке и столбце равна 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 для матричного решения подробный пример над.

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

Графическое представление

Отношение «содержит» можно представить как двудольный граф.

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

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

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

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

Эквивалентные проблемы

Хотя каноническая проблема точного покрытия предполагает сбор S подмножеств набора Икс, логика не зависит от наличия подмножеств, содержащих элементы. "Абстрактная проблема точного покрытия" возникает всякий раз, когда существует гетерогенное отношение между двумя наборами п и Q и цель - выбрать подмножество П* из п так что каждый элемент в Q относится к ровно один элемент в П*.В общем, элементы п представляют собой выбор и элементы Q представляют собой «ровно одно» ограничение на этот выбор.

Более формально, учитывая бинарное отношение р ⊆ п × Q между сетами п и Q, можно назвать подмножество П* из п "абстрактное точное покрытие" Q если каждый элемент в Q является р^Т-относится только к одному элементу в П*. Вот р^Т это разговаривать из р.

В общем, р^Т ограниченный к Q × П* это функция от Q к П*, который отображает каждый элемент в Q к уникальному элементу в П* это р-относится к этому элементу в Q.Эта функция на, если только П* содержит «пустой набор», т.е. элемент, который не р-относится к любому элементу в Q.

В канонической задаче о точном покрытии п это коллекция S подмножеств Икс, Q это набор Икс, р является ли бинарное отношение "содержит" между подмножествами и элементами, и р^Т ограниченный Q × П* функция "содержится в" от элементов до выбранных подмножеств.

Набор точных ударов

В математика, учитывая коллекцию S подмножеств набора Икс, набор точных ударов ИКС* это подмножество Икс так что каждое подмножество в S содержит ровно один элемент в ИКС*. Один говорит, что каждое подмножество в S поражен ровно один элемент в ИКС*.

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

Проблема точного набора совпадений - это абстрактная проблема точного покрытия. обозначение выше, п это набор Икс, Q это коллекция S подмножеств Икс, р является бинарным отношением "содержится в" между элементами и подмножествами, и р⁻¹ ограниченный Q × П* функция "содержит" от подмножеств до выбранных элементов.

В то время как проблема точного покрытия включает в себя выбор подмножеств, а отношение «содержит» от подмножеств к элементам, проблема точного попадания в множество включает выбор элементов, а отношение «содержится в» от элементов к подмножествам. В некотором смысле проблема точного совпадения множества заключается в обратная задача точного покрытия, включающая тот же набор и набор подмножеств.

Пример набора точных ударов

Как в подробный точный пример обложки выше, пусть S = {А, B, C, D, E, F} набор подмножеств множества Икс = {1, 2, 3, 4, 5, 6, 7} такое, что:

• А = {1, 4, 7};
• B = {1, 4};
• C = {4, 5, 7};
• D = {3, 5, 6};
• E = {2, 3, 6, 7}; и
• F = {2, 7}.

потом ИКС* = {1, 2, 5} - точное совпадение, поскольку каждое подмножество в S содержит ровно один элемент в ИКС*, как видно из выделения.

Более того, {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 - единственный оставшийся элемент, который попадает в А, точный набор совпадений должен содержать 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 в задаче о точном покрытии, подмножества я и IV содержать элемент б в задаче двойного точного попадания.

В частности, пусть S = {я, II, III, IV, V, VI, VII} набор подмножеств множества Икс = {а, б, c, d, е, ж} такой, что:

• я = {а, б}
• II = {е, ж}
• III = {d, е}
• IV = {а, б, c}
• V = {c, d}
• VI = {d, е}
• VII = {а, c, е, ж}

потом ИКС* = {б, d, ж} является точным набором совпадений, поскольку каждое подмножество в S содержит (попадает) ровно один элемент в ИКС*, как видно по выделению.

Точный набор ударов ИКС* = {б, d, ж} здесь по сути то же самое, что и точное покрытие 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 - это рекурсивный, недетерминированный, в глубину, возврат алгоритм.

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

Обобщения

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

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

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

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

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

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

Пентамино черепица

Основная статья: Пентамино

Задача выложить доску размером 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 пентамино существует ограничение, заключающееся в том, что оно должно быть размещено ровно один раз. Назовите эти ограничения в честь соответствующих пентамино: F I L P N T U V W X Y Z.^[6]

Квадрат: Для каждого из 60 квадратов существует ограничение: он должен быть покрыт пентамино ровно один раз. Назовите эти ограничения после соответствующих квадратов на доске: ij, где я это звание и 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 столбца соответствуют ограничениям. Каждая строка содержит одну единицу в столбце, идентифицирующем пентомино, и пять единиц в столбцы, обозначающие квадраты, покрытые пентамино.

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

Судоку

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

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

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

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

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

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

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

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

Решение судоку - это точная проблема прикрытия.

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

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

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

Ограничения строки-столбца R1 C1 R1 C2 … 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 … … … … …

Ограничения количества строк R1 #1 R1 #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 … … … … …

Ограничения количества столбцов C1 #1 C1 #2 … R1C1 # 1 1 0 … R1C1 # 2 0 1 … … … … … R2C1 # 1 1 0 … R2C1 # 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 … … … … …

Ограничения количества ящиков B1 #1 B1 #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 … … … … … R2C1 # 1 1 0 … R2C1 # 2 0 1 … … … … … R2C2 # 1 1 0 … R2C2 # 2 0 1 … … … … … R2C3 # 1 1 0 … R2C3 # 2 0 1 … … … … … R3C1 # 1 1 0 … R3C1 # 2 0 1 … … … … … R3C2 # 1 1 0 … R3C2 # 2 0 1 … … … … … R3C3 # 1 1 0 … R3C3 # 2 0 1 … … … … …

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

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

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

N проблема королев

Основная статья: Проблема N ферзей

В N проблема королев является примером обобщенной задачи о точном покрытии.^[3] Проблема включает в себя четыре вида ограничений:

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

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

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

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

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

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

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

использованная литература

1. М. Р. Гарей; Д.С. Джонсон (1979). Компьютеры и непреодолимость: руководство по теории NP-полноты. Нью-Йорк: W.H. Фримен. ISBN  0-7167-1045-5. Это классическая книга, развивающая теорию, затем каталогизирующая много НП-Полные задачи.
2. Ричард М. Карп (1972). "Сводимость комбинаторных задач ". В Р. Э. Миллер; Дж. В. Тэтчер (ред.). Сложность компьютерных вычислений. Proc. Symp. по сложности компьютерных вычислений. Нью-Йорк: Пленум. С. 85–103. ISBN  0-3063-0707-3.
3. Кнут, Дональд (2000). «Танцующие звенья». arXiv:cs / 0011047.
4. Дональд Кнут в своей статье «Танцующие связи» этот пример приводится в виде уравнения (3) только с переупорядоченными строками.
5. Дональд Кнут объясняет это простое обобщение в своей статье «Танцующие связи», в частности, объясняя тетрастик и N ферзей проблемы.
6. Голомб, Соломон В. (1994). Полимино: головоломки, выкройки, задачи и упаковки (2-е изд.). Принстон, Нью-Джерси: Издательство Принстонского университета. п.7. ISBN  0-691-02444-8.
7. Хэнсон, Роберт М. "Проблема с точным покрытием". www.stolaf.edu. Колледж Святого Олафа. Получено 20 августа 2020.

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

• Бесплатная программная реализация решателя Exact Cover на C - использует алгоритм X и танцующие ссылки. Включает примеры судоку и головоломок с логической сеткой.
• Решатель Exact Cover в Golang - использует алгоритм X и танцующие ссылки. Включает примеры судоку и n-королев.
• Точное покрытие - Справочный проект по математике