정확한 표지

수학에서, 집합 X의 부분 집합 $S{\displaystyle }$ ${\displaystyle S}$을(를) 집합 X의 부분 집합 S {\$displaystyle$ $S$$}$의 하위 $집합{\displaystyle {}^{}}$ S ${\displaystyle {\ast }^{}}$${\displaystyle$ $S^{*}}}}$에 있는 각 $요소$가 S$\$ {\$displaystyle$ S$^{*}$의 정확히 하나의 부분 집합에 포함되도록$$$$ 정확한 표지가 각 원소라고 되어 있다$.$${\displaystyle X}$ ${\displaystyle X}$은(는) $S{\displaystyle {}^{}}$ ${\displaystyle {\ast }^{}}$ ${\$ S$^{*}$에 있는 하나의 부분집합에 의해 정확히 가려진다$.$ 정확한 덮개는 일종의 덮개다.

컴퓨터 과학에서, 정확한 표지 문제는 정확한 표지가 존재하는지 여부를 결정하기 위한 결정 문제다.정확한 표지 문제는 NP-완전이며^[1] Karp의 21개 NP-완전성 문제 중 하나이다.^[2]정확한 표지 문제는 일종의 제약 만족도 문제다.

정확한 표지 문제는 발생 행렬이나 초당적 그래프로 나타낼 수 있다.

크누스의 알고리즘 X는 정확한 커버 문제에 대한 모든 해결책을 찾는 알고리즘이다.DLX는 컴퓨터에서 도널드 크누스의 춤추는 링크 기법을 사용하여 효율적으로 구현될 때$$ $알고리즘{\displaystyle }$ X ${\displaystyle$ X$}$에 붙여진 이름이다.^[3]

표준 정확한 커버 문제는 "정확히 하나의" 제약조건뿐만 아니라 "최대한 하나의" 제약조건을 포함하도록 약간 일반화될 수 있다.

펜토미노 기울기 발견과 스도쿠 해결은 정확한 커버 문제의 주목할 만한 예다.퀸즈 문제는 약간 일반화된 정확한 커버 문제다.

형식 정의

집합 $X{\displaystyle }$ ${\displaystyle X}$의 부분$$ 집합 $S{\displaystyle }$ ${\displaystyle S}$을(를) 수집할 경우$,$ $X{\displaystyle }$ ${\displaystyle X}$의 정확한 표지는 다음 두 가지 조건을 만족하는$$ $S{\displaystyle }$ ${\displaystyle S}$의 하위 집합 $S{\displaystyle {}^{}}$∗ ${\$이다.

• $∗{\$의 두 개별 하위 집합의 교차점은 비어 있다$$. 즉, $S{\displaystyle {}^{}}$ ${\displaystyle {\ast }^{}}$ ${\$ S$^{*}$의 하위 집합은 쌍으로 분리된다.즉, $X{\displaystyle }$ ${\displaystyle X}$의 각 요소는 $S{\displaystyle {}^{}}$ ${\displaystyle {\ast }^{}}$ ${\$ S$^{*}$의 최대 하나의 하위 집합에 포함되어 있다$$$.$
• The union of the subsets in ${\displaystyle S^{*}}$ is ${\displaystyle X}$, i.e., the subsets in ${\displaystyle S^{*}}$ cover ${\displaystyle X}$. In other words, each element in ${\displaystyle X}$ is contained in at least one subset in ${\displaystyle S^{*}}$.

요컨대, $X{\displaystyle }$ ${\displaystyle X}$의 각 원소가 $S{\displaystyle {}^{}}$ ${\displaystyle {\ast }^{}}$ ${\$ S$^{*}$의 정확히 하나의 서브셋에 포함되어 있다는$$ 점에서 정확한 커버는 "정확한" 것이다$.$

마찬가지로 $X{\displaystyle }$ ${\displaystyle X}$의 정확한 표지는 $X$ ${\displaystyle X}$을(를) 분할하는$$ $S{\displaystyle }$ ${\displaystyle S}$의 $하위{\displaystyle {}^{}}$ 집합이다$.$

$X{\displaystyle }$ ${\displaystyle X}$의 정확한 커버가 존재하려면$$ 다음을 수행해야 한다.

• $S{\displaystyle }$ ${\displaystyle S}$에서 하위 집합의 조합은 $X{\displaystyle }$ ${\displaystyle X}$이다$.$ 즉, $X{\displaystyle }$ ${\displaystyle X}$의 각 요소는 S ${\displaystyle S}$의 적어도 하나의 하위 집합에 포함된다$.$

빈 세트 ∅이 $S{\displaystyle }$ ${\displaystyle S$에 포함되어 있으면 정확한 커버에 있는지 여부에 따라 차이가 없다.따라서 다음과 같이 가정하는 것이 일반적이다.

• 빈 세트는 $S{\displaystyle {}^{}}$ ${\displaystyle {\ast }^{}}$ ${\$에 있지 않다$.$ 즉, $S{\displaystyle {}^{}}$ ${\displaystyle {\ast }^{}}$ ${\$의 각 부분집합에는 적어도 하나의 요소가 포함되어$$ 있다.

기본 예시

Let S = {N, O, P, E}은(는) 다음과 같은 집합 X = {1, 2, 3, 4}의 하위 집합 모음입니다.

• N = { },
• O = {1, 3}
• P = {2, 3} 및
• E = {2, 4}.

하위 집합 O = {1, 3} 및 E = {2,4}이(가) 분리되고 조합이 X = {1, 2, 3, 4}이므로 하위 집합 {O, E}은 X의 정확한 표지다.

하위 집합 {N, O, E}도 X의 정확한 표지다.빈 집합 N = { }을(를) 포함해도 모든 하위 집합과 분리되며 유니언을 변경하지 않으므로 아무런 차이가 없다.

하위 집합 {E, P}은(는) X의 정확한 표지가 아니다.하위 집합 E와 P, {2}의 교차점이 비어 있지 않음:Subset E와 P는 분리되지 않았다.더욱이, 하위 집합 E와 P의 조합, {2, 3, 4}은 X = {1, 2, 3, 4}이 아니다: E와 P는 모두 원소 1을 포함하지 않는다.

${\displaystyle 한편\mathcal{}}$, $\bigcup {\displaystyle }$ S${\displaystyle }$=${\displaystyle }${${\displaystyle 1}$,${\displaystyle 2}$,${\displaystyle }$3, ${\displaystyle 4\}}$ ${\displaystyle \bigcup{\mathcal{S}=\{1,2,3,4\}}$의 적절한 부분집합이기 때문에, Y = {1,2,3,4\}의 정확한 커버(사실상 커버조차도 포함하지 않는다)는 없다: S의 하위집합에는 5가 포함되어 있지 않다.

상세 예시

Let S = {A, B, C, D, E, F}은(는) 다음과 같은 집합 X = {1, 2, 3, 4, 5, 6, 7}의 하위 집합 모음입니다:

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

그러면 X의 각 원소가 정확히 하위 집합 중 하나에 포함되기 때문에 하위 집합 S^* = {B, D, F}이(가) 정확한 표지가 된다.

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

더구나 {B, D, F}은(는) 다음 주장이 증명하듯이 유일한 정확한 표지다.A와 B는 1을 포함하는 유일한 하위 집합이기 때문에 정확한 커버는 A나 B를 포함해야 하지만 둘 다 포함하지는 않는다.정확한 표지에 A가 포함되어 있으면, B, C, E 또는 F가 포함되어 있지 않다. 각 하위 집합은 A와 공통되는 요소를 가지고 있기 때문이다.그러면 D만이 남은 부분 집합이지만 {A, D} 집합은 요소 2를 포함하지 않는다.결론적으로 A가 포함된 정확한 표지는 없다.반면에, 만약 정확한 표지에 B가 포함된다면, 그것은 A나 C를 포함하지 않는다. 왜냐하면 각각의 하위 집합은 B와 공통되는 요소를 가지고 있기 때문이다.D는 5를 포함하는 유일한 하위 집합이므로, D는 정확한 커버의 일부여야 한다.정확한 표지에 D가 포함되어 있으면 E는 D와 공통되는 요소를 가지고 있기 때문에 E가 포함되지 않는다.그렇다면 F만이 남아 있는 부분집합이며, {B, D, F} 집합은 실로 정확한 표지가 된다.이 인수의 매트릭스 기반 버전은 Knuth의 알고리즘 X에 대한 기사의 예를 참조하십시오.

표현

정확한 커버 문제는 S의 하위 집합과 X의 요소들 사이의 이진 관계 "포함"에 의해 정의된다.이 관계를 나타내는 다른 동등한 방법들이 있다.

표준 표현

관계 "포함"을 나타내는 표준 방법은 각 부분 집합의 요소를 나열하는 것이다.

예를 들어 위의 자세한 예는 다음과 같은 표준 표현을 사용한다.

• A = {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은 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
A	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

다시 말하지만, 각 원소는 정확히 하나의 선택된 부분 집합에 포함되기 때문에, 즉 각 열은 강조 표시가 명확해짐에 따라 정확히 선택된 하나의 행에 1을 포함하기 때문에 하위 집합^* S = {B, D, F}은 정확한 표지다.

위의 자세한 예에 대한 매트릭스 기반 솔루션은 Knuth의 알고리즘 X 기사의 예를 참조하십시오.

다시 말해, 발생 행렬은 하이퍼그래프를 설명하는 것으로도 볼 수 있다.하이퍼그래프는 X의 각 요소에 대해 하나의 노드를 포함하고 S의 각 부분 집합에 대해 하나의 에지를 포함한다. 각 노드는 커버를 형성하는 가장자리 중 정확히 하나의 에지에 포함된다.

그래프 표현

관계 "포함"은 초당적 그래프로 나타낼 수 있다.

그래프의 정점은 두 개의 분리 집합으로 나뉘는데 하나는 S의 하위 집합을 나타내고 다른 하나는 X의 요소를 나타낸다.부분 집합에 요소가 포함된 경우 가장자리는 그래프에서 해당 정점을 연결한다.

그래프 표현에서 정확한 표지는 요소에 해당하는 각 정점이 정확히 하나의 선택된 정점에 연결되도록 하위 집합에 해당하는 정점을 선택하는 것이다.

예를 들어, 위의 세부 예에서 "포함" 관계는 6+7 = 13 정점인 초당적 그래프로 나타낼 수 있다.

다시 말하지만, 각 원소가 정확히 하나의 선택된 부분집합에 포함되기 때문에, 즉 X의 각 원소에 해당하는 정점이 강조 표시가 명확해짐에 따라 정확히 하나의 선택된 정점에 연결되기 때문에, 하위^* 집합 S = {B, D, F}은 정확한 표지다.

등가문제

표준적인 정확한 커버 문제는 집합 X의 하위 집합의 집합 S를 포함하지만, 논리는 요소를 포함하는 하위 집합의 존재에 의존하지 않는다."추상적인 정확한 커버 문제"는 두 세트 P와 Q 사이에 이질적인 관계가 있을 때마다 발생하며 목표는 Q의 각 요소가 P*의 한 요소와 정확히 관련되도록 P의 부분 집합 P*를 선택하는 것이다.일반적으로 P의 요소는 선택을 나타내고 Q의 요소는 그러한 선택에 대한 "정확히 하나의" 제약조건을 나타낸다.

좀 더 공식적으로, 세트 P와 Q 사이의 2진수 관계 R p P × Q를 주어, Q의 각 원소가 P*의 정확히 하나의 원소와 R 관련된다면^T P의 서브셋 P*를 Q의 "추상적인 정확한 커버"라고 부를 수 있다.여기 R은^T R의 반대다.

일반적으로, Q × P*로 제한된^T R은 Q에서 P*까지의 함수로서, Q의 각 원소를 Q의 해당 원소와 R이 관련된 P*의 고유 원소에 매핑한다.이 기능은 P*가 "빈 세트"를 포함하지 않는 한, 즉 Q의 어떤 요소와도 R과 관련이 없는 요소를 포함하지 않는 한 위에 있다.

표준적인 정확한 커버 문제에서 P는 X의 서브셋 집합 S이고, Q는 X, R은 서브셋과 요소 사이의 이진 관계 "내용"이며, R은^T 요소에서 선택된 서브셋에 이르는 "내포함수"이다.

정확한 타격 세트

수학에서, 집합 X의 부분 집합의 집합 S에 주어진, 정확한 타격 집합 X*는 X의 부분 집합이다. 그래서 S의 각 부분 집합은 X*에서 정확히 하나의 요소를 포함한다.하나는 S의 각 부분 집합이 X*의 정확히 하나의 원소에 의해 타격된다고 말한다.

컴퓨터 과학에서 정확한 타격 세트 문제는 정확한 타격 세트를 찾거나 없는 것으로 판단하기 위한 결정 문제다.

정확한 타격 세트 문제는 추상적인 정확한 커버 문제다.위의 표기법에서 P는 X, Q는 X의 서브셋 집합의 집합체 S, R은 원소와 서브셋 사이의 "내포되어 있다"는 이항 관계, 그리고 Q × P*로 제한된 R은⁻¹ 서브셋에서 선택된 원소까지 "내포되어 있다"는 함수다.

정확한 커버 문제는 하위 세트를 선택하고 하위 세트와 요소 간의 "포함" 관계를 포함하지만, 정확한 타격 세트 문제는 요소와 요소 간의 "포함" 관계를 선택하는 것을 포함한다.어떤 의미에서, 정확한 타격 세트 문제는 동일한 서브셋 집합과 집합의 집합과 관련된 정확한 커버 문제의 역방향이다.

정확한 타격 세트 예

위의 정확한 표지 예에서와 같이, S = {A, B, C, D, E, F}을(를) 다음과 같이 집합 X = {1, 2, 3, 4, 5, 6, 7}의 하위 집합 집합 집합 집합으로 한다.

• A = {1, 4, 7};
• B = {1, 4};
• C = {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가 포함되면 두 타격 모두 C가 포함되기 때문에 4가 포함되지 않는다.1이 A를 치는 유일한 요소인 만큼 정확한 타격 세트에는 1이 들어가야 한다.그렇다면 더 이상 남아 있는 요소가 없고, {1, 2, 5}은 실로 정확한 타격 세트다.

이 예는 위의 상세한 표지 예시와 동일한 하위 집합의 컬렉션을 포함하지만 본질적으로 다른 문제다.어떤 의미에서 정확한 타격 세트 문제는 매트릭스 표현에 따라 다음과 같이 분명하게 나타나기 때문에 위와 같은 정확한 피복 문제의 역(또는 전치 또는 역치)이다.

	A	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, VI, VII, 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}과 본질적으로 동일하다.

	I	II	III	IV	V	VI	7세
a	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

솔루션 찾기

알고리즘 X는 도널드 크누스가 정확한 커버 문제에 대한 모든 해결책을 찾기 위해 "가장 명백한 시행착오적 접근법"으로 붙인 이름이다.^[3]기술적으로 알고리즘 X는 반복적이고 비결정론적이며 깊이 우선의 역추적 알고리즘이다.

컴퓨터에 도널드 크누스의 춤추는 링크 기법을 이용해 알고리즘 X를 효율적으로 구현하면 크누스는 이를 DLX라고 부른다.DLX는 문제의 매트릭스 표현을 사용하며, 매트릭스 1s의 일련의 이중 연계 목록으로 구현된다. 각 1개 요소는 위, 아래, 왼쪽, 그리고 그 자체의 오른쪽에 다음 1에 대한 링크를 가지고 있다.(기술적으로, 리스트는 순환적이기 때문에, 이것은 토러스(torus)를 형성한다.)정확한 표지 문제는 희박한 경향이 있기 때문에, 이 표현은 일반적으로 크기와 필요한 처리 시간 모두에서 훨씬 더 효율적이다.그런 다음 DLX는 Dancing Links 기술을 사용하여 가능한 해결책으로 행의 순열을 신속하게 선택하고 잘못된 추측을 효율적으로 역추적(undo)한다.^[3]

일반화

표준 정확한 커버 문제에서, 각 제약조건은 정확히 한 번 충족되어야 한다.이 요구사항을 약간 완화하는 것은 간단한 일반화로서, 어떤 "기본" 제약조건은 정확히 하나의 선택으로 충족되어야 하지만 다른 "보조" 제약조건은 최대 하나의 선택으로 충족될 수 있다.

Knuth의 설명대로, 일반화된 정확한 커버 문제는 단지 2차 컬럼에 1개씩을 포함하는 각 2차 컬럼에 대해 하나의 행을 추가하기만 하면 등가의 정확한 커버 문제로 변환될 수 있다.^[5]특정 후보 솔루션에서 특정 2차 열을 만족하면 추가된 행이 필요하지 않다.그러나 일반화 문제에서 허용되지만 표준 문제가 아닌 2차 열이 만족되지 않으면 추가된 행을 선택하여 열이 만족되는지 확인할 수 있다.

그러나 크누스는 일반화된 알고리즘이 더 간단하고 빠르기 때문에 일반화된 문제를 직접적으로 다루는 것이 더 낫다고 설명한다.그의 알고리즘 X에 대한 간단한 변경은 2차 열을 직접 처리할 수 있게 한다.

N 퀸즈 문제는 체스판의 대각선에 해당하는 제약조건이 정확한 퀸 카운트가 아닌 최대치를 가지기 때문에 일반화된 정확한 커버 문제의 예다.

주목할 만한 예

NP-완전성 때문에 NP의 어떤 문제도 정확한 커버 문제로 축소될 수 있으며, 그 다음 Dancing Links와 같은 기술로 해결할 수 있다.그러나 일부 잘 알려진 문제들에 대해서는 특히 직접적인 감소가 있다.예를 들어 판자를 펜토미노로 타일링하는 문제와 스도쿠를 푸는 문제는 둘 다 정확한 커버 문제로 볼 수 있다.

펜토미노 타일링

도날드 크누스가 논문 '댄싱 링크스'에서 설명한 것처럼 60제곱미터 크기의 판자를 12개의 서로 다른 프리 펜토미노와 타일링하는 문제는 정확한 커버 문제의 한 예다.^[3]

예를 들어, 4개의 중앙 사각형이 제거된 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개의 펜토미노 각각에 대해 정확히 한 번 배치해야 한다는 제약이 있다.이러한 제약조건의 이름을 해당 펜토미노(F I L P N T U V W X Y Z)의 뒤에 붙이십시오.^[6]

사각형: 60개의 각 사각형에 대해 정확히 한 번 펜토미노로 덮어야 한다는 제약이 있다.이 제약조건의 이름을 ij, 여기서 나는 순위고 j는 파일이다.

따라서 모두 12+60 = 72개의 제약조건이 있다.

두 종류의 제약조건은 모두 "정확히 하나의" 제약조건이기 때문에, 문제는 정확한 커버 문제인 것이다.

문제는 펜토미노를 칠판에 붙이는 각 방법마다 하나씩, 많은 선택들을 포함한다.각각의 선택은 6개의 제약조건, 즉 펜토미노가 배치되는 것에 대한 1개의 제약조건과 그것이 배치되는 5개의 제곱에 대한 5개의 제약조건을 만족시키는 것으로 간주하는 것이 편리하다.

4개의 중앙 사각형이 제거된 8×8 체스 보드의 경우, 예를 들어 1568개의 그러한 선택이 있다.

• {F, 12, 13, 21, 22, 32}
• {F, 13, 14, 22, 23, 33}
• …
• {나, 11, 12, 13, 14, 15}
• {나, 12, 13, 14, 15, 16}
• …
• {L, 11, 21, 31, 41, 42}
• {L, 12, 22, 32, 42, 43}
• …

이 정확한 커버 문제의 많은 해결책 중 하나는 다음과 같은 12가지 선택사항이다.

• {나, 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}
• {T, 61, 71, 72, 73, 81}
• {V, 68, 78, 86, 87, 88}
• {Y, 74, 82, 83, 84, 85}

이러한 선택사항은 펜토미노 타일링 문제에 대한 다음 해결책에 해당한다.

펜토미노 타일링 문제는 정확한 타격 세트 문제보다는 정확한 커버 문제로 더 자연스럽게 보여지는데, 각 선택 사항을 각각의 제약조건 집합으로 보는 것이 더 자연스럽기 때문이다.

각각의 선택은 열거하기 쉬운 6개의 제약조건과 관련이 있다.반면에, 각각의 제약조건은 열거하기 어려운 많은 선택과 관련이 있다.

정확한 표지 문제든 정확한 타격 세트 문제로 보든 매트릭스 표현은 동일하며, 선택에 해당하는 행은 1568개, 제약조건에 해당하는 열은 72개다.각 행은 펜토미노를 식별하는 열에 1개씩, 펜토미노가 다루는 사각형을 식별하는 열에 5개의 1s를 포함한다.

매트릭스를 이용하여 컴퓨터는 예를 들어 춤추는 링크를 사용하여 모든 해결책을 비교적 빨리 찾을 수 있다.

스도쿠

주요 기사:스도쿠, 스도쿠의 수학, 스도쿠 해결 알고리즘

스도쿠의 문제는 특정한 제약조건을 만족시키기 위해 격자의 셀(또는 제곱)에 숫자(또는 숫자, 값, 기호)를 할당하는 것이다.

표준 9×9 스도쿠 변종에는 다음과 같은 네 가지 종류의 제약이 있다.

행-열:행과 열의 각 교차점, 즉 각 셀은 정확히 하나의 숫자를 포함해야 한다.

행 번호:각 행은 각 숫자를 정확히 한 번 포함해야 함

열 번호:각 열에는 각 숫자가 정확히 한 번 포함되어야 한다.

상자 번호:각 상자는 각 번호를 정확히 한 번 포함해야 한다.

첫 번째 제약조건은 사소한 것처럼 보일 수 있지만, 그럼에도 불구하고 셀당 하나의 숫자만 존재하도록 하는 것이 필요하다.직관적으로 숫자를 셀에 배치하는 것은 동일한 열, 행 또는 상자를 공유하는 다른 셀에 해당 번호를 배치하는 것을 금지하고 또한 현재 점유 중인 셀에 다른 번호를 배치하는 것을 금지한다.

스도쿠를 푸는 것은 정확한 표지 문제다.

보다 정확히 말하면 스도쿠 문제 해결은 정확한 타격 세트 문제로서, 각 제약조건이 정확히 하나의 선택 가능성을 포함하는 (즉, 타격에) 가능성을 선택하는 문제로 볼 때, 정확한 커버 문제와 같다.위의 (일반화)정확한 표지 문제에 대한 표기법에서 X는 가능성의 집합, Y는 제약조건 집합, R은 "ins insident"의 이진관계다.

각각의 특정 번호를 특정 셀에 할당하는 것은 가능성(또는 후보)이다.스도쿠를 연필과 종이로 연주할 때 가능성을 흔히 연필 자국이라고 한다.

각각의 9×9 셀이 9개의 숫자 중 한 개씩 할당되는 표준 9×9 스도쿠 변종에서는 9×9×9=729 가능성이 있다.행, 열 및 숫자에 대한 명확한 표기법을 사용하여 가능성 레이블을 지정할 수 있다.

R1C1#1, R1C1#2, …, R9C9#9.

각 종류의 제약이 정확히 어떤 것을 포함한다는 사실은 스도쿠를 정확한 타격 세트 문제로 만드는 것이다.제약조건은 제약조건 집합으로 나타낼 수 있다.문제는 각 제약조건 집합이 정확히 하나의 선택된 가능성을 포함하는 가능성(즉, 타격)을 선택하는 것이다.

표준 9×9 스도쿠 변종에서는 네 종류의 제약조건에 해당하는 네 종류의 제약조건이 있다.

행-기둥: 행-기둥 구속조건 집합에는 특정 행과 열의 교차, 즉 셀의 교차 가능성이 모두 포함된다.예를 들어, R1C1이라는 레이블을 지정할 수 있는 1행과 1열에 대해 설정된 제약조건에는 1행과 1열에 대한 9가지 가능성이 있지만 다음과 같은 숫자가 다르다.

R1C1 = { R1C1#1, R1C1#2, R1C1#3, R1C1#4, R1C1#5, R1C1#6, R1C1#7, R1C1#8, R1C1#9}.

행 번호:행 번호 제약 조건 집합에는 특정 행과 번호에 대한 모든 가능성이 포함되어 있다.예를 들어, R1#1이라는 레이블을 지정할 수 있는 1행과 1행에 대해 설정된 제약조건에는 1행과 1행에 대한 9가지 가능성이 있지만 다음과 같은 다른 열이 포함된다.

R1#1 = { R1C1#1, R1C2#1, R1C3#1, R1C4#1, R1C5#1, R1C6#1, R1C7#1, R1C8#1, R1C9#1}.

열 번호:열 번호 제약 조건 집합에는 특정 열과 숫자에 대한 모든 가능성이 포함되어 있다.예를 들어, C1#1이라는 레이블을 지정할 수 있는 1열과 1열에 대해 설정된 제약조건에는 1열과 1열에 대한 9가지 가능성이 있지만 다른 행이 포함된다.

C1#1 = { R1C1#1, R2C1#1, R3C1#1, R4C1#1, R5C1#1, R6C1#1, R7C1#1, R8C1#1, R9C1#1}.

상자 번호: 상자 번호 제약 조건 집합에는 특정 상자와 숫자에 대한 모든 가능성이 포함되어 있다.예를 들어, B1#1이라고 라벨을 붙일 수 있는 상자 1(상단 레프트한드 코너)과 숫자 1에 대해 설정된 제약조건은 상자 1과 숫자 1의 셀에 대한 9가지 가능성을 포함한다.

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=81개 행-열 제약조건 세트, 9×9=81개 행-번호 제약조건 세트, 9×9=81개 열-번호 제약조건 세트, 9×9=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]

RxCy#z는 좌표 x, y, z를 가진 3차원 공간에서 9×9×9 큐브로서 배열할 수 있다는 점에 유의한다.Then each row Rx, column Cy, or number #z is a 9×9×1 "slice" of possibilities; each box Bw is a 9x3×3 "tube" of possibilities; each row-column constraint set RxCy, row-number constraint set Rx#z, or column-number constraint set Cy#z is a 9x1×1 "strip" of possibilities; each box-number constraint set Bw#z is a 3x3×1 "square" of possibilities; and eac 가능성 RxCy#z는 하나의 가능성으로 구성된 1x1×1 "쿠비"이다.또한 각 제약조건 집합 또는 가능성은 구성요소 집합의 교차점이다.예를 들어, R1C2#3 = R1 c C2 # #3이며, 여기서 ∩은 교차점을 설정함을 의미한다.

다른 스도쿠 변주곡은 행, 열, 숫자 및/또는 제약조건의 종류가 다르지만 모두 가능성과 제약조건 세트를 수반하므로 정확한 타격세트 문제로 볼 수 있다.

N 퀸즈 문제

이 구간은 확장이 필요하다.추가하면 도와줄 수 있다. (2008년 7월)

N 퀸즈 문제는 일반화된 정확한 커버 문제의 한 예다.^[3]이 문제에는 다음과 같은 네 가지 종류의 제약이 따른다.

순위: 각 N 등급에 대해 정확히 한 명의 여왕이 있어야 한다.

파일: 각 N 파일에 대해 퀸이 정확히 한 명씩 있어야 한다.

대각선:2N - 1 대각선 각각에 대해 최대 1명의 여왕이 있어야 한다.

역 대각선:2N - 1 역 대각선 각각에 대해, 최대 1명의 여왕이 있어야 한다.

2N 순위 및 파일 제약 조건이 1차 제약 조건을 형성하는 반면 4N - 2 대각선 및 역 대각선 제약 조건이 2차 제약 조건을 형성한다는 점에 유의하십시오.또한, 첫 번째와 마지막 대각선과 역방향 대각선은 각각 체스보드의 사각형 하나만 포함하기 때문에 생략할 수 있으며, 따라서 이차적 제약의 수를 4N - 6으로 줄일 수 있다.그러면 N 퀸즈 문제의 행렬은 N행과² 6N - 6열로, 체스 보드의 각 사각형에 가능한 퀸을 배치하기 위한 각 행과 각 제약조건에 대한 각 열을 가진다.

참고 항목

• 제약 만족도 문제
• 댄싱 링크스
• 차이 맵 알고리즘
• 히트 세트
• Karp의 21개의 NP 완성 문제
• 크누스의 알고리즘 X
• NP 완료 문제 목록
• 완벽한 매칭과 3차원 매칭은 정확한 커버 문제의 특별한 경우
• 집합 파티션

참조

외부 링크

• C에서 정확한 커버 해결사의 무료 소프트웨어 구현 - 알고리즘 X와 춤추는 링크를 사용한다.스도쿠와 로직 그리드 퍼즐의 예를 포함한다.
• 골랑의 정확한 커버 용액 - 알고리즘 X와 춤추는 링크를 사용한다.스도쿠와 n-퀴엔의 예를 포함한다.
• 정확한 표지 - 산술 참조 프로젝트