8-3. AIC
우리는 이미 'AIC 기초(AIC Basics)' 레슨에서 AIC가 무엇인지 이야기했습니다.
요약하자면:
- AIC는 강한 링크와 약한 링크가 번갈아 나타나는 체인입니다.
- 강한 링크로 시작해서 강한 링크로 끝납니다.
- 후보 숫자가 거짓이라고 가정하면서 체인을 시작합니다.
- 체인의 양쪽 끝 중 하나는 항상 참이 되므로, 체인의 양 끝을 모두 바라보는 모든 후보 숫자를 제거할 수 있습니다.
우리는 또한 다음에 대해서도 이야기했습니다:
- 약한 링크가 어떻게 우리를 참인 후보 숫자에서 거짓인 후보 숫자로 이끄는지, 그리고
- 강한 링크가 어떻게 우리를 거짓인 후보 숫자에서 참인 후보 숫자로 이끄는지.
지금까지 우리는 바이-로컬(bi-locals)과 바이-밸류(bi-values)로만 체인을 만들었습니다. 이것들은 항상 약하게도 연결되어 있고 강하게도 연결되어 있습니다.
하지만 강하게 연결된 모든 후보 숫자가 약하게도 연결되어 있는 것은 아니며, 이번 레슨에서는 바로 그 경우들을 살펴볼 것입니다.
후보 숫자 그룹 (Candidate Groups)
지금까지 저는 링크가 두 후보 숫자 사이에만 존재한다고 말씀드렸지만, 그것이 전부는 아닙니다.
링크는 후보 숫자들의 '그룹' 사이에도 존재할 수 있습니다.
이 그리드를 예로 들어보겠습니다.
여기서 만약 [주황색 1]이 거짓이라면...
... [초록색 1] 중 하나는 참이 되고, 그러면...
... 두 개의 [주황색 1]은 모두 거짓이 되고, 그러면...
... [초록색 1]은 참이 되며...
... 체인은 양방향으로 작동하므로(가역적이므로) 우리는 [빨간색 1]을 제거할 수 있습니다.
(체인의 양쪽 끝 중 하나는 항상 참이 됩니다.)
여기서 우리가 어떤 종류의 링크를 사용했다고 생각하시나요?
맞습니다. 해당 행에 3개의 후보 숫자가 있음에도 불구하고 우리는 강한 링크를 사용했습니다.
이것은 오른쪽에 있는 두 개의 1이 같은 박스 안에 있기 때문에 가능합니다. 이들이 바로 우리의 후보 숫자 '그룹'입니다.
즉, 강한 링크는 두 개의 단일 후보 숫자 사이가 아니라, 하나의 후보 숫자 [주황색 1]과 후보 숫자 그룹 [초록색 1] 사이에 형성된 것입니다.
논리는 동일하게 유지되며, 체인을 계속 이어나갈 때 이 그룹을 개별 후보 숫자들로 취급하지 않는 것이 중요합니다.
따라서 우리의 다음 단계는 현재 그룹 [초록색 1]에서 다음 그룹 [주황색 1]로 이동하는 것입니다.
(그리고 그 후 그룹은 오른쪽 아래에 있는 다음 후보 숫자 [초록색 1]로 연결됩니다.)
여기서 우리는 두 그룹 사이의 '약한 링크'를 사용했습니다.
만약 체인이 달랐다면 강한 링크를 쉽게 사용할 수도 있었을 것입니다. 왜냐하면 한 그룹의 후보 숫자들이 모두 거짓이라면, 다른 그룹의 후보 숫자 중 하나는 반드시 참이 되었을 것이기 때문입니다.
자, 만약 이 셀도 1이 될 수 있다면 어떻게 될까요?
이 셀은 두 그룹 모두에 속하게 될 것입니다. 논리는 여전히 작동합니다:
만약 이 세 개의 후보 숫자가 거짓이라면...
... 저 세 개의 후보 숫자 중 하나는 참이 될 것입니다.
모든 것이 예상대로 작동합니다.
약한 링크가 없는 경우 (No weak link)
이제 두 그룹 사이의 링크가 약했던 이전 예시로 돌아가 보겠습니다. 이번에는 박스 중앙에 추가 후보 숫자가 존재하게 됩니다.
두 그룹이 교차하는 지점에 있는 그 후보 숫자가 모든 것을 바꿉니다.
이제 이 셀들 중 하나가 참이라고 해서...
... 이 셀들이 거짓이 된다는 것을 의미하지 않습니다.
만약 중앙의 후보 숫자가 참이라면 두 그룹 모두 참이 되지만, 체인에서는 항상 참과 거짓이 번갈아 나타나야만 합니다.
따라서 교차하는 두 그룹은 '강한 링크는 가능하지만 약한 링크는 불가능한' 예시 중 하나입니다.
또 다른 예시 (Another example)
강한 링크가 약한 링크를 의미하지 않는 또 다른 예는 '유니크 레탱글(Unique Rectangles)'입니다.
만약 이런 유니크 레탱글이 있다면, 치명적인 패턴(deadly pattern)을 방지하기 위해 [노란색 8] 중 하나가 거짓일 때 다른 하나는 반드시 참이어야 한다는 것을 알 수 있습니다. (따라서 이들은 강하게 연결되어 있습니다).
하지만 이들은 약하게 연결되어 있지는 않습니다. 둘 중 하나가 참이라고 해서 두 번째 것이 거짓이어야 한다고 추론할 수 없기 때문입니다. 둘 다 참일 수도 있으니까요.
마무리 (Finished)
여러 가지 기술을 AIC와 결합하는 것은 아주 재미있을 수 있습니다.
적용하기 어려울 수도 있지만, 유니크 레탱글(또는 다른 고급 기술)에서 나온 강한 링크를 AIC에 사용하여 후보 숫자를 제거해 냈을 때의 짜릿함은 엄청납니다.
한번 도전해 보세요!