체스 판에서 기사의 최단 경로
나는 다가오는 프로그래밍 대회를 위해 연습을 해왔고 완전히 어리둥절한 질문을 우연히 발견했습니다. 하지만 결코 떠오르지 않는다는 손가락을 꼬집기보다는 지금 배워야 할 개념 인 것 같습니다.
기본적으로 체스 판에있는 기사를 다룹니다. 시작 위치와 끝 위치의 두 가지 입력이 제공됩니다. 목표는 기사가 목표 위치에 도달하기 위해 취할 수있는 최단 경로를 계산하고 인쇄하는 것입니다.
나는 최단 경로 같은 것을 다루지 않았고 어디서부터 시작해야할지조차 모른다. 이 문제를 해결하기 위해 어떤 논리를 사용합니까?
추신 : 만약 관련성이 있다면, 그들은 광장의 중심이 다음과 같을 때 기사가 만들 수있는 (잠재적으로) 8 번의 동작으로 형성된 사각형의 네 모서리로 이동할 수 있도록 허용하여 기사의 정상적인 동작을 보완하기를 원합니다. 기사의 위치.
사용 가능한 모든 이동이 연결되고 (값 = 1) 사용할 수없는 이동이 연결 해제 된 (값 = 0) 그래프가 있습니다. 희소 행렬은 다음과 같습니다.
(a1,b3)=1,
(a1,c2)=1,
.....
그래프에서 두 점의 최단 경로는 http://en.wikipedia.org/wiki/Dijkstra's_algorithm을 사용하여 찾을 수 있습니다 .
wikipedia-page의 의사 코드 :
function Dijkstra(Graph, source):
for each vertex v in Graph: // Initializations
dist[v] := infinity // Unknown distance function from source to v
previous[v] := undefined // Previous node in optimal path from source
dist[source] := 0 // Distance from source to source
Q := the set of all nodes in Graph
// All nodes in the graph are unoptimized - thus are in Q
while Q is not empty: // The main loop
u := vertex in Q with smallest dist[]
if dist[u] = infinity:
break // all remaining vertices are inaccessible from source
remove u from Q
for each neighbor v of u: // where v has not yet been removed from Q.
alt := dist[u] + dist_between(u, v)
if alt < dist[v]: // Relax (u,v,a)
dist[v] := alt
previous[v] := u
return dist[]
편집하다:
- 바보처럼 http://en.wikipedia.org/wiki/A*_algorithm을 사용하는 것이 더 빠를 수 있다고 말했습니다 .
- 가장 빠른 방법은 모든 거리를 미리 계산하여 8x8 풀 매트릭스에 저장하는 것입니다. 음, 나는 그것을 속임수라고 부르고 문제가 작기 때문에 작동합니다. 그러나 때로는 대회가 프로그램 실행 속도를 확인합니다.
- 요점은 프로그래밍 대회를 준비하고 있다면 Dijkstra를 포함한 일반적인 알고리즘을 알아야한다는 것입니다. 좋은 시작점은
Introduction to AlgorithmsISBN 0-262-03384-4를 읽는 것 입니다. 또는 wikipedia, http://en.wikipedia.org/wiki/List_of_algorithms를 사용해 볼 수 있습니다 .
편집 : 여기에 제시된 공식을 수정 한 simon의 대답을 참조 하십시오.
실제로 O (1) 공식이 있습니다.
이것은 내가 그것을 시각화하기 위해 만든 이미지입니다 (기사가 N 번째 이동 에서 도달 할 수있는 사각형은 같은 색으로 칠해져 있습니다).
여기서 패턴을 알 수 있습니까?
패턴을 볼 수 있지만 f( x , y )정사각형에서 정사각형 ( 0 , 0 )으로 이동하는 데 필요한 이동 횟수를 반환하는 함수를 찾기가 정말 어렵습니다.( x , y )
하지만 다음과 같은 경우에 작동하는 공식이 있습니다. 0 <= y <= x
int f( int x , int y )
{
int delta = x - y;
if( y > delta )
return 2 * ( ( y - delta ) / 3 ) + delta;
else
return delta - 2 * ( ( delta - y ) / 4 );
}
참고 :이 질문은 SACO 2007 Day 1 에 요청되었으며
솔루션은 여기에 있습니다.
여기에 올바른 O (1) 솔루션이 있지만, 기사가 체스 기사처럼 움직이며 무한 체스 판에서 움직이는 경우 :
https://jsfiddle.net/graemian/5qgvr1ba/11/
이것을 찾는 열쇠는 보드를 그릴 때 나타나는 패턴을 알아 차리는 것입니다. 아래 다이어그램에서 사각형의 숫자는 해당 사각형에 도달하는 데 필요한 최소 이동 횟수입니다 (폭 우선 검색을 사용하여 찾을 수 있음).
솔루션은 축과 대각선에 대칭이기 때문에 x> = 0 및 y> = x 케이스 만 그렸습니다.
왼쪽 하단 블록은 시작 위치이며 블록의 숫자는 해당 블록에 도달하기위한 최소 이동 횟수를 나타냅니다.
주목해야 할 3 가지 패턴이 있습니다.
- 증가하는 파란색 세로 그룹 4 개
- "기본"빨간색 대각선 (백 슬래시처럼 왼쪽 상단에서 오른쪽 하단으로 실행)
- "보조"녹색 대각선 (빨간색과 같은 방향)
(두 대각선 세트가 왼쪽 상단에서 오른쪽 하단으로 표시되는지 확인합니다. 이동 횟수가 일정합니다. 왼쪽 하단 상단 오른쪽 대각선은 훨씬 더 복잡합니다.)
각각에 대한 공식을 유도 할 수 있습니다. 노란색 블록은 특별한 경우입니다. 따라서 솔루션은 다음과 같습니다.
function getMoveCountO1(x, y) {
var newXY = simplifyBySymmetry(x, y);
x = newXY.x;
y = newXY.y;
var specialMoveCount = getSpecialCaseMoveCount(x ,y);
if (specialMoveCount !== undefined)
return specialMoveCount;
else if (isVerticalCase(x, y))
return getVerticalCaseMoveCount(x ,y);
else if (isPrimaryDiagonalCase(x, y))
return getPrimaryDiagonalCaseMoveCount(x ,y);
else if (isSecondaryDiagonalCase(x, y))
return getSecondaryDiagonalCaseMoveCount(x ,y);
}
가장 어려운 것은 수직 그룹입니다.
function isVerticalCase(x, y) {
return y >= 2 * x;
}
function getVerticalCaseMoveCount(x, y) {
var normalizedHeight = getNormalizedHeightForVerticalGroupCase(x, y);
var groupIndex = Math.floor( normalizedHeight / 4);
var groupStartMoveCount = groupIndex * 2 + x;
return groupStartMoveCount + getIndexInVerticalGroup(x, y);
}
function getIndexInVerticalGroup(x, y) {
return getNormalizedHeightForVerticalGroupCase(x, y) % 4;
}
function getYOffsetForVerticalGroupCase(x) {
return x * 2;
}
function getNormalizedHeightForVerticalGroupCase(x, y) {
return y - getYOffsetForVerticalGroupCase(x);
}
다른 경우는 바이올린을 참조하십시오.
내가 놓친 더 단순하거나 더 우아한 패턴이 있을까요? 그렇다면 나는 그들을보고 싶다. 특히 파란색 세로 케이스에서 대각선 패턴을 발견했지만 아직 살펴 보지 않았습니다. 그럼에도 불구하고이 솔루션은 여전히 O (1) 제약 조건을 충족합니다.
최근에 만난 매우 흥미로운 문제입니다. 몇 가지 솔루션을 찾은 후 SACO 2007 Day 1 솔루션O(1) time and space complexity 에 제공된 분석 공식 ( ) 을 복구하려고했습니다 .
먼저 수식을 수정하는 데 도움이 된 매우 멋진 시각화 에 대해 Graeme Pyle 에 감사드립니다 .
어떤 이유로 (단순화 또는 아름다움 또는 실수 로 인한 것일 수 있음) 운영자 로 minus로그인하여 floor잘못된 공식을 얻었습니다 floor(-a) != -floor(a) for any a.
다음은 올바른 분석 공식입니다.
var delta = x-y;
if (y > delta) {
return delta - 2*Math.floor((delta-y)/3);
} else {
return delta - 2*Math.floor((delta-y)/4);
}
이 공식은 (1,0) 및 (2,2) 코너 케이스를 제외하고 모든 (x, y) 쌍 (축 및 대각선 대칭을 적용한 후)에 대해 작동하며 패턴을 충족하지 않고 다음 스 니펫에서 하드 코딩됩니다.
function distance(x,y){
// axes symmetry
x = Math.abs(x);
y = Math.abs(y);
// diagonal symmetry
if (x < y) {
t = x;x = y; y = t;
}
// 2 corner cases
if(x==1 && y == 0){
return 3;
}
if(x==2 && y == 2){
return 4;
}
// main formula
var delta = x-y;
if(y>delta){
return delta - 2*Math.floor((delta-y)/3);
}
else{
return delta - 2*Math.floor((delta-y)/4);
}
}
$body = $("body");
var html = "";
for (var y = 20; y >= 0; y--){
html += '<tr>';
for (var x = 0; x <= 20; x++){
html += '<td style="width:20px; border: 1px solid #cecece" id="'+x+'_'+y+'">'+distance(x,y)+'</td>';
}
html += '</tr>';
}
html = '<table>'+html+'</table>';
$body.append(html);<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>참고 : 설명 용으로 만 사용 된 jQuery는 코드를 참조하십시오 distance.
예, Dijkstra와 BFS가 답을 얻을 수 있지만,이 문제의 체스 컨텍스트는 특히 무한 체스 판에서 일반적인 최단 경로 알고리즘보다 훨씬 빠른 솔루션을 산출 할 수있는 지식을 제공한다고 생각합니다.
간단하게 체스 판을 (x, y) 평면으로 설명하겠습니다. 목표는 후보 단계 (+ -1, + -2), (+ -2, + -1) 및 (+ -2) 만 사용하여 (x0, y0)에서 (x1, y1)까지의 최단 경로를 찾는 것입니다. , + -2), 질문의 PS에 설명 된대로
다음은 새로운 관찰입니다 : 모서리가있는 사각형 그리기 (x-4, y-4), (x-4, y + 4), (x + 4, y-4), (x + 4, y + 4) . 이 세트 (S4라고 부름)는 32 점을 포함합니다. 이 32 개 지점에서 (x, y)까지의 최단 경로는 정확히 두 번 이동 해야 합니다 .
집합 S3 (유사하게 정의 됨)의 24 개 지점 중 하나에서 (x, y)까지의 최단 경로 는 최소 두 번의 이동이 필요 합니다 .
따라서 | x1-x0 |> 4 또는 | y1-y0 |> 4 인 경우 (x0, y0)에서 (x1, y1)까지의 최단 경로는 (x0, y0)에서 (x0, y0)까지의 최단 경로보다 정확히 2 번 더 이동합니다. S4. 그리고 후자의 문제는 간단한 반복으로 신속하게 해결할 수 있습니다.
N = max (| x1-x0 |, | y1-y0 |)라고합시다. N> = 4이면 (x0, y0)에서 (x1, y1)까지의 최단 경로에 ceil (N / 2) 단계가 있습니다.
위의 O (1) 답변 [ https://stackoverflow.com/a/8778592/4288232 by Mustafa Serdar Şanlı]이 실제로 작동하지 않습니다. ((1,1) 또는 (3,2) 또는 (4,4)를 확인하고 (1,0) 또는 (2,2)의 명백한 가장자리 사례를 제외)).
다음은 훨씬 더 추악한 솔루션 (파이썬)으로 작동합니다 ( "테스트"가 추가됨).
def solve(x,y):
x = abs(x)
y = abs(y)
if y > x:
temp=y
y=x
x=temp
if (x==2 and y==2):
return 4
if (x==1 and y==0):
return 3
if(y == 0 or float(y) / float(x) <= 0.5):
xClass = x % 4
if (xClass == 0):
initX = x/2
elif(xClass == 1):
initX = 1 + (x/2)
elif(xClass == 2):
initX = 1 + (x/2)
else:
initX = 1 + ((x+1)/2)
if (xClass > 1):
return initX - (y%2)
else:
return initX + (y%2)
else:
diagonal = x - ((x-y)/2)
if((x-y)%2 == 0):
if (diagonal % 3 == 0):
return (diagonal/3)*2
if (diagonal % 3 == 1):
return ((diagonal/3)*2)+2
else:
return ((diagonal/3)*2)+2
else:
return ((diagonal/3)*2)+1
def test():
real=[
[0,3,2,3,2,3,4,5,4,5,6,7,6,7],
[3,2,1,2,3,4,3,4,5,6,5,6,7,8],
[2,1,4,3,2,3,4,5,4,5,6,7,6,7],
[3,2,3,2,3,4,3,4,5,6,5,6,7,8],
[2,3,2,3,4,3,4,5,4,5,6,7,6,7],
[3,4,3,4,3,4,5,4,5,6,5,6,7,8],
[4,3,4,3,4,5,4,5,6,5,6,7,6,7],
[5,4,5,4,5,4,5,6,5,6,7,6,7,8],
[4,5,4,5,4,5,6,5,6,7,6,7,8,7],
[5,6,5,6,5,6,5,6,7,6,7,8,7,8],
[6,5,6,5,6,5,6,7,6,7,8,7,8,9],
[7,6,7,6,7,6,7,6,7,8,7,8,9,8]]
for x in range(12):
for y in range(12):
res = solve(x,y)
if res!= real[x][y]:
print (x, y), "failed, and returned", res, "rather than", real[x][y]
else:
print (x, y), "worked. Cool!"
test()
당신이해야 할 일은 기사의 가능한 움직임을 그래프로 생각하는 것인데, 보드의 모든 위치는 노드이고 가능한 이동은 다른 위치로 에지로 간주됩니다. 모든 모서리가 동일한 가중치 또는 거리를 갖기 때문에 dijkstra의 알고리즘이 필요하지 않습니다 (모두 수행하기 쉽고 짧습니다). 시작 지점에서 끝 위치에 도달 할 때까지 BFS 검색을 수행 할 수 있습니다.
Python의 첫 번째 원칙의 솔루션
나는 Codility 테스트에서이 문제를 처음 접했습니다. 그들은 그것을 해결하는 데 30 분을주었습니다.이 결과를 얻는 데는 그보다 훨씬 더 오래 걸렸습니다! 문제는 기사가 합법적 인 기사의 이동 만 사용하여 0,0에서 x, y로 이동하는 데 얼마나 많은 이동이 필요한지였습니다. x와 y는 다소 제한이 없었습니다 (따라서 여기서 간단한 8x8 체스 판에 대해 이야기하지 않습니다).
그들은 O (1) 솔루션을 원했습니다. 저는 프로그램이 문제를 명확하게 해결하는 솔루션을 원했습니다 (즉, Graeme의 패턴보다 더 분명하게 옳은 것을 원했습니다. 패턴은 당신이 보지 않는 곳을 분해하는 습관을 가지고 있습니다), 저는 정말로 의존 할 필요가 없었습니다. Mustafa의 솔루션에서와 같이 논증되지 않는 공식
그래서 여기 내 솔루션이 있습니다. 다른 사람들과 마찬가지로 솔루션이 축과 대각선에 대해 대칭임을 주목하여 시작하십시오. 따라서 0> = y> = x에 대해서만 풀면됩니다. 설명 (및 코드)의 단순함을 위해 문제를 뒤집을 것입니다. 기사는 x, y에서 시작하여 0,0을 목표로합니다.
문제를 원점 근처로 축소한다고 가정 해 봅시다. 우리는 'vicinty'가 실제로 의미하는 바를 곧 알게 될 것이지만, 지금은 치트 시트에 몇 가지 해결책을 적어 보겠습니다 (왼쪽 하단에서 시작).
2 1 4 3
3 2 1 2
0 3 2 3
따라서 그리드에 x, y가 주어지면 원점으로 이동 한 횟수를 읽을 수 있습니다.
그리드 밖에서 시작했다면 다시 돌아 가야합니다. y = x / 2로 표시되는 선인 '중간 선'을 소개합니다. 해당 라인의 x, y에있는 모든 기사는 일련의 8시 동작 (즉 : (-2, -1) 동작)을 사용하여 치트 시트로 돌아갈 수 있습니다. x, y가 정중선 위에 있으면 8시와 7시 이동의 연속이 필요하고 정중선 아래에 있으면 8시와 10시의 연속이 필요합니다. '시계가 움직인다. 여기서 주목해야 할 두 가지 사항 :
- 이러한 시퀀스는 가장 짧은 경로입니다. (증명하고 싶습니까, 아니면 명백합니까?)
- 우리는 그러한 움직임의 수에만 관심이 있습니다. 어떤 순서로든 무브를 믹스 앤 매치 할 수 있습니다.
따라서 중간 선 위의 움직임을 살펴 보겠습니다. 우리가 주장하는 것은 다음과 같습니다.
(dx; dy) = (2,1; 1,2) (n8; n7) (수학 조판이없는 행렬 표기법-열 벡터 (dx; dy)는 열 벡터 (n8; n7)를 곱한 정사각형 행렬과 같습니다. 8시 이동 수 및 7시 이동 수) 및 유사하게;
(dx; dy) = (2,2; 1, -1) (n8; n10)
나는 dx, dy가 대략 (x, y)이므로 (x-dx, y-dy)는 원점 근처에있을 것입니다 ( '근처'가 무엇이든간에).
이 용어를 계산하는 코드의 두 줄이 이에 대한 해결책이지만 몇 가지 유용한 속성을 갖도록 선택되었습니다.
- 중간 선 위 공식은 (x, y)를 (0,0), (1,1) 또는 (2,2) 중 하나로 이동합니다.
- 중간 선 아래 수식은 (x, y)를 (0,0), (1,0), (2,0) 또는 (1,1) 중 하나로 이동합니다.
(이것들의 증거를 원하십니까?) 따라서 Knight의 거리는 n7, n8, n10 및 치트 시트 [x-dx, y-dy]의 합이 될 것이며, 치트 시트는 다음과 같이 축소됩니다.
. . 4
. 2 .
0 3 2
자, 이것은 이야기의 끝이 아닙니다. 맨 아래 줄에있는 3을보십시오. 이에 도달 할 수있는 유일한 방법은 다음 중 하나입니다.
- 우리는 거기서 시작했거나
- 우리는 8시와 10시 이동의 순서로 그곳으로 이동했습니다. 그러나 마지막 움직임이 8 시라면 (어떤 순서로든 움직일 수 있기 때문에 자격이 있음), 거리가 실제로 2 인 (3,1)을 통과했을 것입니다. 원본 치트 시트에서 참조). 그래서 우리가해야 할 일은 8시 방향으로 한 번 뒤로 돌아가서 총 두 번의 동작을 줄이는 것입니다.
오른쪽 상단의 4와 유사한 최적화가 있습니다. 거기에서 시작하는 것 외에도 (4,3)에서 8시 방향으로 이동하는 것이 유일한 방법입니다. 그것은 치트 시트에 있지 않지만, 만약 그것이 있다면 그 거리는 3이 될 것입니다. 왜냐하면 우리는 7시를 (3,1)에 대신 할 수 있었기 때문입니다. 거리는 2입니다. 그래서 우리는 하나를 역 추적해야합니다. 8시 방향으로 이동 한 다음 7시 방향으로 이동합니다.
따라서 치트 시트에 숫자를 하나 더 추가해야합니다.
. . 4
. 2 . 2
0 3 2
(참고 : (0,1) 및 (0,2)에서 역 추적 최적화의 전체 부하가 있지만 솔버가 우리를 절대로 데려 가지 않을 것이기 때문에 걱정할 필요가 없습니다.)
그래서 여기에 이것을 평가하는 파이썬 코드가 있습니다 :
def knightDistance (x, y):
# normalise the coordinates
x, y = abs(x), abs(y)
if (x<y): x, y = y, x
# now 0 <= y <= x
# n8 means (-2,-1) (8 o'clock), n7 means (-1,-2) (7 o'clock), n10 means (-2,+1) (10 o'clock)
if (x>2*y):
# we're below the midline. Using 8- & 10-o'clock moves
n7, n8, n10 = 0, (x + 2*y)//4, (x - 2*y + 1)//4
else:
# we're above the midline. Using 7- and 8-o'clock moves
n7, n8, n10 = (2*y - x)//3, (2*x - y)//3, 0
x -= 2*n8 + n7 + 2*n10
y -= n8 + 2*n7 - n10
# now 0<=x<=2, and y <= x. Also (x,y) != (2,1)
# Try to optimise the paths.
if (x, y)==(1, 0): # hit the 3. Did we need to?
if (n8>0): # could have passed through the 2 at 3,1. Back-up
x, y = 3, 1; n8-=1;
if (x, y)==(2, 2): # hit the 4. Did we need to?
if (n8>0): # could have passed through a 3 at 4,3. Back-up, and take 7 o'clock to 2 at 3,1
x, y = 3, 1; n8-=1; n7+=1
# Almost there. Now look up the final leg
cheatsheet = [[0, 3, 2], [2, None, 2], [4]]
return n7 + n8 + n10 + cheatsheet [y][x-y]
덧붙여서, 실제 경로를 알고 싶다면이 알고리즘도 제공합니다 : 그것은 단순히 n7 7시 움직임의 연속이고 그 뒤에 n8 8시 움직임, n10 10- 시 이동 및 치트 시트 (그 자체가 치트 시트에있을 수 있음)에 의해 지시되는 춤.
지금 : 이것이 옳다는 것을 증명하는 방법. 이 결과를 정답 표와 비교하는 것만으로는 충분하지 않습니다. 문제 자체는 제한이 없기 때문입니다. 그러나 우리는 기사의 제곱 s의 거리가 d라면 {m}이 s로부터의 합법적 인 이동의 집합이라면 기사의 거리 (s + m)는 d-1 또는 d + 1이어야한다고 말할 수 있습니다. 모든 m. (당신은 이것에 대한 증명이 필요합니까?) 또한, s가 원점이 아니라면 거리가 d-1 인 그러한 사각형이 적어도 하나 있어야합니다. 따라서 우리는이 속성이 모든 사각형에 대해 유지됨을 보여줌으로써 정확성을 증명할 수 있습니다. 그러므로:
def validate (n):
def isSquareReasonable (x, y):
d, downhills = knightDistance (x, y), 0
moves = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
for dx, dy in moves:
dd = knightDistance (x+dx, y+dy)
if (dd == d+1): pass
elif (dd== d-1): downhills += 1
else: return False;
return (downhills>0) or (d==0)
for x in range (0, n+1):
for y in range (0, n+1):
if not isSquareReasonable (x, y): raise RuntimeError ("Validation failed")
또는 내리막에서 출발지까지의 경로를 추적하여 어느 한 사각형의 정확성을 증명할 수 있습니다. 먼저 s의 합리성을 확인한 다음 거리 (s + m) == d-1이되는 s + m을 선택합니다. 원점에 도달 할 때까지 반복합니다.
Howzat?
/*
This program takes two sets of cordinates on a 8*8 chessboard, representing the
starting and ending points of a knight's path.
The problem is to print the cordinates that the knight traverses in between, following
the shortest path it can take.
Normally this program is to be implemented using the Djikstra's algorithm(using graphs)
but can also be implemented using the array method.
NOTE:Between 2 points there may be more than one shortest path. This program prints
only one of them.
*/
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
int m1=0,m2=0;
/*
This array contains three columns and 37 rows:
The rows signify the possible coordinate differences.
The columns 1 and 2 contains the possible permutations of the row and column difference
between two positions on a chess board;
The column 3 contains the minimum number of steps involved in traversing the knight's
path with the given permutation*/
int arr[37][3]={{0,0,0},{0,1,3},{0,2,2},{0,3,3},{0,4,2},{0,5,3},{0,6,4},{0,7,5}, {1,1,2},{1,2,1},{1,3,2},{1,4,3},{1,5,4},{1,6,3},{1,7,4},{2,2,4},{2,3,3},{2,4,2},
{2,5,3},{2,6,3},{2,7,5},{3,3,2},{3,4,3},{3,5,4},{3,6,3},{3,7,4},{4,4,4},{4,5,3},{4,6,4},{4,7,5},{5,5,4},{5,6,5},{5,7,4},{6,6,5},{6,7,5},{7,7,6}};
void printMoves(int,int,int,int,int,int);
void futrLegalMove(int,int,int,int);
main()
{
printf("KNIGHT'S SHORTEST PATH ON A 8*8 CHESSBOARD :\n");
printf("------------------------------------------");
printf("\nThe chessboard may be treated as a 8*8 array here i.e. the (1,1) ");
printf("\non chessboard is to be referred as (0,0) here and same for (8,8) ");
printf("\nwhich is to be referred as (7,7) and likewise.\n");
int ix,iy,fx,fy;
printf("\nEnter the initial position of the knight :\n");
scanf("%d%d",&ix,&iy);
printf("\nEnter the final position to be reached :\n");
scanf("%d%d",&fx,&fy);
int px=ix,py=iy;
int temp;
int tx,ty;
printf("\nThe Knight's shortest path is given by :\n\n");
printf("(%d, %d)",ix,iy);
futrLegalMove(px,py,m1,m2);
printMoves(px,py,fx,fy,m1,m2);
getch();
}
/*
This method checkSteps() checks the minimum number of steps involved from current
position(a & b) to final position(c & d) by looking up in the array arr[][].
*/
int checkSteps(int a,int b,int c,int d)
{
int xdiff, ydiff;
int i, j;
if(c>a)
xdiff=c-a;
else
xdiff=a-c;
if(d>b)
ydiff=d-b;
else
ydiff=b-d;
for(i=0;i<37;i++)
{
if(((xdiff==arr[i][0])&&(ydiff==arr[i][1])) || ((xdiff==arr[i][1])&& (ydiff==arr[i] [0])))
{
j=arr[i][2];break;
}
}
return j;
}
/*
This method printMoves() prints all the moves involved.
*/
void printMoves(int px,int py, int fx, int fy,int a,int b)
{
int temp;
int tx,ty;
int t1,t2;
while(!((px==fx) && (py==fy)))
{
printf(" --> ");
temp=checkSteps(px+a,py+b,fx,fy);
tx=px+a;
ty=py+b;
if(!(a==2 && b==1))
{if((checkSteps(px+2,py+1,fx,fy)<temp) && checkMove(px+2,py+1))
{temp=checkSteps(px+2,py+1,fx,fy);
tx=px+2;ty=py+1;}}
if(!(a==2 && b==-1))
{if((checkSteps(px+2,py-1,fx,fy)<temp) && checkMove(px+2,py-1))
{temp=checkSteps(px+2,py-1,fx,fy);
tx=px+2;ty=py-1;}}
if(!(a==-2 && b==1))
{if((checkSteps(px-2,py+1,fx,fy)<temp) && checkMove(px-2,py+1))
{temp=checkSteps(px-2,py+1,fx,fy);
tx=px-2;ty=py+1;}}
if(!(a==-2 && b==-1))
{if((checkSteps(px-2,py-1,fx,fy)<temp) && checkMove(px-2,py-1))
{temp=checkSteps(px-2,py-1,fx,fy);
tx=px-2;ty=py-1;}}
if(!(a==1 && b==2))
{if((checkSteps(px+1,py+2,fx,fy)<temp) && checkMove(px+1,py+2))
{temp=checkSteps(px+1,py+2,fx,fy);
tx=px+1;ty=py+2;}}
if(!(a==1 && b==-2))
{if((checkSteps(px+1,py-2,fx,fy)<temp) && checkMove(px+1,py-2))
{temp=checkSteps(px+1,py-2,fx,fy);
tx=px+1;ty=py-2;}}
if(!(a==-1 && b==2))
{if((checkSteps(px-1,py+2,fx,fy)<temp) && checkMove(px-1,py+2))
{temp=checkSteps(px-1,py+2,fx,fy);
tx=px-1;ty=py+2;}}
if(!(a==-1 && b==-2))
{if((checkSteps(px-1,py-2,fx,fy)<temp) && checkMove(px-1,py-2))
{temp=checkSteps(px-1,py-2,fx,fy);
tx=px-1;ty=py-2;}}
t1=tx-px;//the step taken in the current move in the x direction.
t2=ty-py;//" " " " " " " " " " " " " " " " " " " " " y " " " " ".
px=tx;
py=ty;
printf("(%d, %d)",px,py);
futrLegalMove(px,py,t1,t2);
a=m1;
b=m2;
}
}
/*
The method checkMove() checks whether the move in consideration is beyond the scope of
board or not.
*/
int checkMove(int a, int b)
{
if(a>7 || b>7 || a<0 || b<0)
return 0;
else
return 1;
}
/*Out of the 8 possible moves, this function futrLegalMove() sets the valid move by
applying the following constraints
1. The next move should not be beyond the scope of the board.
2. The next move should not be the exact opposite of the previous move.
The 1st constraint is checked by sending all possible moves to the checkMove()
method;
The 2nd constraint is checked by passing as parameters(i.e. a and b) the steps of the
previous move and checking whether or not it is the exact opposite of the current move.
*/
void futrLegalMove(int px,int py,int a,int b)
{
if(checkMove(px+2,py+1) && (a!=-2 && b!=-1))
m1=2,m2=1;
else
{
if(checkMove(px+2,py-1)&& (a!=-2 && b!=1))
m1=2,m2=-1;
else
{
if(checkMove(px-2,py+1)&& (a!=2 && b!=-1))
m1=-2,m2=1;
else
{
if(checkMove(px-2,py-1)&& (a!=2 && b!=1))
m1=-2,m2=-1;
else
{
if(checkMove(px+1,py+2)&& (b!=-2 && a!=-1))
m2=2,m1=1;
else
{
if(checkMove(px+1,py-2)&& (a!=-1 && b!=2))
m2=-2,m1=1;
else
{
if(checkMove(px-1,py+2)&& (a!=1 && b!=-2))
m2=2,m1=-1;
else
{
if(checkMove(px-1,py-2)&& (a!=1 && b!=2))
m2=-2,m1=-1;
}}}}}}}
}
//End of Program.
저는 아직 그래프를 연구하지 않았습니다. 단순히 배열을 통해 구현하는 문제에 따라 이것 외에는 어떤 해결책도 도출 할 수 없었습니다. 나는 순위와 파일 (일반적인 체스 표기법)이 아니라 배열 인덱스로 위치를 취급했습니다. 참고로, 이것은 8 * 8 체스 판 전용입니다. 모든 개선 조언은 항상 환영합니다.
* 논리에 대한 이해를 위해서는 주석으로 충분해야합니다. 그러나 항상 요청할 수 있습니다.
* DEV-C ++ 4.9.9.2 컴파일러 (Bloodshed 소프트웨어)에서 확인되었습니다.
이것도 도움이 될 것 같아요 ..
NumWays(x,y)=1+min(NumWays(x+-2,y-+1),NumWays(x+-1,y+-2));
솔루션을 얻기 위해 동적 프로그래밍을 사용합니다.
추신 : 그래프의 노드와 에지를 선언하는 문제없이 BFS를 사용합니다.
다음은 Perl에서 구현 된이 특정 문제에 대한 해결책입니다. 가장 짧은 경로 중 하나가 표시됩니다. 경우에 따라 둘 이상이있을 수 있습니다.
위에서 설명한 알고리즘을 사용하지 않았지만 다른 솔루션과 비교하면 좋을 것입니다.
#!/usr/local/bin/perl -w
use strict;
my $from = [0,0];
my $to = [7,7];
my $f_from = flat($from);
my $f_to = flat($to);
my $max_x = 7;
my $max_y = 7;
my @moves = ([-1,2],[1,2],[2,1],[2,-1],[1,-2],[-1,-2],[-2,-1],[-2,1]);
my %squares = ();
my $i = 0;
my $min = -1;
my @s = ( $from );
while ( @s ) {
my @n = ();
$i++;
foreach my $s ( @s ) {
unless ( $squares{ flat($s) } ) {
my @m = moves( $s );
push @n, @m;
$squares{ flat($s) } = { i=>$i, n=>{ map {flat($_)=>1} @m }, };
$min = $i if $squares{ flat($s) }->{n}->{$f_to};
}
}
last if $min > -1;
@s = @n;
}
show_path( $f_to, $min );
sub show_path {
my ($s,$i) = @_;
return if $s eq $f_from;
print "$i => $f_to\n" if $i == $min;
foreach my $k ( keys %squares ) {
if ( $squares{$k}->{i} == $i && $squares{$k}->{n}->{$s} ) {
$i--;
print "$i => $k\n";
show_path( $k, $i );
last;
}
}
}
sub flat { "$_[0]->[0],$_[0]->[1]" }
sub moves {
my $c = shift;
my @s = ();
foreach my $m ( @moves ) {
my $x = $c->[0] + $m->[0];
my $y = $c->[1] + $m->[1];
if ( $x >= 0 && $x <=$max_x && $y >=0 && $y <=$max_y) {
push @s, [$x, $y];
}
}
return @s;
}
__END__
public class Horse {
private int[][] board;
private int[] xer = { 2, 1, -1, -2, -2, -1, 1, 2 };
private int[] yer = { 1, 2, 2, 1, -1, -2, -2, -1 };
private final static int A_BIG_NUMBER = 10000;
private final static int UPPER_BOUND = 64;
public Horse() {
board = new int[8][8];
}
private int solution(int x, int y, int destx, int desty, int move) {
if(move == UPPER_BOUND) {
/* lets put an upper bound to avoid stack overflow */
return A_BIG_NUMBER;
}
if(x == 6 && y ==5) {
board[6][5] = 1;
return 1;
}
int min = A_BIG_NUMBER;
for (int i = 0 ; i < xer.length; i++) {
if (isMoveGood(x + xer[i], y + yer[i])) {
if(board[x + xer[i]][y + yer[i]] != 0) {
min = Integer.min(min, 1 + board[x +xer[i]] [y +yer[i]]);
} else {
min = Integer.min(min, 1 + solution(x + xer[i], y + yer[i], destx, desty, move + 1));
}
}
}
board[x][y] = min;
return min;
}
private boolean isMoveGood(int x, int y) {
if (x >= 0 && x < board.length && y >= 0 && y < board.length)
return true;
return false;
}
public static void main(String[] args) {
int destX = 6;
int destY = 7;
final Horse h = new Horse();
System.out.println(h.solution(0, 0, destX, destY, 0));
}
}
Graeme Pyle의 답변 jsfiddle 위의 루비 코드 , 모든 추가 코드를 스트라이프하고 그의 알고리즘으로 솔루션을 얻기 위해 나머지를 루비로 변환하면 작동하는 것처럼 보입니다. 그래도 테스트 :
def getBoardOffset(board)
return board.length / 2
end
def setMoveCount(x, y, count, board)
offset = getBoardOffset(board)
board[y + offset][x + offset] = count
end
def getMoveCount(x, y, board)
offset = getBoardOffset(board)
row = board[y + offset]
return row[x + offset]
end
def isBottomOfVerticalCase(x, y)
return (y - 2 * x) % 4 == 0
end
def isPrimaryDiagonalCase(x, y)
return (x + y) % 2 == 0
end
def isSecondaryDiagonalCase(x, y)
return (x + y) % 2 == 1
end
def simplifyBySymmetry(x, y)
x = x.abs
y = y.abs
if (y < x)
t = x
x = y
y = t
end
return {x: x, y: y}
end
def getPrimaryDiagonalCaseMoveCount(x, y)
var diagonalOffset = y + x
var diagonalIntersect = diagonalOffset / 2
return ((diagonalIntersect + 2) / 3).floor * 2
end
def getSpecialCaseMoveCount(x, y)
specials = [{
x: 0,
y: 0,
d: 0
},
{
x: 0,
y: 1,
d: 3
},
{
x: 0,
y: 2,
d: 2
},
{
x: 0,
y: 3,
d: 3
},
{
x: 2,
y: 2,
d: 4
},
{
x: 1,
y: 1,
d: 2
},
{
x: 3,
y: 3,
d: 2
}
];
matchingSpecial=nil
specials.each do |special|
if (special[:x] == x && special[:y] == y)
matchingSpecial = special
end
end
if (matchingSpecial)
return matchingSpecial[:d]
end
end
def isVerticalCase(x, y)
return y >= 2 * x
end
def getVerticalCaseMoveCount(x, y)
normalizedHeight = getNormalizedHeightForVerticalGroupCase(x, y)
groupIndex = (normalizedHeight/4).floor
groupStartMoveCount = groupIndex * 2 + x
return groupStartMoveCount + getIndexInVerticalGroup(x, y)
end
def getIndexInVerticalGroup(x, y)
return getNormalizedHeightForVerticalGroupCase(x, y) % 4
end
def getYOffsetForVerticalGroupCase(x)
return x * 2
end
def getNormalizedHeightForVerticalGroupCase(x, y)
return y - getYOffsetForVerticalGroupCase(x)
end
def getSecondaryDiagonalCaseMoveCount(x, y)
diagonalOffset = y + x
diagonalIntersect = diagonalOffset / 2 - 1
return ((diagonalIntersect + 2) / 3).floor * 2 + 1
end
def getMoveCountO1(x, y)
newXY = simplifyBySymmetry(x, y)
x = newXY[:x]
y = newXY[:y]
specialMoveCount = getSpecialCaseMoveCount(x ,y)
if (specialMoveCount != nil)
return specialMoveCount
elsif (isVerticalCase(x, y))
return getVerticalCaseMoveCount(x ,y)
elsif (isPrimaryDiagonalCase(x, y))
return getPrimaryDiagonalCaseMoveCount(x ,y)
elsif (isSecondaryDiagonalCase(x, y))
return getSecondaryDiagonalCaseMoveCount(x ,y)
end
end
def solution(x ,y)
return getMoveCountO1(x, y)
end
puts solution(0,0)
유일한 의도는 누군가가 전체 코드를 필요로하는 경우 코드 변환 시간을 절약하는 것입니다.
Jules May 함수의 PHP 버전입니다.
function knightDistance($x, $y)
{
$x = abs($x);
$y = abs($y);
if($x < $y)
{
$tmp = $x;
$x = $y;
$y = $tmp;
}
if($x > 2 * $y)
{
$n7 = 0;
$n8 = floor(($x + 2*$y) / 4);
$n10 = floor(($x - 2*$y +1) / 4);
}
else
{
$n7 = floor((2*$y - $x) / 3);
$n8 = floor((2*$x - $y) / 3);
$n10 = 0;
}
$x -= 2 * $n8 + $n7 + 2 * $n10;
$y -= $n8 + 2 * $n7 - $n10;
if($x == 1 && $y == 0)
{
if($n8 > 0)
{
$x = 3;
$y = 1;
$n8--;
}
}
if($x == 2 && $y == 2)
{
if($n8 > 0)
{
$x = 3;
$y = 1;
$n8--;
$n7++;
}
}
$cheatsheet = [[0, 3, 2], [2, 0, 2], [4]];
return $n7 + $n8 + $n10 + $cheatsheet [$y][$x-$y];
}
여기 내 프로그램이 있습니다. 이것은 완벽한 해결책이 아닙니다. 재귀 함수에는 많은 변경 사항이 있습니다. 그러나이 최종 결과는 완벽합니다. 나는 약간의 최적화를 시도했습니다.
public class KnightKing2 {
private static int tempCount = 0;
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
int ip1 = Integer.parseInt(in.nextLine().trim());
int ip2 = Integer.parseInt(in.nextLine().trim());
int ip3 = Integer.parseInt(in.nextLine().trim());
int ip4 = Integer.parseInt(in.nextLine().trim());
in.close();
int output = getStepCount(ip1, ip2, ip3, ip4);
System.out.println("Shortest Path :" + tempCount);
}
// 2 1 6 5 -> 4
// 6 6 5 5 -> 2
public static int getStepCount(int input1, int input2, int input3, int input4) {
return recurse(0, input1, input2, input3, input4);
}
private static int recurse(int count, int tx, int ty, int kx, int ky) {
if (isSolved(tx, ty, kx, ky)) {
int ccount = count+1;
System.out.println("COUNT: "+count+"--"+tx+","+ty+","+ccount);
if((tempCount==0) || (ccount<=tempCount)){
tempCount = ccount;
}
return ccount;
}
if ((tempCount==0 || count < tempCount) && ((tx < kx+2) && (ty < ky+2))) {
if (!(tx + 2 > 8) && !(ty + 1 > 8)) {
rightTop(count, tx, ty, kx, ky);
}
if (!(tx + 2 > 8) && !(ty - 1 < 0)) {
rightBottom(count, tx, ty, kx, ky);
}
if (!(tx + 1 > 8) && !(ty + 2 > 8)) {
topRight(count, tx, ty, kx, ky);
}
if (!(tx - 1 < 0) && !(ty + 2 > 8)) {
topLeft(count, tx, ty, kx, ky);
}
if (!(tx + 1 > 8) && !(ty - 2 < 0)) {
bottomRight(count, tx, ty, kx, ky);
}
if (!(tx - 1 < 0) && !(ty - 2 < 0)) {
bottomLeft(count, tx, ty, kx, ky);
}
if (!(tx - 2 < 0) && !(ty + 1 > 8)) {
leftTop(count, tx, ty, kx, ky);
}
if (!(tx - 2 < 0) && !(ty - 1 < 0)) {
leftBottom(count, tx, ty, kx, ky);
}
}
return count;
}
private static int rightTop(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx + 2, ty + 1, kx, ky);
}
private static int topRight(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx + 1, ty + 2, kx, ky);
}
private static int rightBottom(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx + 2, ty - 1, kx, ky);
}
private static int bottomRight(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx + 1, ty - 2, kx, ky);
}
private static int topLeft(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx - 1, ty + 2, kx, ky);
}
private static int bottomLeft(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx - 1, ty - 2, kx, ky);
}
private static int leftTop(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx - 2, ty + 1, kx, ky);
}
private static int leftBottom(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx - 2, ty - 1, kx, ky);
}
private static boolean isSolved(int tx, int ty, int kx, int ky) {
boolean solved = false;
if ((tx == kx) && (ty == ky)) {
solved = true;
} else if ((tx + 2 == kx) && (ty + 1 == ky)) { // right top
solved = true;
} else if ((tx + 2 == kx) && (ty - 1 == ky)) { // right bottom
solved = true;
} else if ((ty + 2 == ky) && (tx + 1 == kx)) {// top right
solved = true;
} else if ((ty + 2 == ky) && (tx - 1 == kx)) {// top left
solved = true;
} else if ((tx - 2 == kx) && (ty + 1 == ky)) { // left top
solved = true;
} else if ((tx - 2 == kx) && (ty - 1 == ky)) {// left bottom
solved = true;
} else if ((ty - 2 == ky) && (tx + 1 == kx)) { // bottom right
solved = true;
} else if ((ty - 2 == ky) && (tx - 1 == kx)) { // bottom left
solved = true;
}
return solved;
}
}
다음은 finit 보드에서 작동하는 Mustafa Serdar Şanlı 코드를 기반으로 한 C 버전입니다.
#include <stdio.h>
#include <math.h>
#define test(x1, y1, x2, y2) (sx == x1 && sy == y1 &&tx == x2 &&ty == y2) || (sx == x2 && sy == y2 && tx == x1 && ty==y1)
int distance(int sx, int sy, int tx, int ty) {
int x, y, t;
double delta;
// special corner cases
if (test(1, 1, 2, 2) ||
test(7, 7, 8, 8) ||
test(7, 2, 8, 1) ||
test(1, 8, 2, 7))
return 4;
// axes symmetry
x = abs(sx - tx);
y = abs(sy - ty);
// diagonal symmetry
if (x < y) {
t = x;
x = y;
y = t;
}
// 2 corner cases
if (x == 1 && y == 0)
return 3;
if (x == 2 && y == 2)
return 4;
// main
delta = x - y;
if (y > delta) {
return (int)(delta - 2 * floor((delta - y) / 3));
}
else {
return (int)(delta - 2 * floor((delta - y) / 4));
}
}
재귀 솔루션에 대한 증명으로 여기 에서 테스트하십시오.
참고 URL : https://stackoverflow.com/questions/2339101/knights-shortest-path-on-chessboard
'developer tip' 카테고리의 다른 글
| 스위치 케이스의 변수 범위 (0) | 2020.09.05 |
|---|---|
| JSON에서 각 이름이 인용되는 이유는 무엇입니까? (0) | 2020.09.05 |
| Android에서 화면 회전시 대화 상자 닫기 방지 (0) | 2020.09.05 |
| namedtuple에 힌트 입력 (0) | 2020.09.05 |
| Xcode 8 및 iOS10부터 viewDidLayoutSubviews에서보기 크기가 적절하지 않습니다. (0) | 2020.09.05 |