기사의 여행 | 오일러의 해밀턴 경로와 Warnsdorff의 휴리스틱 알고리즘

knight를 움직여 체스판 전체를 중복 없이 다 지날 수 있을까요?

기사의 여행은 대표적인 해밀턴회로문제이다.

기사의 여행 문제는 64개의 꼭짓점을 갖는 기사 그래프(knight’s graph)에서

해밀턴 경로와 해밀턴 순환을 찾는 문제입니다.

( 나이트문제는 수학사에 자주 등장한다. 이전영상: 과르니의 체스퍼즐(듀드니방법 , 위상기하학적접근)

---

이 그래프는 8×8 체스판에서 나이트가 움직일 수 있는 방향들을 변으로 하죠.

오일러가 발견한 대칭적이며 재진입적인 해밀턴회로를 영상으로 경퀘하게 표현하였다.

Warnsdorff의 휴리스틱 알고리즘을 사용하지 않고 대칭성이 있는 해밀터회로를 발견한 오일러

문제를 풀기만도 벅찼는데 역시 오일러는 단순하게 풀기만 하는 것이 아니라 대칭성 있는 방식으로 풀어내는군요.

나이트의 이동경로는 두 칸 전진 후 좌 또는 우로 한 칸이라고 기억하시는 게 편하죠. 

왼쪽 체스판에서 나이트가 움직이는 방식을 보여줍니다. 

레온하르트 오일러를 비롯한 많은 수학자들이 이 문제의 다양한 변형에 대하여 연구하였습니다.

1857년 해밀턴이 만든 아이코시안게임

해밀턴회로는 아일랜드 출신의 수학자 윌리엄 로원 해밀턴(Sir William Rowan Hamilton,1805-1865)이 

그래프 이론에 제기한 회로의 종류입니다. 

윌리엄 로원 해밀턴은 케일리-해밀턴정리(Cayley–Hamilton theorem)로도 유명하죠. 

요즘은 고교과정에서 케일리해밀턴정리와 그래프를 배우지 않으니 어색할 거예요.

하지만 유명한 수학자인 오일러와 해밀턴의 발자취를 좇아가는 것은 즐거우니 가볍게 따라가 봐요.

---

기본적으로 해밀턴 경로(Hamiltonian path)는 어떤 연결된 그래프에서 

모든 꼭짓점을 한 번씩만 지나는 경로(path)를 부르는 말이에요. 

또한 이 경로가 회로일 경우 해밀턴 회로라고 하며, 어떤 그래프가 해밀턴 회로를 가질 때, 

이 그래프를 해밀턴 그래프라고 합니다. 

오일러 회로와 같이 다루기도 하죠. 

1857년 해밀턴이 만든 아이코시안게임이(icosian game-1857) 대표적인 예입니다.(상단 이미지의 오른쪽)

오일러 회로는 해밀턴회로와는 달리  연결된 그래프의 모든 변을 중복 없이 지나는 회로입니다. 

한붓그리기로 많은 사람들에게 알려져 있죠.  

 

9세기 Rudrata's Kavyalankara에서 하프보드에서의 기사의 여행이 시적표현으로 처음 언급되었다.

9세기 Rudrata's Kavyalankara 에서 하프보드에서의 기사의 여행이 

정교한 시적표현(citra-alaṅkāra)으로 처음 언급되었습니다.

8음절로 이루어진 4행의 동일한 구절은 왼쪽에서 오른쪽으로 읽으며, 여행 중인 기사의 길을 나타냅니다.

영상에 순서대로 움직이도록 표현하였습니다. 

어려운 문제들을 음률에 담아 기억하고 전해지는  인도식 방법이 보입니다.

보다 즐겁게 기억하고 생각을 할 수 있는 방법이라고 생각합니다.

옛날 인도의 수학자들이 유튜브를 했다면 많은 뛰어난 지식과 지혜들이

사라지지 않고 훨씬 더 잘 전달되었을 텐데 말이죠. 

 

 

 

Bhat Nilakantha가 쓴 Bhagavantabaskaraby의 다섯 번째 책(17세기말)과 

 Leonhard Euler(1759)는  대칭적이며 재진입적인 해밀턴회로를 발견했습니다.

유튜브영상의 시작이 이 해밀턴회로를 표현하고 있습니다. 

숫자를 강조하고 싶어 크게했으나 조금 작게 할 걸 하고 후회중이다.

기사의 여행 문제는 64개의 꼭짓점을 갖는 기사 그래프(영어: knight’s graph)에서 

해밀턴 경로와 해밀턴 순환을 찾는 문제였죠. 

이 그래프는 8×8 체스판에서 나이트가 움직일 수 있는 방향들을 변으로 하죠.

여기에서 각 숫자는 해당위치에서 가능한 이동 횟수를 나타냅니다.

숫자가 가려서 보이지 않는다. 위에서부터 3,7,7,7,5,2 이다.

 b4에서 시작을 한다고 가정하면 나이트가 갈 수 있는 곳 중에서 다음에 갈 수 있는 경우의 수는 다음과 같죠.

가장 적은 곳은 a2가 되겠죠.

이렇게 다음에 갈 수 있는 경우의 수가 가장 적은 곳으로 계속 이동하여 해밀턴 경로를 찾는 것이 

1823년 HC von Warnsdorff의 "Des Rösselsprungs einfachste und allgemeinste Lösung"에서 

처음 소개된 Warnsdorff의 규칙입니다. 

Warnsdorff의 법칙을 사용하여 모든 시작 위치에 대한 기사 투어를 찾는 컴퓨터 프로그램은 

Gordon Horsington이 작성했으며 1984년 'Century/Acorn User Book of Computer Puzzles '

라는 책에 출판되었습니다. 

8×8 보드에는 정확히 26,534,728,821,064개의 기사의 여행이 있습니다.

기사의 여행과 해밀턴회로였습니다. 감사합니다.

기사의여행 유튜브영상입니다.
https://youtu.be/WoMHDix7y6k