나이트 투어

Knight's tour
체스판 오픈 기사 투어
5×5 보드상의 오픈 나이트 투어 애니메이션

기사 투어는 기사가 각 광장을 정확히 한 번 방문하도록 체스판있는 기사의 일련의 움직임이다.기사가 시작 사각형에서 한 기사의 이동 거리인 사각형에서 끝나면(같은 경로를 따라 즉시 보드를 다시 둘러볼 수 있도록), 둘러보기는 닫힙니다(또는 다시 입장할 수 있습니다). 그렇지 않으면 [1][2]열려 있습니다.

기사의 여행 문제는 기사의 여행을 찾는 수학적인 문제이다.기사 투어를 찾기 위한 프로그램을 만드는 것은 컴퓨터 공학 [3]학생들에게 주어지는 일반적인 문제이다.기사 투어 문제의 변형에는 일반적인 8×8과 다른 크기의 체스판뿐만 아니라 불규칙한(직각형이 아닌) 보드도 포함된다.

이론.

표준 8×8 체스 보드에서 기사 투어에 사용할 수 있는 모든 경로를 보여주는 기사 투어의 그래프입니다.각 노드의 숫자는 해당 위치에서 수행할 수 있는 가능한 이동 수를 나타냅니다.

기사의 여행 문제는 그래프 이론에서 더 일반적인 해밀턴 경로 문제의 한 예이다.닫힌 기사의 투어를 찾는 문제도 마찬가지로 해밀턴 순환 문제의 한 예이다.일반적인 해밀턴 경로 문제와 달리, 기사의 투어 문제는 선형 시간 [4]내에 해결할 수 있습니다.

역사

체스 게임 기계인 터크에 의해 해결된 기사의 여행.이 특정 솔루션은 닫힌 상태(원형)이므로 보드 상의 어느 지점에서나 완료할 수 있습니다.

기사의 여행 문제에 대한 가장 오래된 언급은 서기 9세기로 거슬러 올라간다.루드라사의 시학 작품인 카비얄랑카라[5](5.15)에서는 기사가 반판을 타고 여행하는 패턴이 투라가파다반다 또는 말의 계단에 정렬된 것으로 정교한 시적 형상(시트라 알라카라)으로 표현되어 있다.8음절로 된 4행의 같은 구절을 왼쪽에서 오른쪽으로 읽거나 순회하는 기사의 길을 따라 읽으면 된다.산스크리트어에 사용되는 인디안 문자 체계는 음절 체계이기 때문에, 각 음절은 체스판의 정사각형을 나타낸다고 생각할 수 있다.Rudrata의 예는 다음과 같습니다.

से ना ली ली ली ना ना ली
ली ना ना ना ना ली ली ली
ली ना ली ले ना ली ना
ली ली ली ना ना ना ना ली

번역 완료:

인식하다 동작하다 동작하다 동작하다 동작하다
동작하다 동작하다 동작하다 동작하다
동작하다 동작하다 움직이다 동작하다
동작하다 동작하다 동작하다 동작하다

예를 들어, 첫 번째 줄을 왼쪽에서 오른쪽으로 읽거나 첫 번째 사각형에서 두 번째 줄, 세 번째 음절(2.3)로 이동한 다음 1.5~2.7~4.8~3.6~4.4~3.2로 읽습니다.

14세기 스리 바이슈나바 시인이자 철학자 베단타 데시카는 랑가나타 경의 신성한 샌들 스리랑암을 찬양하는 그의 1,008자 매그넘 작품, 즉 파두카 사하스람(30장: 치트라 파다티)에서 각각 32자를 포함한 산스크리트 계율을 연속적으로 작곡했다.1절부터 4×8 보드 위에서 왼쪽 [6]상단 모서리부터 나이트 투어를 한다.번역된 19절은 다음과 같다.

sThi

(1)

rA

(30)

(9)

샘.

(20)

sa

(3)

dhA

(24)

rA

(11)

dhya

(26)

vi

(16)

(19)

(2)

(29)

tha

(10)

(27)

엄마.

(4)

(23)

sa

(31)

thpA

(8)

dhu

(17)

kE

(14)

sa

(21)

rA

(6)

sA

(25)

엄마.

(12)

뛰었다

(18)

(15)

rA

(32)

네.

(7)

(28)

다하

(13)

nna

(22)

(5)

위 절에서 나이트 투어를 진행하면 얻을 수 있는 20절은 다음과 같습니다.

