중국 링 퍼즐 (구연환, 九連環, Chinese Ring Puzzle)

구연환(九連環)이라 할 때 그 한자의 뜻을 살펴보면, 아홉 구, 연결할 연, 고리 환으로 되어 있습니다. 즉, 9개의 링이 연결되어 있는 것이란 뜻입니다.
사진을 보시면 굳이 설명이 필요없을 정도입니다.

먼저 다양한 구연환 사진을 제시해 보겠습니다.

(출처: www.puzzlemuseum.com)

 

(출처: http://home.comcast.net/~l-whiting/attbi/CPR.html)

 

(출처: http://home.comcast.net/~l-whiting/attbi/CPR.html)

 

(출처: http://home.comcast.net/~l-whiting/attbi/CPR.html)

 

(출처: http://home.comcast.net/~l-whiting/attbi/CPR.html)

 

(출처: www.puzzlemuseum.com)

 

(출처: http://home.comcast.net/~l-whiting/attbi/CPR.html)

 

사진을 통해서 알 수 있듯이 링이 9개가 아닌 것들도 구연환이라 칭하겠습니다.
아울러 소재도 아이보리 상아에서부터, 금속, 나무, 플라스틱 등 매우 다양합니다.

구연환은 제목에서처럼 중국 링 퍼즐 (Chinese Rings Puzzle), 옥련환 (玉連環), 인내 퍼즐 (Patience Puzzle), 악마의 바늘 퍼즐 (Devil's Needle Puzzle), 카타콤 (Catacombs), 퍼즐링 링 (The Puzzling Rings), Meleda, Baguenaudier, Tiring Irons, 죄수의 자물쇠 (Prisoner's Lock), 용 자물쇠  (Dragon Lock) Cardan's Rings, Cardan's Suspension, Ring of Linked Rings, 인디언 링 (Indian Rings), Iron Irritation 등 여러가지로 불리고 있습니다
(Baguenaudier는 불어로서 'Time-Waster'라는 뜻이라고 하는 군요.)
Cardan's Rings 라는 표현은 예전에 소개한 호프만의 "Puzzles Old and New." 책에서도 나오는 표현입니다.

제리 슬로컴은 베를린에 있는 Peter Catel의 1785년도 카탈로그에서 구연환이 Nuremberg 라는 이름으로 홍보된 것을 발견합니다.
제리 슬로컴은 구연환이 독일에서 Zankeisen 이라는 이름으로 알려져 있는 것을 역시 발견합니다. Zankeisen은 Quarrel Iron 이라는 뜻이라고 하는군요. 이 단어를 따라 추적해보면 구연환의 역사는 유럽에서는 1541년으로 거슬러 올라갑니다.

이 구연환을 누가 맨 처음에 개발했는지에 대해서는 전반적으로 작자 미상으로 여기고 있습니다.
그러나 Wolfram Mathworld Site에 나와 있는 내용을 보면, 이 구연환 퍼즐은 중국의 Hung Ming (Chu-Ko Liang, 181 ~ 234 A.D.) 장군이 2세기 경에 발명했다고 Stewart Culin (1858-1929, 인류학자) 이 주장합니다.
전투를 위해 고향을 떠날때 그의 부인에게 만들어 주었다고 하는군요. 사랑하는 남편을 기다리는 고통을 이 퍼즐을 통해서 잊게 하고, 기다림의 무료함을 달래기 위한 목적이었다고 합니다.
그러나 이것은 아직까지 명확하게 입증되지 않은 상태라고 하는군요.

위 이름 중에서 자물쇠라는 표현이 들어가 있는 것처럼 구연환은 실제 자물쇠로도 사용 가능합니다. 과거에 프랑스에서는 농민들이 많이 사용했다고 하는군요. 대신 채우기도 어렵고 여는 것도 어렵겠지요. 

이 퍼즐을 푸는 과정에서 링의 숫자가 올라감에 따라 움직임 횟수는 기하급수적으로 늘어납니다.
정확히 숫자를 표현하면 아래 표와 같습니다. 

링의 갯수	최소 필요 움직임 횟수
3	5
4	10
5	21
6	42
7	85
8	170
9	341

위 표에서 일정한 규칙을 발견할 수 있습니다.
즉 링의 갯수가 하나씩 증가함에 따라 최소 필요 움직임 횟수는 거의 두배씩 증가합니다.
좀더 정확히 표현하면 링의 갯수가 짝수일 때는 정확히 두배, 홀수일 때는 두배에 1이 추가됩니다.

수학적인 관점에서 좀더 엄밀하게 표현하면 아래와 같습니다.
링의 갯수가 홀수일 경우: (2ⁿ⁺¹ - 1)/3
링의 갯수가 짝수일 경우: (2ⁿ⁺¹ - 2)/3

또는 다른 식으로 심플하게 표현하기도 하더군요.
[2ⁿ⁺¹/3], 단 꺾쇠 괄호의 의미는 소수점 이하는 절사하라는 것임. 

이것은 누적 이진법 (Binary Gray Code) 이라는 수학적 원리가 적용된 것이라 하는군요.
(퍼즐러 갱은 위 용어에 대한 우리말 표현을 몰라서 그냥 누적 이진법이라고 표현해보았습니다.
혹시 수학 전공하신 분 있으면 정확한 표현을 알려주시면 감사감사~~~)

아뭏든 링 숫자가 늘어남에 따라 거쳐야 하는 단계 수는 배로 증가하는 것을 알 수 있습니다.
자 여기서 문제한번 내 볼까요?
링이 10개일 때는 최소 필요 움직임 횟수는 몇회가 필요할까요?
너무 무시했나요?
ㅎㅎㅎ

그런데 일부 사이트에서는 위 표에 있는 것과 다른 횟수를 제시하기도 합니다.
예를 들면 링이 7개인 구연환의 경우에 85회가 아니라 64회라고 말입니다. 
다른 숫자를 주장하는 사이트도 어느 정도 공신력 있는 사이트이구요.
이러다 보니 퍼즐러 갱 처음에는 이런 상반된 주장 때문에 무지 헷갈렸습니다.

도대체 어느 주장이 맞는거야? 이것 참 나!!!! 하고 말이죠.

자 그럼 어느 것이 맞을까요?
퍼즐러 갱이 위에서 제시한 것과 다르게 주장하는 것이 틀린 것일까요?

정답을 말씀드리면 둘 다 맞다입니다.
무슨 말이냐구요?
둘 다 맞는 주장인데 서로 다른 주장인 것처럼 보이는 것은 움직임의 횟수를 계산하는 기준이 다르기 때문입니다.

구연환 퍼즐을 풀다 보면 연이어 있는 두 개의 링을 동시에 움직일 수 있는 상황이 자주 발생합니다.
이 때 두개의 링을 동시에 움직이는 것을 1회로 볼 것인가 아니면 2회로 볼 것인가의 차이입니다.
즉, 좀더 작은 숫자를 주장하는 경우는 1회로 간주한 상태에서의 숫자이고, 위 표에서 퍼즐러 갱이 제시한 숫자는 2회로 샘한 경우입니다.

이처럼 동시에 두개의 링을 움직이는 상황을 1회로 간주할 경우의 최소 필요 움직임 횟수는 아래 표와 같습니다.

링의 갯수	최소 필요 움직임 횟수
3	4
4	7
5	16
6	31
7	64
8	127
9	256

위 결과를 좀더 엄정하게 수식으로 표시하면 다음과 같습니다.
링의 갯수가 홀수일 경우: 2^n-1
링의 갯수가 짝수일 경우: 2^n-1 - 1

그런데 또 어느 사이트에서는 바로 위의 표와는 약간 다른 숫자를 주장하는 경우도 있습니다.
위의 표와 거의 같은 듯 하면서도 1회씩이 작은 숫자를 주장합니다.
좀더 정확히는 링의 갯수가 홀수일 때 이런 현상이 나타납니다.

이것 또한 계산의 기준이 다르기 때문에 나타나는 현상입니다.
링의 숫자가 홀수일 때는 맨 끝에 있는 링이 저절로 움직일 수 있기 때문에, 이 움직임을 횟수에 포함할 것이냐 배제할 것이냐의 이슈가 있습니다. 이것을 움직임 횟수에서 제외하면 위의 표에 나와 있는 것보다는 1씩이 작은 움직임 횟수가 나오게 되는 것이지요. 
맨 처음 움직이는 것을 뺄거냐 합산할 거냐의 차이가 있을 뿐입니다.
이런 기준을 적용하면 최소 필요 움직임 횟수는 아래 표와 같게 됩니다.
그리고 이 최소 필요 움직임 횟수는 단순한 누적 이진법이 적용된 숫자입니다.

링의 갯수	최소 필요 움직임 횟수	산식
3	3	1+2
4	7	1+2+4
5	15	1+2+4+8
6	31	1+2+4+8+16
7	63	1+2+4+8+16+32
8	127	1+2+4+8+16+32+64
9	255	1+2+4+8+16+32+64+128

일반적으로는 맨 위에 있는 표에서 제시한 숫자가 정석으로 통하고 있습니다.
각각의 모든 움직임을 정확하게 계산했기 때문이지요. 그리고 이 산식에서 각종 조건들을 부여하면 다른 방식의 숫자가 모두 산출되기 때문에 일종의 기본으로 통하고 있습니다.

재미난 점을 말씀드리면,
누적 이진법의 무서운 힘에 관한 것입니다.
링의 숫자가 하나 늘어날 때마다 움직임 횟수는 거의 배가 되기 때문에 푸는 해법이 무지 어려워지고 시간도 오래 걸리게 됩니다.
가령 링의 숫자가 65개일 경우를 가정해 보지요.
65개의 링일 경우의 움직임 횟수를 엑셀로 계산해 보니 '245957E+19' 이라고 나오더군요. 
이것을 숫자로 표현해 보면 24,595,700,000,000,000,000 회가 나오는군요. 숫자가 워낙 커서 이걸 어떻게 읽어야 할 지도 모르겠습니다. 아마도 2천4백5십9경5천7백조 회라고 읽는 것 같군요.
자 여기서 1초에 한번씩 움직일 정도로 숙달된 퍼즐러가 빨리 풀어 나간다 할 지라도 이 구연환 퍼즐을 다 풀기 위해서 소요되는 시간을 퍼즐러 갱 걍 심심해서 계산한번 해 보았습니다.
정확히 779,923,000,000 년이 걸리는 군요.
한번 읽어 볼게요.
7천7백9십9억2천3백만년이 걸리는 군요. 허걱^^
거의 7천8백년이나 걸린다니.

누적 이진법의 무서운 힘을 느끼셨습니까?

그 얇은 신문지 종이를 반으로 접고 그것을 다시 반으로 접고, 다시 반으로 접고 하는 식으로 반복하면 지구에서 달까지 가기 위해서는 몇회가 필요할 까요?
지구에서 달까지의 거리는 38만 4400 km 입니다.
신문지 종이의 두께를 0.1 mm라 가정하고, 퍼즐러 갱이 계산해 보니 42번 반복하면 43만 9805 km가 됩니다. 달까지 가고도 남네요.
어렸을 적에 들었던 이야기를 손수 엑셀을 이용해서 검증해 보니 재미있기도 하고, 다시한번 신기하다는 느낌이 드는군요.

아참 그리고 예전에 올린 '한니발(Hannibal) 목재 퍼즐' 글과 '코끼리 와이어 퍼즐(Elephant Wire Puzzle)' 글에서 코끼리 와이어 퍼즐, 한니발 퍼즐, 하노이의 탑 (Tower of Hanoi) 등이 모두 같은 원리가 적용된다고 했었지요.
이 구연환 퍼즐 처럼 링의 숫자가 올라감에 따라서 움직임 횟수가 기하급수적으로 올라가는 누적 이진법이 적용되는 것이지요.
참고로 한니발 퍼즐의 경우 프랑스에서는 구연환 퍼즐의 또다른 이름인 Boguendier로도 부른다고 하는군요.

에궁.
수학이 싫어서 이과를 가지 않고 문과를 간 퍼즐러갱이 수학을 다루고 있으니 머리에 쥐가 나는군요.
위의 내용을 이해하고 정리하느라 퍼즐러 갱 무지 고생했습니다.
박수좀 쳐주세요. 짝짝짝 말이죠.

자 이제 이 구연환 퍼즐을 푸는 방법에 대해서 말씀드리겠습니다.

구연환을 푸는 과정 중 스타팅 포인트에서 유의할 점이 하나 있습니다.
링의 갯수가 짝수일 경우에는 최초의 움직임에 있어서, 끝에 있는 두개의 링을 움직여야 한다는 것입니다.
링의 갯수가 홀수일 경우에는 최초의 움직임에 있어서, 끝에 있는 한개의 링을 움직여야 한다는 것입니다.

이 스타팅 포인트를 잘못 잡으면 영원히 미궁에 빠집니다.

그리고 5개의 링이 있는 구연환 퍼즐은 먼저 3개의 링이 있는 구연환 퍼즐을 먼저 다 푼 다음에 시작하면 됩니다.
마찬가지로 7개의 링이 있는 구연환 퍼즐은 5개의 링이 있는 구연환 퍼즐,
9개의 링이 있는 정식 구연환 퍼즐은 7개의 링이 있는 구연환 퍼즐을 먼저 다 푼 다음에 시작하면 됩니다.
9개-->8개, 7개-->6개, 5개-->4개 가 아니라는 것이지요.

마찬가지로 8개의 링이 있는 구연환 퍼즐은 6개의 링이 있는 구연환 퍼즐을 먼저 다 푼 다음에 시작하면 됩니다.
마찬가지고 6개의 링이 있는 구연환 퍼즐은 4개의 링이 있는 구연환 퍼즐을 먼저 다 푼 다음에 시작해야 하구요.
8개-->7개, 6개-->5개 가 아니라는 것이지요.

이것은 위에 말한 스타팅 포인트에서의 유의사항과도 일맥상통하지요.

이것의 해법을 말로 설명하기에는 상당히 어려움이 있으니 솔루션이 나와 있는 인터넷 페이지를 제시해 봅니다. 
http://home.comcast.net/~l-whiting/attbi/CPR.html
위 사이트에서는 7개의 링을 기준으로 이진법에 의한 설명, 사진에 의한 설명, 그래픽에 의한 설명 등이 잘 나와 있습니다.
http://britton.disted.camosun.bc.ca/chinesering/ninering_sol.html
위 사이트에서는 5개의 링을 기준으로 사진에 의해 설명하고 있습니다.

이 퍼즐을 푸는 동영상을 유튜브에서 한번 찾아보았습니다.
기본적으로 짝수와 홀수 링의 해법이 약간 다르기 때문에 두 종류의 구연환 퍼즐 해법 동영상을 제시해 드립니다.

아래는 6개의 링이 있는 구연환을 가지고서 해법 및 유사 퍼즐을 보여드리는 유튜브 동영상입니다.
아울러 유사 퍼즐도 보여주고 있습니다.
상당히 훌륭한 동영상이라 할 수 있겠습니다.

아래는 7개의 링이 있는 구연환을 가지고서 해법을 보여드리는 유튜브 동영상입니다.

참고로 유튜브 사이트(www.youtube.com)에 들어가서 'Chinese Ring Puzzle' 이라고 입력하시면 수많은 해법 동영상이 나옵니다.

그리고 아래 사이트에서는 구연환 퍼즐을 시뮬레이션할 수 있는 프로그램을 제공하고 있습니다.
링의 숫자를 3개부터 적용해 보면서 링의 숫자를 하나씩 올려가 보면 위에서 설명한 내용을 직접 체험할 수 있습니다.
버튼을 적당히 눌러보면 그 기능은 쉽게 파악할 수 있을 것입니다.
바로 가기 --> http://demonstrations.wolfram.com/TheChineseRingsPuzzle/

아래 사이트에서는 6개의 링을 기준으로 제시하고 있습니다.
위에서 언급한 프로그램보다는 성능이 떨어집니다.
바로 가기 --> http://britton.disted.camosun.bc.ca/patience/patience.htm

퍼즐러갱의 경우 이 구연환 퍼즐을 썩 좋아하지는 않습니다.
왜냐구요?
너무 단순한 원리가 적용되거든요.
단순 반복 작업 즉 노가다를 필요로 하는,
그래서 이름도 인내 퍼즐 (Patience Puzzle), 죄수의 자물쇠 (Prisoner's Lock) 란 이름이 붙어 있지요.

그래서 일부 퍼즐러들은 이 구연환 퍼즐을 탱글먼트 퍼즐(Disentanglement Puzzle)로 분류하는 대신에 순차 이동 퍼즐 (Sequential Movement Puzzle) 로 구분하기도 합니다.

오늘도 해피 퍼즐링~~

 

*아래 화면은 퍼즐러갱이 개설한 유튜브 '퍼즐러갱TV'의 초기화면입니다. 아래 그림을 클릭/터치하여 퍼즐러갱TV를 감상해 보시지요(구독과 좋아요는 저에게 큰 힘을 줍니다)!!