체스 기사의 움직임 만 사용하여 타일 하나에서 다른 타일로 이동하는 간단한 알고리즘

Question

체스에서 기사의 움직임 만 사용하여 두 지점 사이를 빠르게 갈 수있는 방법을 찾고자하는 문제가 있습니다. 처음 생각한 것은 A* 알고리즘이나 Dijkstra's 알고리즘이었습니다. 나이트 동작 만 사용하는 방법을 모르겠습니다. 더 나은 알고리즘이나 나를 도울 수있는 몇 가지 팁을 제안 해 주시면 감사하겠습니다. 고맙습니다. 당신이 시작되는 소스 광장, 그리고 당신이 퍼즐을 해결하기 위해 땅을 필요로하는 곳에있는 대상 광장 :

는 두 개의 매개 변수에 걸리는 대답 (SRC, 이명 령)라는 함수를 작성합니다. 이 함수는 체스 기사의 움직임을 사용하여 소스 사각형에서 대상 사각형으로 이동하는 데 필요한 최소 이동 수를 나타내는 정수를 반환해야합니다 (즉, 모든 방향에서 두 개의 사각형과 그 방향에 수직 인 한 개의 사각형이 바로 뒤에옵니다) , 또는 그 반대로, "L"모양). 모두 원본 및 대상 사각형은 0에서 63까지의 정수가 될 것이며, 아래의 예 체스 판처럼 번호가 매겨집니다 : 주어진 노드의 모든 이웃을 찾을 필요가 알고리즘에 대한

 
------------------------- 
| 0| 1| 2| 3| 4| 5| 6| 7| 
------------------------- 
| 8| 9|10|11|12|13|14|15| 
------------------------- 
|16|17|18|19|20|21|22|23| 
------------------------- 
|24|25|26|27|28|29|30|31| 
------------------------- 
|32|33|34|35|36|37|38|39| 
------------------------- 
|40|41|42|43|44|45|46|47| 
------------------------- 
|48|49|50|51|52|53|54|55| 
------------------------- 
|56|57|58|59|60|61|62|63| 
------------------------- 

Answer 1

는 다음과 같은 방법으로 문제를 접근.

2 단계 : 하나의 사각형에서 다른 사각형으로 기사가 이동하는 경우 정확하게 꼭지점 사이에 모서리를 배치하십시오.

3 단계 : Dijkstra의 알고리즘을 적용하십시오. Dijkstra 알고리즘은 두 정점 (사각형) 사이의 경로 길이를 찾는 알고리즘입니다.

Answer 2

. divmod https://docs.python.org/3/library/functions.html#divmod을 사용하면 0-63 표기법을 행과 열로 쉽게 변환 할 수 있으므로 기사를 쉽게 계산할 수 있습니다.

Answer 3

이 문제의 경우 너비 우선 검색만으로 충분합니다 (Dijkstra 및 BFS는 unweighted 그래프에 대해서도 같은 방법). 체스 나이트의 이동 만 사용되도록하려면 적절한 방법으로 이동을 정의해야합니다.

체스 나이트는 두 개의 정사각형을 어떤 방향으로 움직여야하고, 그 다음에는 그 정사각형에 수직 한 한 정사각형을 움직이는 것에 주목하십시오. 즉, 두 개의 정사각형을 오른쪽에서 왼쪽으로 이동하거나 한 정사각형을 위아래로 움직이거나 두 개의 정사각형을 위 또는 아래로 이동 한 다음 한 개의 정사각형을 왼쪽 또는 오른쪽으로 이동할 수 있음을 의미합니다.

셀을 0-63 대신 행 (0-7) 및 열 (0-7)로 식별하면 계산이 훨씬 쉬워집니다.이 작업은 셀 인덱스를 8로 나누고 행과 열 인덱스로 몫과 나머지를 반환합니다. 따라서 기사의 위치가 (x, y)이면 그 다음으로 가능한 위치는 (x - 2, y - 1), (x - 2, y + 1), (x + 2, y - 1), (x + 2, y + 1), (x - 1, y - 2), (x - 1, y + 2), (x + 1, y - 2), (x + 1, y + 2) 일 수 있습니다. 이 8 개의 모든 셀이 그리드 내부에 있지 않을 수 있으므로 보드 밖으로 떨어지는 위치는 버려야합니다.

단계 1 : 체스 보드의 각 사각형은 버텍스 그래프를 구축

Answer 4

User_Targaryen의 답이 사용자의 질문에 직접 답하기 때문에 가장 좋지만, 컴퓨팅의 목표가 가장 짧은 시간 내에 답변을 전달하는 것이라면 대수적 솔루션을 추천합니다.

알고리즘을 줄이려면 x, y 및 xy 축에 대한 반사를 사용하여 x> = y 인 경우에만 양수 (x, y)를 고려하고 시작 이동을 좌표 (0 , 0). 이것은 가능한 방향의 8 분의 1입니다.

해결책을 발견하는 힌트는 그래프 용지 또는 Dijkstra의 알고리즘을 사용하여 첫 번째 8 분주의 모든 점에 도달하여 최대 5 개 이동을 제한하고이를 격자로 표시하는 것입니다. 그리드의 각 셀에는 최소 이동 수를 나타내는 숫자가 레이블되어야합니다.

귀하의 질문을 확대하고 싶으신 경우 알려주십시오. 추가 정보가 필요하십니까?