sthi tha sa ma ya rA ja thpA

ga ra mA dha kE ga vi

dhu run ha sam sanna tha dhA dhA.

sA dhyA tha pa ka rA sa rA

데시카는 하룻밤 사이에 1008절(위에서 언급한 특별한 차투랑가 투랑가 파다반담 포함)을 모두 [7]작곡한 것으로 알려져 있다.

바트 닐라칸타가 쓴 바가반타바스카라비의 다섯 번째 책에 보고된 투어는 약 1600년 또는 약 1700년에 쓰여진 산스크리트어로 된 자전거 작품입니다.이 투어는 재진입뿐만 아니라 대칭적이며,[8] 같은 투어에 기초해 다른 정사각형부터 시작한다.닐라칸타의 업적은 오일러(1759)의 업적보다 최소 60년 앞선 완전 대칭 닫힌 여행이라는 놀라운 업적이다.

오일러의 반마법의 정사각형(대각선은 마법의 상수에 합하지 않음, 260)도 기사의 여행을 형성한다.

닐라칸타 이후, 그 기사의 여행을 조사한 최초의 수학자 중 한 명은 레온하르트 오일러였다.기사의 여행을 끝내기 위한 첫 번째 절차는 1823년 H. C. von Warnsdorf에 의해 처음 기술된 Warnsdorf의 규칙이었다.

20세기에는 을리포 문인들이 주로 사용했다.가장 주목할 만한 예는 조르주 페렉의 소설 Life a User's Manual의 장 순서를 정하는 10×10 기사 투어이다.

Viswanathan Anand와 Veselin Topalov의 2010 World Chess Championship의 6번째 게임에서 Anand는 13개의 연속적인 기사 이동(두 기사 모두 사용했음에도 불구하고)을 하는 것을 보았다.온라인 해설자들은 Anand가 경기 중에 기사의 투어 문제를 해결하려고 한다고 조롱했다.

존재.

반지름 대칭으로 닫힌 기사 투어

Schwenk는[9] m n n이 있는 모든 m × n 보드에 대해 다음 세 가지 조건 중 하나 이상이 충족되지 않는 한 비공개 기사 투어가 항상 가능하다는 것을 증명했다.

  1. m과 n은 둘 다 홀수입니다.
  2. m = 1, 2, 또는 4
  3. m = 3 n = 4, 6, 또는 8.

Cull 등 Conrad 등은 작은 치수가 최소 5인 직사각형 보드에는 (아마도 열린) 기사 [4][10]투어가 있다는 것을 증명했다.

투어의 수

8 × 8 보드에는 정확히 26,534,728,821,064개의 유도 클로즈드 투어가 있다(즉, 같은 경로를 따라 반대 방향으로 이동하는 두 개의 투어는 회전[11][12][13]반사처럼 별도로 계산된다).모든 투어는 역추적이 가능하기 때문에 무방향 폐쇄 투어의 수는 이 수의 절반입니다.6×6 [14]보드에는 9,862개의 무방향 비공개 투어가 있습니다.

n 다이렉트 투어 수(개방 및 폐쇄)
n×n 보드상에서
(OEIS의 시퀀스 A165134)
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

컴퓨터로 둘러보기 찾기

컴퓨터로 주어진 보드에서 기사 투어를 찾는 방법에는 여러 가지가 있습니다.이러한 방법 중 일부는 알고리즘이고 다른 일부는 휴리스틱입니다.

브루트포스 알고리즘

기사의 투어에 대한 무리한 검색은 가장 작은 [15]보드를 제외한 모든 보드에서는 비현실적이다.예를 들어, 8×8 [16]보드에는 약 4×10개의51 가능한 이동 시퀀스가 있으며, 이러한 대규모 세트에서 작업을 수행하는 것은 최신 컴퓨터(또는 컴퓨터 네트워크)의 용량을 훨씬 초과합니다.그러나 이 숫자의 크기는 "인간의 통찰력과 창의력을 사용하여..." 큰 [15]어려움 없이 해결할 수 있는 문제의 어려움을 나타내지 않는다.

분할 및 정복 알고리즘

보드를 작은 조각으로 분할하여 각 조각에 둘러보고 패치를 붙이면 대부분의 직사각형 보드에 선형 시간, 즉 [10][17]보드의 정사각형 수에 비례하는 시간 에 둘러볼 수 있습니다.

워너스도르프의 법칙

