슬링크

슬리더링크(Slitherlink)는 스도쿠를 유행시킨 일본의 퍼즐 출판사 니콜리(Nikoli)가 소개한 고리 만들기 퍼즐이다. 규칙은 간단하지만 푸는 것은 만만치 않다.

퍼즐은 점들이 격자 모양으로 놓여 만들어지는 직사각형 칸들의 모음이다. 각 칸은 비어 있거나 $0$부터 $3$까지의 정수 하나를 담는다. 이웃한 점들을 가로 또는 세로 선분으로 이어, 그려진 선분들이 하나의 닫힌 고리(모든 점에서 선분이 정확히 $2$개 또는 $0$개만 만나는 연결된 순환)를 이루도록 해야 한다. 숫자가 적힌 칸은 그 숫자와 정확히 같은 개수의 변이 고리에 포함되어야 하고, 비어 있는 칸은 몇 개의 변이 포함되든 상관없다. 올바른 퍼즐은 고리가 유일하게 정해지도록 충분한 숫자를 담고 있다.

일반적인 슬리더링크를 푸는 문제는 (도쿄대학의 Takayuki Yato에 의해) NP-완전임이 알려져 있는데, 이는 일반적인 경우를 푸는 효율적인 알고리즘이 알려져 있지 않다는 뜻이다. 그러나 제약을 하나 두면 실용적으로 풀 수 있게 된다. 이 문제에서 다루는 슬링크(Slink)는 빈 칸이 없는 슬리더링크이다. 즉 모든 칸에는 네 변 중 몇 개가 고리에 속하는지를 나타내는 숫자가 반드시 적혀 있다. 슬링크 퍼즐의 정답 고리는 대응되는 슬리더링크와 완전히 같으며, 주어지는 정보의 양만 다르다.

슬링크 퍼즐은 국소적인 추론 규칙들을 반복 적용하여 풀 수 있다. 예를 들어 $0$이 적힌 칸의 네 변은 모두 고리에 포함되지 않는다. 또한 $0$에 이웃한 $3$은 $0$과 맞닿은 변이 제거되므로 남는 세 변을 모두 사용해야 한다.

아래는 추론 규칙들이다. 각 규칙은 어떤 변을 고리에 반드시 포함시키거나, 고리에서 반드시 제외한다. 모든 입력 퍼즐은, 적용 가능한 규칙을 항상 적용하기만 하면 도달할 수 있는 유일한 정답을 가짐이 보장된다.

