기사의 여행
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
기사의 여행은 체스판의 각 칸을 정확히 한 번씩 방문하는 기물의 이동 경로를 찾는 문제로, 수학 및 컴퓨터 과학 분야에서 연구되어 왔다. 9세기부터 언급된 이 문제는 1600년대에 대칭적인 나이트 투어 연구로 이어졌으며, 20세기에는 문학적 기법으로 활용되기도 했다. 기사의 여행은 체스판의 크기에 따라 해답 존재 여부가 달라지며, 슈웽크의 정리와 컬과 콘래드의 정리를 통해 특정 크기의 체스판에서는 해답이 불가능함을 알 수 있다. 분할 정복, 반스도르프 규칙, 인공 신경망 등 다양한 알고리즘을 사용하여 이 문제를 해결할 수 있으며, 오일러의 해법은 이 문제 해결에 중요한 이정표가 되었다.
더 읽어볼만한 페이지
- 해밀턴 경로 - 외판원 문제
외판원 문제(TSP)는 여러 도시를 모두 한 번씩 방문하고 출발점으로 돌아오는 최소 비용의 이동 순서를 구하는 문제로, NP-난해 문제에 속하며, 배송 계획 등에 응용되고 다양한 해법이 존재한다. - 체스 문제 - 변형 체스 기물
변형 체스 기물은 표준 체스와 다른 움직임을 가진 기물들을 사용하며, 다양한 표기법과 기물 가치를 통해 득점과 전략 수립에 활용된다. - 체스 문제 - 투 나이트 엔드게임
투 나이트 엔드게임은 체스 종반전에서 두 개의 나이트가 상대의 킹 또는 폰을 상대로 벌이는 상황으로, 특정 조건 하에서 체크메이트가 가능하며 폰의 위치와 츠크츠방 개념이 승패에 중요한 영향을 미치는 유형이다. - 수학적 체스 문제 - 맨해튼 거리
맨해튼 거리는 좌표축에 평행하게 측정한 거리 차이의 절댓값 합으로, 택시 기하학이라고도 불리며, 체스 룩의 이동이나 격자 도시 이동 거리 측정에 활용된다. - 수학적 체스 문제 - 체비쇼프 거리
체비쇼프 거리는 두 벡터 또는 점 사이의 거리 측정 방식으로, 각 좌표 성분 차이의 절댓값 중 최댓값으로 정의되며 L∞ 거리라고도 불린다.
| 기사의 여행 | |
|---|---|
| 개요 | |
| 이름 | 기사의 여행 |
| 설명 | 모든 칸을 정확히 한 번씩 방문하는 기사의 이동 시퀀스 |
| 퍼즐 유형 | 조합 퍼즐 |
| 관련 항목 | 해밀턴 경로 문제 |
| 특성 | |
| 수학적 표현 | 그래프 이론에서의 해밀턴 경로 |
| 목적 | 체스판의 모든 칸을 한 번씩 방문하는 경로를 찾는 것 |
| 규칙 | 기사는 체스에서와 같이 "L"자 모양으로 움직임 |
| 변형 | 닫힌 기사의 여행 (시작과 끝 칸이 기사의 움직임으로 연결됨) 반기사의 여행 (체스판의 절반만 방문) |
| 해결 방법 | |
| 경고르의 규칙 | 각 단계에서 가장 적게 방문한 인접 칸으로 이동하는 휴리스틱 알고리즘 |
| 분할 정복 | 작은 보드를 해결하고 이를 결합하여 더 큰 솔루션을 형성하는 방법 |
| 역사 | |
| 기원 | 9세기 인도 또는 아랍 세계 |
| 유럽 소개 | 18세기 |
| 연구 | 레온하르트 오일러 히람 콕스 폰 바싱 |
| 추가 정보 | |
| 완전 그래프 | 모든 정점 쌍이 가장자리에 연결된 그래프 |
| 해밀턴 경로 | 그래프의 모든 정점을 정확히 한 번 방문하는 경로 |
| 해밀턴 회로 | 해밀턴 경로이면서 시작 정점과 끝 정점이 같은 경로 |
| 예시 | |
 | |
