나이트 바꾸기 퍼즐 (Knight Exchange Puzzle)

 이 퍼즐은 과리니 디 포를리(Guarini di Forli)의 작품(1512년)으로, 가장 오래된 체스 퍼즐중 하나라고 한다.[1] 이 퍼즐을 풀기 위해선 간단하게, 체스에서 나이트(Knight)가 장기의 말(馬)처럼 날 일(日)자 대각선 방향으로 움직인다는 것만 알면 된다. 

(출처 : 위키백과)

 자 이제 본 문제로 넘어가자. 3×3 체스판 위에 4개의 나이트가 자리잡고 있다. 두 개의 나이트는 흰 색으로, 위의 양 꼭짓점에 있고, 남은 두 개의 나이트는 검은 색으로, 아래의 양 꼭짓점에 위치해있다. 문제가 요구하는 것은 바로 이 두 흰 나이트와 두 검은 나이트의 위치를 서로 바꾸어 보라는 것이다.

서로의 위치를 바꾸어 보아라.

 얼핏 보면 3×3의 체스판이 너무 작아서 볼가능할것도 같지만, 막상 직접 움직여보면 구조가 간단한 덕분에 쉽에 바꿀 수 있을 것이다. 만일 성공했다면, 옮기는데 든 횟수를 최소화하는데 주력해보자.



해답

최소 16번으로 가능하다.

 다음은 듀드니의 작품으로, 위 문제를 좀 더 어렵게 만든 문제다. 목적은 흰 색과 검은 색의 나이트를 서로 바꾸는 것으로 앞 문제와 같으며, 다만, 숫자가 좀 늘었다.

Exchange them, please.

해설

 복잡한 문제같지만, 매우 간단하게 풀 수 있는 방법이 있다. 우선 나이트가 움직일 수 있는 길을 직선으로 나타낸 다이어그램을 그리고, 마치 체스의 칸이 구슬이고, 선들이 목걸이의 실들이라고 생각하자. 그렇게 되면, 우리가 나타낸 다이어그램은 마치 목걸이처럼 펼칠 수 있어서 이 퍼즐의 구조가 눈에 확연히 들어온다.[2]

 

문제가 요구하는 것은 서로의 위치를 바꾸는 것이다. 그것은 곧 좌측 상단의 흰 색 나이트가 목걸이를 돌고 돌아 우측 하단의 칸에 자리잡고, 나머지 나이트들도 좀 전의 횐 색 나이트와 똑같이 목걸이의 반시계방향으로 돌아주면 되는 것으로, 각자 4번 씩 총 16번의 움직임으로 퍼즐을 해결할 수 있다. 간단한 위상수학적 변형이 문제 해결의 최소 휫수를 간단하게 증명하는 걸 도와준 것이다.

한결 낫지요?

 좀 더 어렵다는 두 번째 역시 이런 변형을 거치면 쉽게 풀 수 있다. 다만, 이번에는 실 조각이 14개나 생겨서 좀 복잡한 목걸이가 될 것이다. 엉켜있는 목걸이를 잘 풀었으면 좋겠군요.

 이런 종류의 문제들은 듀드니가 만든 것 말고도 어느정도 찾아보면 좀 있다. 3개씩 바꾸는 것 보다 더 어려운 퍼즐을 원하시는 분들은 아래의 사이트에 가서 열심이 머리를 굴려주세요.
http://www.ageofpuzzles.com/Puzzles/G-KnightsExchange/G-KnightsExchange.htm



참고한 책
[1] 재미있는 영재들의 수학퍼즐, 박부성 지음, (주)자음과 모음.  p50 마지막 줄.
[2] 이야기 수학퍼즐 아하!(원제 : Aha Insight), 마틴가드너 지음, 사계절.  p180-184.  책에선 이 방법을 '실과 구슬 모양의 분석'이라 하였다.
[3]http://www.puzzles.com/PuzzlePlayground/FourKnights/FourKnights.htm 
     http://www.puzzles.com/PuzzlePlayground/SixKnights/SixKnights.htm
    이 곳에서 문제를 다운로드 받아서 프린트해 볼 수 있다.