abcdefgh
8
Chessboard480.svg
a6 three
c6 seven
d5 seven
b4 white knight
d3 seven
a2 two
c2 five
8
77
66
55
44
33
22
11
abcdefgh
Warnsdorff의 규칙을 그래픽으로 표현한 것입니다.각 사각형에는 기사가 해당 사각형에서 수행할 수 있는 이동 수를 나타내는 정수가 포함됩니다.이 경우 규칙은 정수가 가장 작은 정사각형, 즉 2로 이동하도록 지시합니다.
Warnsdorff의 규칙을 사용하여 만든 매우 큰(130×130) 정사각형 오픈 기사 투어

Warnsdorff의 규칙은 한 기사의 투어를 찾기 위한 휴리스틱이다.기사는 항상 기사가 가장 적게 전진하는 광장으로 이동하도록 이동한다.각 후보 사각형에 대한 전진 이동 수를 계산할 때 이미 방문한 사각형에 다시 방문한 이동 수는 카운트되지 않습니다.앞으로 나아가는 수가 같은 두 가지 이상의 선택지를 가질 수 있다; 그러한 관계를 끊는 방법에는 폴이[18] 고안한 것과 다람쥐와 컬이 [19]고안한 것을 포함해 다양한 방법이 있다.

이 규칙은 일반적으로 모든 그래프에 적용될 수도 있습니다.그래프 이론의 관점에서 각 이동은 인접한 정점으로 [20]최소도로 이루어진다.해밀턴 경로 문제는 일반적으로 NP-hard이지만 실제로 발생하는 많은 그래프에서 이 발견적 접근법은 선형 [18]시간 에 해답을 성공적으로 찾을 수 있다.기사의 투어는 정말 특별한 [21]경우야.

휴리스틱은 1823년 [21]H. C. von Warnsdorff에 의해 "Des Röselsprungs einfachste und algemeinste Lösung"에서 처음 기술되었다.

Warnsdorff의 규칙을 사용하여 어떤 출발 위치에서든 기사의 여행을 찾아주는 컴퓨터 프로그램은 Gordon Horsington에 의해 쓰여졌고 1984년 Century/Acorn User Book of Computer [22]Puzzes라는 에 출판되었다.

뉴럴 네트워크 솔루션

뉴럴 네트워크에 의해 해결된 24×24 보드상의 기사 투어 클로즈드

기사의 투어 문제도 뉴럴 네트워크 [23]구현으로 해결됩니다.네트워크는 모든 법률 기사의 움직임이 뉴런에 의해 표현되도록 설정되며, 각 뉴런은 무작위로 "활동적" 또는 "비활동적"으로 초기화됩니다(1 또는 0의 출력). 1은 뉴런이 해결책의 일부임을 암시합니다.각 뉴런은 또한 0으로 초기화된 상태 함수(아래 설명)를 가지고 있습니다.

네트워크가 실행되도록 허용되면, 각 뉴런은 다음 전환 규칙에 따라 인접 뉴런의 상태와 출력(정확히 기사 한 명의 이동)을 기반으로 상태와 출력을 변경할 수 있습니다.