2. 역사
기사의 여행 문제는 그래프 이론에서 다루는 해밀턴 경로 문제의 한 예시이며, 특히 시작점으로 돌아오는 닫힌 기사의 여행(closed knight's tour)을 찾는 문제는 해밀턴 순환 문제에 해당한다. 일반적인 해밀턴 경로 문제와는 달리, 기사의 여행 문제는 선형 시간 안에 해결할 수 있는 효율적인 알고리즘이 존재한다.[4]
기사의 여행 문제에 대한 가장 오래된 기록은 서기 9세기 인도 문헌에서 찾아볼 수 있다. 산스크리트어 수사학 작품인 Rudrata의 에는 체스판 절반 크기에서 기사의 이동 경로를 이용한 시 형식이 등장한다.[5] 이후 14세기 베단타 데시카나 17세기 바타 닐라칸타 등 인도 학자들에 의해 다양한 형태의 기사의 여행이 연구되었다.[6][7][8]
서양에서는 18세기 수학자 레온하르트 오일러가 이 문제를 본격적으로 연구하기 시작했으며, 19세기에는 H. C. 폰 반스도르프가 기사의 여행을 완성하는 체계적인 방법인 반스도르프 규칙을 발표했다.
20세기에 들어서는 문학 실험 그룹 울리포 작가들이 기사의 여행을 창작 기법으로 활용했으며, 조르주 페렉은 소설 ''인생 사용 설명서''의 장 순서를 10 × 10 크기 보드에서의 기사의 여행 경로에 따라 배열하기도 했다. 현대 체스 경기에서도 2010년 세계 체스 선수권 대회 당시 비스와나탄 아난드가 보여준 연속적인 나이트 이동이 기사의 여행과 연관되어 언급되기도 했다.
2. 1. 초기 언급
기사의 여행 문제에 대한 가장 오래된 기록은 서기 9세기로 거슬러 올라간다. 산스크리트어로 된 수사학 작품인 Rudrata의 [5](5.15)에서는 체스판 절반 크기에서 기사의 이동 경로 패턴을 또는 '말의 걸음 배열'이라는 정교한 시적 형태로 제시했다. 이 시는 각 8음절로 이루어진 4행으로 구성되어 있으며, 동일한 구절을 왼쪽에서 오른쪽으로 읽거나 기사의 이동 경로를 따라 읽을 수 있다. 산스크리트어 표기에 사용되는 인도계 문자는 음절 문자 체계이므로, 각 음절을 체스판의 한 칸에 대응시킬 수 있다. Rudrata가 제시한 예시는 다음과 같다.| 세 | 나 | 리 | 리 | 리 | 나 | 나 | 리 |
|---|---|---|---|---|---|---|---|
| 리 | 나 | 나 | 나 | 나 | 리 | 리 | 리 |
| ㄴ | 리 | 나 | 리 | 레 | 나 | 리 | 나 |
| 리 | 리 | 리 | 나 | 나 | 나 | 나 | 리 |
이를 로마자로 표기하면 다음과 같다.
| se | nā | lī | lī | lī | nā | nā | lī |
|---|---|---|---|---|---|---|---|
| lī | nā | nā | nā | nā | lī | lī | lī |
| na | lī | nā | lī | le | nā | lī | nā |
| lī | lī | lī | nā | nā | nā | nā | lī |
예를 들어, 첫 번째 줄은 왼쪽에서 오른쪽으로 '세나리리리나나리'로 읽을 수 있다. 또한 기사의 이동 경로를 따라 첫 번째 칸(1.1 '세')에서 시작하여 두 번째 줄 세 번째 칸(2.3 '나'), 첫 번째 줄 다섯 번째 칸(1.5 '리'), 두 번째 줄 일곱 번째 칸(2.7 '리'), 네 번째 줄 여덟 번째 칸(4.8 '리'), 세 번째 줄 여섯 번째 칸(3.6 '나'), 네 번째 줄 네 번째 칸(4.4 '나'), 세 번째 줄 두 번째 칸(3.2 '리') 순서로 이동하며 읽어도 동일한 구절이 된다.
14세기 스리 바이슈나바교 시인이자 철학자인 베단타 데시카는 란가나타 신의 신성한 샌들을 찬양하는 1,008행의 대작 (제30장: ''Chitra Paddhati'')에서 기사의 여행을 활용했다. 그는 각각 32개의 문자로 구성된 두 개의 연속적인 산스크리트어 구절(아누슈투브 운율)을 작곡했는데, 두 번째 구절은 4 × 8 크기의 보드에서 기사의 이동 경로를 따라 첫 번째 구절의 문자를 배열하여 만들 수 있다. 왼쪽 상단 모서리에서 시작하는 이 방식은 첫 번째 구절(19번째 구절)의 문자를 이용해 두 번째 구절(20번째 구절)을 생성한다.[6] 로마자로 표기된 19번째 구절과 각 문자의 이동 순서(괄호 안 숫자)는 다음과 같다.
| sThi (1) | rA (30) | ga (9) | sAm (20) | sa (3) | dhA (24) | rA (11) | dhyA (26) |
| vi (16) | ha (19) | thA (2) | ka (29) | tha (10) | thA (27) | ma (4) | thA (23) |
| sa (31) | thpA (8) | dhu (17) | kE (14) | sa (21) | rA (6) | sA (25) | mA (12) |
| ran (18) | ga (15) | rA (32) | ja (7) | pa (28) | dha (13) | nna (22) | ya (5) |
위 표의 이동 순서(1번 'sThi' → 2번 'thA' → 3번 'sa' → ...)를 따라 문자를 배열하면 다음과 같은 20번째 구절이 만들어진다.
sThi thA sa ma ya rA ja thpA
ga tha rA mA dha kE ga vi |
dhu ran ha sAm sa nna thA dhA
sA dhyA thA pa ka rA sa rA ||
전설에 따르면, 데시카는 도전 과제로서 하룻밤 만에 이 특별한 ''차투랑가 투랑가 파다반담''을 포함하여 의 1,008개 구절 전체를 작곡했다고 전해진다.[7]
17세기경에 쓰여진 산스크리트어 의례, 법, 정치를 다룬 백과사전적 작품인 바타 닐라칸타(Bhatta Nilakantha)의 제5권에는 세 가지의 기사의 여행이 기록되어 있다. 이 투어들은 시작점으로 돌아오는 닫힌 투어일 뿐만 아니라 대칭적인 특징을 가지며, 동일한 투어를 기반으로 하되 시작 칸만 다르게 표현되었다.[8] 닐라칸타의 연구는 완전한 대칭성을 갖춘 닫힌 투어를 제시했다는 점에서 주목할 만하며, 이는 레온하르트 오일러가 유사한 연구 결과를 발표한 1759년보다 최소 60년 이상 앞선 뛰어난 업적으로 평가된다.
2. 2. 근대적 발전
1600년 또는 1700년경에 쓰여진 것으로 추정되는 산스크리트어 의례, 법, 정치를 다룬 백과사전적 작품인 바트 닐라칸타의 바가반타바스카라 제5권에는 세 가지의 나이트 투어가 보고되었다. 이 투어들은 단순히 시작점으로 돌아오는 재진입형일 뿐만 아니라 대칭적인 특징을 가지며, 동일한 투어를 기반으로 다른 칸에서 시작하는 형태로 제시되었다.[8] 닐라칸타의 연구는 완전한 대칭성을 가진 폐쇄형 투어를 제시했다는 점에서 레온하르트 오일러의 연구(1759년)보다 최소 60년 앞선 뛰어난 업적으로 평가받는다.
닐라칸타 이후, 나이트 투어 문제를 연구한 서양의 초기 수학자 중 한 명은 레온하르트 오일러였다. 이후 1823년에는 H. C. 폰 반스도르프가 나이트 투어를 완성하는 첫 번째 체계적인 절차인 반스도르프 규칙을 발표했다.
20세기에는 문학 실험 그룹인 울리포 작가들이 나이트 투어를 창작 활동에 활용했다. 특히 주목할 만한 사례는 조르주 페렉의 소설 ''인생 사용 설명서''로, 이 작품은 10 × 10 크기의 체스판 위에서 이루어지는 나이트 투어 경로를 따라 각 장의 순서를 배열하는 독특한 구조를 가지고 있다.
현대에 와서는 체스 경기 중에도 나이트 투어가 언급되기도 했다. 2010년 세계 체스 선수권 대회에서 비스와나탄 아난드는 베셀린 토팔로프와의 여섯 번째 경기 도중, 자신의 두 나이트를 번갈아 움직이며 총 13번의 연속적인 나이트 이동을 선보였다. 이를 지켜보던 온라인 해설자들은 아난드가 경기 중에 나이트 투어 문제를 풀고 있는 것 아니냐는 농담을 하기도 했다.
3. 존재 조건
나이트 투어 문제는 그래프 이론에서 보다 일반적인 해밀턴 경로 문제의 한 예이다. 말이 모든 칸을 한 번씩 방문하고 시작점으로 돌아오는 닫힌 나이트 투어를 찾는 문제는 해밀턴 사이클 문제의 한 예이기도 하다. 일반적인 해밀턴 경로 문제와 달리, 나이트 투어 문제는 선형 시간 안에 해결할 수 있다는 특징이 있다.[4]
특정 크기의 보드에서 나이트 투어가 가능한지, 가능하다면 어떤 조건에서 가능한지에 대한 연구가 진행되어 왔다. 슈웽크(Schwenk)는 닫힌 나이트 투어가 가능한 조건을 증명했으며,[10] 컬(Cull)과 콘래드(Conrad) 등은 열린 나이트 투어가 가능한 조건을 증명했다.[4][18][11][12] 자세한 조건은 아래 하위 문단에서 설명한다.
3. 1. 슈웽크의 정리
슈웽크(Schwenk)[10]는 ''m'' ≤ ''n''인 ''m'' × ''n'' 크기의 보드에서, 다음 세 가지 조건 중 하나 이상에 해당하지 않는 한 항상 폐쇄 나이트 투어가 가능함을 증명했다.
# ''m''과 ''n''이 모두 홀수일 경우
# ''m''이 1, 2 또는 4일 경우
# ''m''이 3이고 ''n''이 4, 6 또는 8일 경우
3. 2. 컬과 콘래드의 정리
컬(Cull) 연구팀과 콘래드(Conrad) 연구팀은 더 작은 차원(''m'')이 5 이상인 직사각형 보드에서는 열린 나이트 투어가 항상 가능함을 증명했다.[4][18] ''m'' ≤ ''n''인 ''m'' × ''n'' 보드에 대해, 다음 세 가지 조건 중 하나 이상이 충족되지 않는 한 나이트 투어는 항상 가능하다.# ''m'' = 1 또는 2
# ''m'' = 3이고 ''n'' = 3, 5 또는 6[11]
# ''m'' = 4이고 ''n'' = 4.[12]
4. 투어의 수
8 × 8 체스판에는 정확히 26,534,728,821,064개의 방향성 폐쇄 순회(같은 경로를 반대 방향으로 이동하는 두 순회, 회전, 반사를 각각 계산)가 존재한다.[13][14][15] 무방향성 폐쇄 순회의 수는 방향성 폐쇄 순회 수의 절반이다. 한편, 6 × 6 체스판에는 9,862개의 무방향성 폐쇄 순회가 있다.[16]
4. 1. 방향성 투어
8 × 8 체스판에는 정확히 26,534,728,821,064개의 방향 폐쇄 순회가 존재한다. 여기서 방향성 폐쇄 순회는 같은 경로를 반대 방향으로 이동하는 두 순회를 별도로 계산하며, 회전이나 반사로 얻어지는 순회 역시 각각 다른 것으로 간주한다.[13][14][15]무방향 폐쇄 순회는 모든 순회를 반대 방향으로도 추적할 수 있으므로, 그 수는 방향성 폐쇄 순회 수의 정확히 절반이 된다. 따라서 8 × 8 체스판의 무방향 폐쇄 순회 수는 13,267,364,410,532개이다. 한편, 6 × 6 체스판에는 9,862개의 무방향 폐쇄 순회가 있다.[16]
''n'' × ''n'' 체스판에서의 방향 순회(열린 순회 및 닫힌 순회 포함)의 수는 다음과 같다.
| n | 방향 순회의 수 (열린 순회 및 닫힌 순회) n × n 체스판 |
|---|---|
| 1 | 1 |
| 2 | 0 |
| 3 | 0 |
| 4 | 0 |
| 5 | 1,728 |
| 6 | 6,637,920 |
| 7 | 165,575,218,320 |
| 8 | 19,591,828,170,979,904 |
4. 2. 체스판 크기에 따른 투어 수
8 × 8 체스판에는 정확히 26,534,728,821,064개의 방향성 닫힌 순회(같은 경로를 반대 방향으로 이동하는 두 순회, 회전, 반사를 각각 계산)가 존재한다.[13][14][15] 무방향성 닫힌 순회의 수는 이의 절반인데, 모든 순회를 반대로 추적할 수 있기 때문이다. 6 × 6 체스판에는 9,862개의 무방향성 닫힌 순회가 있다.[16]다양한 크기의 체스판에서 가능한 방향성 순회(열린 순회 및 닫힌 순회 포함)의 수는 다음과 같다.
| n | 방향 순회의 수(열린 순회 및 닫힌 순회) n × n 체스판 |
|---|---|
| 1 | 1 |
| 2 | 0 |
| 3 | 0 |
| 4 | 0 |
| 5 | 1,728 |
| 6 | 6,637,920 |
| 7 | 165,575,218,320 |
| 8 | 19,591,828,170,979,904 |
5. 컴퓨터를 이용한 투어 찾기
컴퓨터를 사용하여 주어진 체스판에서 기사의 여행 경로를 찾는 방법에는 여러 가지가 있다. 이러한 방법 중 일부는 알고리즘이고, 다른 일부는 휴리스틱이다.
5. 1. 무차별 대입 알고리즘
기사의 여행 문제를 해결하기 위해 무차별 대입법을 사용하는 것은 아주 작은 보드를 제외하고는 현실적으로 어렵다.[17] 예를 들어 8 × 8 보드에는 13,267,364,410,532개의 기사의 여행 경로가 존재하며,[13] 기사의 움직임으로 만들 수 있는 같은 길이의 이동 순서는 이보다 훨씬 많다. 이렇게 많은 경우의 수를 모두 탐색하는 것은 현대의 컴퓨터(또는 컴퓨터 네트워크) 성능으로도 매우 어렵다. 하지만 경우의 수가 많다는 것이 문제 자체가 해결하기 어렵다는 의미는 아니며, "인간의 통찰력과 독창성을 활용하면 ... 큰 어려움 없이" 해결할 수 있다.[17]5. 2. 분할 정복 알고리즘
보드를 더 작은 조각으로 나누고, 각 조각에 대한 투어를 구성한 다음 조각들을 이어 붙임으로써 대부분의 직사각형 보드에서 선형 시간 내에, 즉 보드 위의 사각형 수에 비례하는 시간 안에 투어를 구성할 수 있다.[18][19]5. 3. 반스도르프 규칙
반스도르프 규칙(Warnsdorff's rule)은 나이트 투어 문제를 해결하는 휴리스틱 방법 중 하나이다. 이 규칙은 나이트가 다음 이동할 칸을 선택할 때, 아직 방문하지 않은 칸 중에서 앞으로 이동할 수 있는 경로의 수가 가장 적은 칸을 선택하도록 한다. 각 후보 칸에서 이동 가능한 경로 수를 계산할 때는 이미 방문했던 칸은 제외한다. 때로는 이동 가능한 경로 수가 같은 칸이 여러 개 있을 수 있는데, 이러한 동점 상황을 해결하기 위한 다양한 방법들이 연구되었다. 대표적으로 Pohl이 제안한 방법[22]과 Squirrel과 Cull이 제안한 방법[20] 등이 있다.
이 규칙은 그래프 이론의 관점에서도 해석될 수 있다. 체스판의 각 칸을 정점(vertex)으로, 나이트의 이동 경로를 간선(edge)으로 생각하면, 반스도르프 규칙은 현재 위치한 정점에서 연결된 인접 정점 중 차수(degree, 해당 정점에 연결된 간선의 수)가 가장 낮은 정점으로 이동하는 것과 같다.[21] 일반적으로 임의의 그래프에서 해밀턴 경로 문제(모든 정점을 한 번씩만 방문하는 경로 찾기)는 NP-난해 문제로 알려져 계산적으로 매우 어렵지만, 반스도르프 규칙과 같은 휴리스틱을 사용하면 실제 여러 그래프에서 선형 시간 내에 해를 효과적으로 찾을 수 있다.[22] 나이트 투어 문제는 이러한 휴리스틱이 성공적으로 적용되는 특별한 경우에 해당한다.[23]
이 휴리스틱은 1823년 H. C. von Warnsdorf가 "Des Rösselsprungs einfachste und allgemeinste Lösung"(기사의 이동에 대한 가장 간단하고 일반적인 해법)이라는 글에서 처음으로 설명했다.[23]
반스도르프 규칙을 이용하여 어떤 시작 위치에서든 나이트 투어를 찾는 컴퓨터 프로그램은 Gordon Horsington이 작성하여 1984년 "Century/Acorn User Book of Computer Puzzles"라는 책에 실리기도 했다.[24]
5. 4. 신경망 해법
나이트 투어 문제는 그래프 이론에서 더 일반적인 해밀턴 경로 문제의 한 예시이다. 닫힌 나이트 투어를 찾는 문제는 해밀턴 사이클 문제의 예시이기도 하다. 일반적인 해밀턴 경로 문제와 달리, 나이트 투어 문제는 선형 시간 안에 해결할 수 있다.[4]
나이트 투어 문제는 신경망을 구현하여 해결할 수도 있다.[25] 이 방식에서는 각 가능한 나이트의 이동을 뉴런으로 표현하도록 네트워크를 설정한다. 각 뉴런은 초기에 무작위로 "활성"(출력 1) 또는 "비활성"(출력 0) 상태를 가지며, 1은 해당 뉴런(이동 경로)이 해법의 일부임을 의미한다. 또한, 각 뉴런은 0으로 초기화되는 상태 함수를 가진다.
네트워크가 작동하면, 각 뉴런은 이웃 뉴런(정확히 나이트 이동 한 번 거리의 경로에 해당하는 뉴런)의 상태와 출력을 바탕으로 자신의 상태와 출력을 다음 규칙에 따라 변경한다.
::
::
여기서 는 시간을 나타내는 이산적인 단계이고, 는 칸 에서 칸 로 이동하는 경로에 해당하는 뉴런의 상태이다. 는 해당 뉴런의 출력(활성 또는 비활성)이며, 는 해당 뉴런의 이웃 뉴런 집합이다.
네트워크는 때로 발산할 수도 있지만, 결국에는 수렴하게 되는데, 이는 모든 뉴런의 상태가 시간 에서 로 변하지 않을 때 발생한다. 네트워크가 수렴하면, 그 결과는 하나의 완전한 나이트 투어를 나타내거나, 또는 같은 보드 내에서 여러 개의 독립적인 나이트 이동 경로(회로)를 나타낸다.
6. 해답 예시
다양한 나이트 투어의 해답 예시는 다음과 같다.
6. 1. 오일러의 해답
나이트 투어를 연구한 초기 수학자 중 한 명은 레온하르트 오일러였다.
오일러가 고안한 해답 중 하나는 오른쪽 그림과 같다. 각 칸의 숫자는 나이트가 해당 칸을 방문하는 순서를 나타낸다. 이 해답은 특별한 성질을 가지는데, 각 가로줄(랭크)과 세로줄(파일)에 있는 숫자들의 합이 모두 260으로 동일하다. 이는 준마방진의 일종이지만, 대각선의 합은 260이 아니므로 완전한 마방진은 아니다. 8x8 크기의 체스판에서는 모든 행, 열, 그리고 두 주 대각선의 합까지 같은 완전 마방진 형태의 나이트 투어는 존재하지 않는 것으로 알려져 있다.[9]
6. 2. 기타 해답
레온하르트 오일러가 고안한 해답 중 하나는 오른쪽 그림과 같다. 그림의 각 칸에는 나이트가 지나가는 순서대로 숫자가 매겨져 있다. 이 해답은 각 가로줄과 세로줄의 숫자 합이 모두 260으로 동일한 특징을 가진다.오일러의 해답처럼 가로줄과 세로줄의 합이 일정한 경우 준마방진이라고 부른다. 하지만 대각선의 합은 마법 상수인 260과 다르기 때문에 완전한 마방진은 아니다. 8x8 체스판에서는 완전한 마방진 형태의 나이트 투어는 존재하지 않는 것으로 알려져 있다.[9]
그 외 다른 해답 예시는 다음과 같다.
참조
[1]
MS thesis
Knight's Tours and Zeta Functions
https://scholarworks[...]
San José State University
2017
[2]
서적
The Oxford Companion to Chess
Oxford University Press
[3]
서적
Java How To Program Fifth Edition.
https://archive.org/[...]
Prentice Hall
2003
[4]
논문
Solution of the Knight's Hamiltonian Path Problem on Chessboards
[5]
서적
Kavyalankara of Rudrata (Sanskrit text, with Hindi translation);
Parimal Sanskrit Series No. 30
[6]
웹사이트
Indian Institute of Information Technology, Bangalore
https://www.iiitb.ac[...]
2019-10-11
[7]
웹사이트
Bridge-India: Paduka Sahasram by Vedanta Desika
http://bridge-india.[...]
2019-10-16
[8]
문서
A History of Chess by Murray
[9]
웹사이트
MathWorld News: There Are No Magic Knight's Tours on the Chessboard
http://mathworld.wol[...]
[10]
논문
Which Rectangular Chessboards Have a Knight's Tour?
https://pdfs.semanti[...]
[11]
웹사이트
Knight's Tours on 3 by N Boards
https://www.mayhemat[...]
[12]
웹사이트
Knight's Tours on 4 by N Boards
https://www.mayhemat[...]
[13]
논문
The number of knight's tours equals 33,439,123,484,294—counting with binary decision diagrams
[14]
논문
Knight's Tours on an {{nowrap|8 × 8}} Chessboard
http://www.combinato[...]
Department of Computer Science, Australian National University
2013-09-22
[15]
서적
Branching Programs and Binary Decision Diagrams
https://books.google[...]
Society for Industrial & Applied Mathematics
[16]
웹사이트
Knight Graph
[17]
기타
Evolutionary Optimization Algorithms
https://books.google[...]
John Wiley & Sons
[18]
논문
Knight's Tour Revisited
https://www.fq.math.[...]
[19]
논문
An Efficient Algorithm for the Knight's Tour Problem
https://core.ac.uk/d[...]
[20]
웹사이트
A Warnsdorff-Rule Algorithm for Knight's Tours on Square Boards
https://github.com/d[...]
2011-08-21
[21]
학회자료
A Predictive Data Analytic for the Hardness of Hamiltonian Cycle Problem Instances
https://pure.uva.nl/[...]
Xpert Publishing Services
2018-11-27
[22]
논문
A method for finding Hamilton paths and Knight's tours
1967-07
[23]
학회자료
Finding Re-entrant Knight's Tours on N-by-M Boards
Association for Computing Machinery
[24]
서적
Century/Acorn User Book of Computer Puzzles
Century Communications
[25]
기타
"Neural network computing for knight's tour problems."
[26]
서적
数学遊園地
講談社
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com