1. 0: $0$이 적힌 칸의 네 변은 모두 고리에서 제외된다.
2. 개수 완성: 어떤 칸의 숫자가 $n$인데 이미 정확히 $n$개의 변이 고리에 포함되어 있으면, 남은 변들은 모두 제외된다.
3. 개수 강제: 어떤 칸의 숫자가 $n$인데 가능한 변이 정확히 $n$개만 남았으면(나머지는 이미 제외됨), 남은 변들을 모두 포함시킨다.
4. 인접한 3: 두 $3$ 칸이 한 변을 공유하면, 그 공유 변과 그에 평행한 양쪽 바깥 변까지 모두 포함된다.
5. 대각선 3: 두 $3$ 칸이 한 점에서만 맞닿으면(대각선으로 인접), 서로 가장 먼 두 바깥 모서리의 변들이 포함된다.
6. 강제된 방향: 어떤 점에 이미 선분 하나가 들어와 있고 그 점에서 가능한 다른 변이 하나뿐이면, 그 변이 포함된다.
7. 꽉 찬 점: 어떤 점에 이미 두 개의 변이 고리에 포함되어 있으면, 그 점의 나머지 변들은 제외된다.
8. 죽은 점: 어떤 점의 세 변이 제외되면 네 번째 변도 제외된다(점의 차수는 항상 $0$ 또는 $2$이며 $1$일 수 없다).
9. 막힌 3(모서리): 한 점에서 두 변이 막혀 있는 $3$(예: 퍼즐의 구석)은 그 점에서 만나는 두 변을 반드시 포함해야 한다.
10. 모서리가 막힌 2: 어떤 $2$의 한 꼭짓점에서 두 변이 막혀 있고, 그 $2$의 이웃 꼭짓점에서도 한 변이 막혀 있으면, 그 이웃 꼭짓점의 나머지 한 변이 포함된다.
11. 막힌 1(모서리): 한 점에서 두 변이 모두 막혀 있는 $1$(예: 퍼즐의 구석)은 그 점의 나머지 두 변을 제외해야 한다.
12. 3의 꼭짓점으로 진입: 고리가 어떤 $3$의 한 꼭짓점에 도달했고 그 꼭짓점에서 $3$의 바깥으로 나가는 변이 막혀 있으면, 그 $3$의 반대쪽 꼭짓점에 있는 두 변이 포함된다.
13. 대각선의 3과 1: $3$과 $1$이 한 점에서만 맞닿아 있고, $1$에서 가장 먼 $3$의 꼭짓점에서 바깥으로 나가는 변들이 막혀 있으면, $1$의 먼 쪽 꼭짓점의 변들도 막힌다. 반대 방향으로도 성립한다.
14. 2의 꼭짓점으로 진입: 고리가 어떤 $2$의 한 꼭짓점에 도달했고 그 꼭짓점에서 바깥으로 나가는 변이 막혀 있으며, 대각선 반대쪽 꼭짓점에서 바깥으로 나가는 변 하나도 막혀 있으면, 그 반대쪽 꼭짓점의 다른 바깥 변이 포함된다.
15. 1의 꼭짓점으로 진입: 고리가 어떤 $1$의 한 꼭짓점에 도달했고 그 꼭짓점에서 $1$의 바깥으로 나가는 변이 막혀 있으면, 그 $1$의 반대쪽 꼭짓점에 있는 두 변은 제외된다.

입력은 여러 개의 슬링크 퍼즐로 이루어진다.

각 퍼즐은 두 정수 $r$과 $c$(칸의 행 수와 열 수)가 공백으로 구분되어 적힌 줄로 시작한다. 이어지는 $r$개의 줄에는 각각 $0$부터 $3$까지의 정수 $c$개가 공백으로 구분되어 주어지며, 이는 각 칸의 숫자를 나타낸다.

퍼즐의 크기는 최소 $2 \times 2$에서 최대 $20 \times 20$ 칸이다. 모든 퍼즐은 적용 가능한 추론 규칙을 항상 적용하기만 하면 찾을 수 있는 유일한 정답을 가짐이 보장된다.

0 0이 적힌 줄은 입력의 끝을 나타내며 퍼즐이 아니다.

각 퍼즐에 대해, 먼저 퍼즐 번호를 한 줄에 출력한다(첫 번째 퍼즐은 $1$, 두 번째는 $2$, …). 그다음 그 퍼즐의 유일한 정답을 그림으로 출력한다.

정답은 다음 문자로 그린다. 고리의 세로 변은 세로줄 |, 가로 변은 붙임표 -, 고리가 방향을 바꾸는 점은 더하기표 +로 나타낸다. 각 칸의 숫자는 좌우에 각각 공백 한 칸씩을 두고 출력한다. 고리가 방향을 바꾸지 않고 곧게 지나가는 점은 그 점이 놓인 선의 일부로 그려진다.

그림 전체를 우물정자 #로 만든 테두리로 둘러싼다. 이때 왼쪽 위 칸의 숫자는 테두리에서 오른쪽으로 네 번째 칸, 아래로 세 번째 칸에 오도록 하고, 오른쪽 아래 칸의 숫자는 테두리에서 왼쪽으로 네 번째 칸, 위로 세 번째 칸에 오도록 한다. 정확한 형식은 예제를 그대로 따른다.