Cave

 Cave는 숫자힌트를 이용해 판 위에 위치하는 동굴의 모습을 찾는 퍼즐이다. 

 GMP Blog를 참조해(https://www.gmpuzzles.com/blog/cave-rules-and-info/) 그 역사를 간략히 요약하자면, Cave는 니코리에서 BAG란 이름으로 최초로 등장했다가 02년 US/Canadian Qualifying Test for WPC에서 Corral이라는 이름으로 점차 알려지기 시작했다. 이때까지만 해도 이 퍼즐은 Loop 퍼즐로 인식되었으나(Corral은 울타리를 의미한다.) 고리를 그리는 것 보다 고리 바깥 영역을 찾는 것이 더 효율적으로 풀린다는 것이 알려지고나서, 규칙의 재정의와 함께 Cave, 즉 동굴이라는 이름으로 자리잡게 되었다.

 

규칙

몇몇 칸을 색칠해 하나의 단일한 빈 공간(색칠되지 않은 영역)을 만들어라 이 때,

1. 색칠되지 않은 칸들은 모두 변을 통해 연결되어야한다. (꼭짓점끼리 붙은 것은 연결된 걸로 치지 않는다.)

2. 모든 색칠된 칸들은 변을 통해 판 바깥과 연결되어야한다. (꼭짓점끼리 붙은 것은 연결된 걸로 치지 않는다.)

3. 숫자가 적힌 칸은 색칠될 수 없으며, 각 숫자는 그 숫자가 적힌 칸에서 가로, 세로로 보이는 (자신을 포함한) 모든 색칠되지 않은 칸의 개수를 뜻해야한다.

 

 바로 예시를 보자.

예시

흰 공간(동굴)이 모두 연결되어있는 모습을 살펴보자. 2번 규칙에 의해 이 동굴은 색칠된 영역을 감쌀 수 없다. 즉 도넛 모양의 동굴은 불가능하다.

주황색으로 색칠된 영역들은 크기와 모양이 제각각이지만 모두 판 바깥과 연결된다는 것도 확인할 수 있다.(만약 판 바깥을 모조리 색칠한다면 색칠된 영역들도 하나의 연결된 영역이 될 것이다.)

이 퍼즐에서는 2×2 규칙이 없으므로 색칠된 칸들이든 아니든 모두 2×2 공간이 생길 수 있다.

 

마지막으로 숫자 단서들을 살펴보자. 6줄1열과 5줄6열엔 모두 숫자 5가 있지만 전자는 세로로만 길쭉하게 다섯 빈칸들이 보이고, 후자는 가로세로 모두 세 칸씩 균등히 빈칸들이 보인다. 가로세로는 단서가 있는 칸에서 겹치므로 3+3-1=5로 다섯개의 색칠되지 않은 빈 칸이 정확하게 세어진다.

 

Cave에서는 규칙에서 파생되는 매우 중요한 정리가 있다. 

정리

2×2 공간에서 대각선끼리는 색칠여부가 같고 변끼리 붙은 두 칸은 색칠여부가 다를 때, 이를 체커보드 패턴(checkerboard pattern)이라 하자. 이 때, Cave에서는 체커보드 패턴이 존재할 수 없다.

이유는 1,2번 규칙에서 쉽게 알 수 있다. 색칠되지 않은 두 빈 칸은 1번에 의해 반드시 연결되어야한다. 따라서 색칠칸 둘 중 하나를 감싸는 형태로 동굴이 형성되어야한다. 그러나 이는 2번에 의해 불가능하다. 

물론 아주 엄밀히 수학적으로 증명하려면 위상수학적 접근이 필요하겠으나, 이 정도 설명만으로도 대부분의 경우 납득하리라 믿어 의심치 않는다. 

 

몇가지 직접 만든 예시문제들을 아래 올린다.

 

Cave는 현재 Grandmaster Puzzles에서 Region Division(이하 RD)으로 분류되고 있다. loop 컨셉에서 시작했다는 퍼즐이 어찌하여 shading도 아니고 RD로 분류되는가? 이에 대해서는 이야기가 많으니 후속 글에서 이어 쓰도록 하겠다.