[메뉴얼] 기법 15 - 나이스 루프 (Nice Loop)
링크 논리를 기반으로 모든 후보 숫자의 가능성을 탐색합니다.
따라서, 링크의 기본 개념을 이해하고 있어야 합니다.
링크의 원리를 이해하려면 **강한 링크(strong link)**와 **약한 링크(weak link)**의 개념을 알아야 합니다.
강한 링크
두 개의 후보 숫자가 같은 위치(셀, 행, 열, 또는 3x3 박스)에 있을 때 형성됩니다. 이 둘 중 하나가 참이라면 다른 하나는 반드시 거짓이 됩니다.
예시: 한 셀에 후보 숫자 1과 2만 남아 있다면, 1이 정답이면 2는 반드시 오답입니다. 이 둘은 강하게 연결되어 있습니다.
특징: A와 B가 강하게 연결되어 있을 때, 'A이면 NOT B', 'NOT A이면 B'가 항상 성립합니다.
약한 링크
두 개의 후보 숫자가 다른 위치에 있지만, 한 위치(셀, 행, 열, 또는 3x3 박스)에 같은 숫자가 여러 개 있을 때 형성됩니다. 이 둘 중 하나가 거짓일 때, 다른 하나가 참이 될 가능성이 있습니다.
예시: 한 행에 숫자 3의 후보가 두 개의 다른 셀에 있다고 가정해 봅시다. 한 셀에 3이 들어가지 않으면, 다른 셀에 3이 들어갈 수 있습니다. 특징: 'NOT A이면 B'는 성립하지만, 'A이면 NOT B'는 항상 성립하지 않습니다.
나이스 루프은 AIC(Alternate Inference Chain)라고 불리웁니다.
일반적으로 강한 링크로 시작하고 끝나는 것이 기본입니다. 강한 링크로 시작하는 것만 나이스 루프에서 다루게 됩니다. 왜냐하면, 체인은 (거짓이면 참) - (참이면 거짓) - (거짓이면 참)...의 논리 흐름을 가집니다.
이를 통해 체인의 양 끝점은 강하게 연결됩니다. 즉, 시작점이 거짓이면 끝점은 참이 되고, 시작점이 참이면 끝점은 거짓이 됩니다. 따라서 양 끝점이 동시에 거짓일 수는 없다는 논리적 결론을 얻게 되며, 이를 활용해 체인의 양 끝점을 동시에 볼 수 있는 다른 후보 숫자들을 제거할 수 있습니다.
즉, 시작 셀과 끝나는 셀까지 순환(loop)하는 구조를 가지고 있습니다. 시작셀과 끝셀이 같은 유닛에 있는 경우에 모순되는 후보숫자를 제거하는 원리입니다.
글로 설명하기 엄청 어려운 로직입니다. 아래 사례를 보면서 이해하면 쉽게 이해할 수 있습니다. 단, 이해하는 것과 스도쿠에서 나이스 루프를 활용하는 것은 완전히 다른 개념입니다. 실제 사람이 나이스 루프를 이용해서 3단계 초과하는 로직을 완성하려면 쉽지 않기 때문입니다.
만약 나이스 루프로 풀 수 밖에 없는 스도쿠 문제가 있다면, 단순 취미의 영역을 넘어서 전문적인 스도쿠 장인이 되어야 합니다. 머리 식히기 용으로 즐기는 유저에게는 너무 어려운 영역에 속한다고 생각합니다. 이런 문제가 있다면 하나셀 스도쿠의 나이스 루프 풀이를 이용하거나, 다른 스도쿠 솔버를 이용해서 진행하는 편이 좋아 보입니다. 원리를 알고 문제를 풀기에는 너무 험난하고 힘든 풀이법입니다. 그냥 원리만 이해하는 수준에서 알고 있어도 충분합니다.
|
|
이제는 실제 사례를 보면서, 어떻게 나이스 루프를 통해서 후보숫자를 제거하는지 알아 봅니다.
나이스 루프의 종류 - 타입 1, 타입 2, 타입 3으로 총 3가지 종류가 있습니다. 이 분류법은 아직까지 명쾌하게 확립된 개념은 아니고, 유튜브 sudokuwiki의 분류 방식을 차용했습니다.
타입 1
'type 1 endpoints are same digit (이조건은 continuous와 같음, 다른점은, 같은 하우스에 있으면 안됨. 같은 하우스에 있는 경우는 continuous임)
타입 2
'type 2 endpoints are different digit
(A=false, B= true, C = false, D = true)
비교, A에 나머지 값에 D가 들어 있거나, D의 나머지 값에 A가 있으면 그 값을 제거함)
시작셀과 끝셀의 후보숫자가 다른 경우, 시작셀과 끝셀에 있는 후보숫자 이외의 숫자를 제거함,
즉, 시작셀과 끝셀에 나이스 루프를 구성하는 숫자를 포함하여햐 한다는 의미임
①번셀의 후보숫자는 79, 시작은 항상 스트롱으로 시작, 즉, 9가 false임
⑥번셀의 후보숫자는 149, 끝 숫자는 4가 true임
루프 순서는 ①s9①w7②s7②w8③s8④w8④s2⑤w2⑤s4⑥(s=strong, w=weak)
①번셀과 ⑥번셀은 같은 행 유닛에 존재함. 따라서, 2가지 경우의 수가 존재함
|
|
나이스 루프 타입2라고 하지만, 사실상 첫셀과 마지막셀이 마주보는(같은 유닛에 있음) 상태이기 때문에 continuous loop와 유사합니다.
①번셀 ⑥번셀은 마주보고 있으면서 상대셀에서 같은 후보숫자를 공유하고 있다면, 당연히 공존할 수 없습니다. 그래서 2개중 1개는 무조건 제거 되는 것입니다. 하지만 왜 loop에 사용된 셀이 아니라, **상대셀**인가?가 주요한 이유입니다.
loop는 정순으로 및 역순으로 true다. 스트롱에서 시작한 루프가 스트롱으로 끝나면 이 루프는 역으로 순환하여도 동일한 루프를 유지합니다. 왜냐하면 false-true-false...로 연결된 루프이기 때문이다. 그래서 루프 속에 등장한 숫자 이외의 숫자를 제거할 수 있다라고 합니다.
타입 2의 다른 예제)
①번셀의 후보숫자는 68, 시작 숫자는 8(false)
⑦번셀의 후보숫자는 268, 끝 숫자는 2(true)
루프는 ①s8①w6②s6②w9③s9④w9④s2⑤w2⑥s2⑦
①번셀과 ⑦번셀은 같은 행 유닛에 존재함. 따라서, 2가지 경우의 수가 존재함
|
|
타입 3(무한 루프 continuous loop)