서 tt)는 이산적인 시간 간격을 j i i제곱 j(\ ( j i V 출력입니다. j{ j ( i ,j) { ( N { , j ) 에는 뉴런의 이웃집합입니다.

다른 경우가 있을 수 있지만 네트워크는 최종적으로 수렴해야 합니다.이것은 시간에서 t+ t 가 바뀌는 뉴런이 없을 때 발생합니다.네트워크가 수렴되면 네트워크는 기사 투어를 인코딩하거나 같은 보드 내에서 여러 개의 독립된 회선을 인코딩합니다.

「 」를 참조해 주세요.

메모들

  1. ^ 브라운, 알프레드 제임스(2017).'Knight's Tours and Zeta Functions'(PDF).산호세 주립 대학교, 페이지 3. 2019-04-13 회수.
  2. ^ Hooper, David; Whyld, Kenneth (1996) [First pub. 1992]. "knight's tour". The Oxford Companion to Chess (2nd ed.). Oxford University Press. p. 204. ISBN 0-19-280049-3.
  3. ^ Deitel, H. M.; Deitel, P. J. (2003). Java How To Program Fifth Edition (5th ed.). Prentice Hall. pp. 326–328. ISBN 978-0131016217.
  4. ^ a b Conrad, A.; Hindrichs, T.; Morsy, H. & Wegener, I. (1994). "Solution of the Knight's Hamiltonian Path Problem on Chessboards". Discrete Applied Mathematics. 50 (2): 125–134. doi:10.1016/0166-218X(92)00170-Q.
  5. ^ Satyadev, Chaudhary. Kavyalankara of Rudrata (Sanskrit text, with Hindi translation);. Delhitraversal: Parimal Sanskrit Series No. 30.
  6. ^ "Indian Institute of Information Technology, Bangalore". www.iiitb.ac.in. Retrieved 2019-10-11.
  7. ^ Bridge-india (2011-08-05). "Bridge-India: Paduka Sahasram by Vedanta Desika". Bridge-India. Retrieved 2019-10-16.
  8. ^ 머레이의 체스 역사
  9. ^ Allen J. Schwenk (1991). "Which Rectangular Chessboards Have a Knight's Tour?" (PDF). Mathematics Magazine: 325–332. Archived from the original (PDF) on 2019-05-26.
  10. ^ a b Cull, P.; De Curtins, J. (1978). "Knight's Tour Revisited" (PDF). Fibonacci Quarterly. 16: 276–285.
  11. ^ Martin Loebbing; Ingo Wegener (1996). "The Number of Knight's Tours Equals 33,439,123,484,294 — Counting with Binary Decision Diagrams". The Electronic Journal of Combinatorics. 3 (1): R5. doi:10.37236/1229. 비고:저자들은 나중에 발표된 숫자가 틀렸다는 것을 인정했다.McKay의 보고서에 따르면, 정확한 숫자는 13,267,364,410,532이고 이 숫자는 Wegener의 2000년 책에서 반복된다.
  12. ^ Brendan McKay (1997). "Knight's Tours on an 8 × 8 Chessboard". Technical Report TR-CS-97-03. Department of Computer Science, Australian National University. Archived from the original on 2013-09-28. Retrieved 2013-09-22.
  13. ^ Wegener, I. (2000). Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics. ISBN 978-0-89871-458-6.
  14. ^ Weisstein, Eric W. "Knight Graph". MathWorld.
  15. ^ a b Simon, Dan (2013), Evolutionary Optimization Algorithms, John Wiley & Sons, pp. 449–450, ISBN 9781118659502, The knight's tour problem is a classic combinatorial optimization problem. ... The cardinality Nx of x (the size of the search space) is over 3.3×1013 (Löbbing and Wegener, 1995). We would not want to try to solve this problem using brute force, but by using human insight and ingenuity we can solve the knight's tour without much difficulty. We see that the cardinality of a combinatorial optimization problem is not necessarily indicative of its difficulty.
  16. ^ "Enumerating the Knight's Tour".[데드링크]
  17. ^ Parberry, Ian (1997). "An Efficient Algorithm for the Knight's Tour Problem" (PDF). Discrete Applied Mathematics. 73 (3): 251–260. doi:10.1016/S0166-218X(96)00010-8.
  18. ^ a b Pohl, Ira (July 1967). "A method for finding Hamilton paths and Knight's tours". Communications of the ACM. 10 (7): 446–449. CiteSeerX 10.1.1.412.8410. doi:10.1145/363427.363463.
  19. ^ Squirrel, Douglas; Cull, P. (1996). "A Warnsdorff-Rule Algorithm for Knight's Tours on Square Boards" (PDF). Retrieved 2011-08-21.
  20. ^ Van Horn, Gijs; Olij, Richard; Sleegers, Joeri; Van den Berg, Daan (2018). A Predictive Data Analytic for the Hardness of Hamiltonian Cycle Problem Instances (PDF). DATA ANALYTICS 2018: The Seventh International Conference on Data Analytics. Athens, greece: XPS. pp. 91–96. ISBN 978-1-61208-681-1. Retrieved 2018-11-27.[영구 데드링크]
  21. ^ a b Alwan, Karla; Waters, K. (1992). Finding Re-entrant Knight's Tours on N-by-M Boards. ACM Southeast Regional Conference. New York, New York: ACM. pp. 377–382. doi:10.1145/503720.503806.
  22. ^ Dally, Simon, ed. (1984). Century/Acorn User Book of Computer Puzzles. ISBN 978-0712605410.
  23. ^ Y. Takefuji, K. C. Lee. "기사 투어 문제용 신경 네트워크 컴퓨팅"뉴로컴퓨팅, 4(5): 249~254, 1992.

외부 링크