Caballero de la Ruta más corta sobre un Tablero de ajedrez
https://stackoverflow.com/questions/2339101
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
He estado practicando para una próxima programación de la competencia y de la que he tropezado a través de una pregunta que estoy completamente desconcertado al.Sin embargo, me siento como si se trata de un concepto que debe aprender ahora, en lugar de cruzar mis dedos que nunca llega.
Básicamente, se trata de un caballero de la pieza en un tablero de ajedrez.Cuenta con dos entradas:ubicación de inicio y finalización de la ubicación.El objetivo es, a continuación, calcular e imprimir el camino más corto que el caballero puede tomar para llegar a la ubicación de destino.
Nunca he tratado con ruta más corta-esque las cosas, y yo no sé ni por dónde empezar.Lo que la lógica de hacer que utilizo para ir a abordar esto?
P. S.Si es relevante, de lo que ellos quieren que usted para complementar el caballero de la normal a la que se mueve también le permite moverse a las cuatro esquinas del cuadrado formado por el (potencialmente) ocho mueve un caballero puede hacer, dado que el centro de la plaza se encuentra el caballero de la ubicación.
Solución
Tienes un gráfico aquí, donde todos los movimientos disponibles están conectados (valor = 1), y no disponibles movimientos son desconectados (valor = 0), la matriz dispersa sería como:
(a1,b3)=1,
(a1,c2)=1,
.....
Y el camino más corto de los dos puntos en un gráfico pueden encontrarse usando http: // en. wikipedia.org/wiki/Dijkstra's_algorithm
Pseudocódigo de Wikipedia páginas:
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[]
EDIT:
- como Morón, dicho usando el http://en.wikipedia.org/wiki/A*_algorithm puede ser más rápido.
- la manera más rápida, es comprobar la validez de calcular todas las distancias y guardarlo en una matriz de 8x8 completa. así, yo llamaría que el engaño, y trabaja sólo por el problema es pequeño. Pero a veces las competiciones comprobará la velocidad de su programa de carreras.
- El punto principal es que si se está preparando
para un concurso de programación, debe conocer
algoritmos comunes incluyendo Dijkstra.
Un punto de partida bueno está leyendo
Introduction to AlgorithmsISBN 0-262-03384-4. O usted podría intentar Wikipedia, http://en.wikipedia.org/wiki/List_of_algorithms
Otros consejos
EDITAR: Véase la respuesta de simon, donde se fija la fórmula que aquí se presenta.
En realidad no es una operación O(1) fórmula
Esta es una imagen que he hecho para visualizarla ( Cuadrados de un caballero puede llegar en Nth mueva están pintados con el mismo color ).
Puede que usted note el patrón aquí?
A pesar de que podemos ver el patrón, es realmente difícil encontrar la función f( x , y ) que devuelve el número de movimientos necesarios para ir de la plaza de ( 0 , 0 ) a la plaza de ( x , y )
Pero aquí es la fórmula que funciona cuando 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 );
}
Nota:Esta pregunta se la hicieron en SACO de 2007, Día 1
Y las soluciones son aquí
Aquí hay una O correcto (1) solución, pero para el caso donde los caballo se mueve como un caballo de ajedrez solamente, y en un tablero de ajedrez infinito:
https://jsfiddle.net/graemian/5qgvr1ba/11/
La clave para encontrar esto es darse cuenta de los patrones que surgen cuando se dibuja la junta. En el siguiente diagrama, el número de la plaza es el número mínimo de movimientos necesarios para alcanzar esa plaza (se puede usar la búsqueda en amplitud para encontrar esto):
Debido a que la solución es simétrica en todos los ejes y las diagonales, sólo he dibujado la x> = 0 e y> = x caso.
El bloque inferior izquierda es la posición inicial y los números de los bloques representan el número mínimo de movimientos para alcanzar esos bloques.
Existen 3 modelos a destacar:
- de incrementación grupos verticales azules de 4
- Las "primarias" diagonales rojas (que corren de arriba a abajo a la izquierda-derecha, como una barra invertida)
- Las diagonales verdes "secundarios" (misma orientación que rojo)
(Asegúrese de ver ambos conjuntos de diagonales como parte superior izquierda a la parte inferior derecha. Tienen un constante movimiento de conteo. Las diagonales superior derecha de abajo a la izquierda son mucho más complejos.)
Se puede derivar fórmulas para cada uno. Los bloques amarillos son casos especiales. Así que la solución se convierte en:
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);
}
con el más duro estando los grupos verticales:
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);
}
Ver el violín para los demás casos.
Tal vez hay patrones más simples o más elegantes que echaba de menos? Si es así, me gustaría verlos. En particular, noto algunos patrones diagonales en los casos verticales de color azul, pero no los he explorado. Independientemente, esta solución aún satisface la O (1) de restricción.
Un problema muy interesante, que me encontré recientemente. Después de mirar algunas soluciones que estaba intentado recuperar fórmula analítica (O(1) time and space complexity) dada en SACO 2007 Día 1 soluciones .
En primer lugar quiero apreciar Graeme Pyle para la visualización muy agradable que me ayudó a la fórmula del arreglo.
Por alguna razón (quizás por la simplificación o la belleza o simplemente un error) se trasladaron signo minus en floor operador, como resultado, han conseguido fórmula incorrecta floor(-a) != -floor(a) for any a.
Aquí es la fórmula analítica correcta:
var delta = x-y;
if (y > delta) {
return delta - 2*Math.floor((delta-y)/3);
} else {
return delta - 2*Math.floor((delta-y)/4);
}
La fórmula funciona para todas las (x, y) pares (después de aplicar ejes y simetría diagonal) excepto (1,0) y (2,2) casos de esquina, que no se satisfacen al patrón y codificado en el siguiente fragmento:
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>
Nota:. El jQuery usada sólo por ilustración, para la función de código Ver distance
Sí, Dijkstra y BFS le conseguirán la respuesta, pero creo que el contexto de ajedrez de este problema proporciona el conocimiento que puede producir una solución que es mucho más rápido que un algoritmo de ruta más corta genérica, especialmente en un tablero de ajedrez infinito.
Para simplificar, vamos a describir el tablero de ajedrez como el (x, y) avión. El objetivo es encontrar el camino más corto a partir de (x0, y0) a (x1, y1), utilizando sólo los pasos candidatos (+ -1, + -2), (+ -2, -1 +) y (+ -2 , + -2), como se describe en el PS de la cuestión
Aquí está la nueva observación: dibujar un cuadrado con esquinas (X-4, Y-4), (X-4, y + 4), (x + 4, y-4), (x + 4, y 4). Este conjunto (lo llaman S4) contiene 32 puntos. El camino más corto desde cualquiera de estos 32 puntos (x, y) requiere exactamente dos movimientos .
La ruta más corta desde cualquiera de los 24 puntos en el conjunto S3 (definido de manera similar) a (x, y) requiere al menos dos movimientos .
Por lo tanto, si | x1-x0 |> 4 ó | y1-y0 |> 4, el camino más corto a partir de (x0, y0) a (x1, y1) es exactamente dos movimientos mayor que el camino más corto a partir de (x0, y0) a S4. Y el último problema puede ser resuelto rápidamente con iteración directa.
Sea N = max (| x1-x0 |, | y1-y0 |). Si N> = 4, entonces el camino más corto a partir de (x0, y0) a (x1, y1) tiene ceil (N / 2) pasos.
La O (1) respuesta anterior [ https://stackoverflow.com/a/8778592/4288232 por Mustafa Serdar Şanlı] no está funcionando realmente. (Check (1,1) o (3,2) o (4,4), a un lado para los casos de borde obvia de (1,0) o (2,2)).
A continuación se muestra una solución más feo mucho (pitón), que hace el trabajo (con "pruebas" añadidos):
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()
Lo que hay que hacer es pensar en los posibles movimientos del caballero como un gráfico, donde cada posición en el tablero es un nodo y los posibles movimientos a otra posición como una ventaja. No hay necesidad de que el algoritmo de Dijkstra, porque cada borde tiene el mismo peso o distancia (todos ellos son igual de fácil o corto que hacer). Usted sólo puede hacer una búsqueda BFS desde su punto de partida hasta llegar a la posición final.
Solución a partir de primeros principios en Python
Me encontró por primera vez este problema en una prueba Codility. Me dieron 30 minutos para resolverlo - me tomó mucho más tiempo de lo que para llegar a este resultado! El problema era: ¿cuántos movimientos que hace falta para que un caballero para ir desde 0,0 a x, y sólo es legal el uso del caballo se mueve. X e Y eran más o menos ilimitada (por lo que no estamos hablando aquí de un simple tablero de ajedrez de 8x8).
Se quería una (1) solución de O. Yo quería una solución en la que el programa estaba resolviendo claramente el problema (es decir, quería algo más, obviamente correcto que el patrón de Graeme - patrones tienen la costumbre de romper en el que no está buscando), y yo realmente quería no tener que depender de una fórmula argumentada, como en la solución de Mustafa
Por lo tanto, aquí está mi solución, por lo que vale la pena. Comienzo, ya que otros tienen, señalando la solución es simétrica alrededor de los ejes y diagonales, por lo que necesitamos para resolver sólo para 0> = y> = x. Para simplificar la explicación (y código) Voy a revertir el problema:. El caballo se inicia en x, y, y está apuntando a 0,0
Supongamos que reducir el tamaño del problema abajo a la vecindad del origen. Vamos a llegar a lo que vicinty 'significa en realidad en su momento, pero por ahora, vamos a escribir algunas soluciones abajo en un cheatsheet (origen abajo a la izquierda):
2 1 4 3
3 2 1 2
0 3 2 3
Por lo tanto, dado X, Y en la parrilla, que se acaba de leer el número de movimientos al origen.
Si hemos comenzado fuera de la red, tenemos que trabajar la espalda camino a ella. Introducimos la 'línea media', que es la línea representada por y = x / 2. Cualquier caballero en x, y en esa línea puede trabajar su parte posterior forma de la cheatsheet usando una serie de 8 en punto se mueve (que es: (-2, -1) se mueve). Si x, y se encuentra por encima de la línea media, a continuación, vamos a necesitar una sucesión de 8 de la mañana y las 7 horas se mueve, y si se encuentra por debajo de la línea media, necesitaremos una sucesión de 8 de la mañana y las 10 de 'reloj se mueve. Dos cosas a tener en cuenta aquí:
- Estas secuencias son demostrablemente caminos más cortos. (¿Quieres que te lo demuestre, o es obvio?)
- Nos preocupan sólo por el número de tales movimientos. Podemos mezclar y combinar los movimientos en cualquier orden.
Por lo tanto, vamos a ver los movimientos por encima de la línea media. Lo que estamos afirmando es que:
-
(dx; dy) = (2,1; 1,2) (n8; n7) (notación matricial, sin composición tipográfica matemáticas - vector columna (dx; dy) es igual a la matriz cuadrada multiplicado por el vector columna ( n8; n7) - el número de las 8 en punto se mueve y el número de las 7 en punto se mueve), y de manera similar;
-
(dx; dy) = (2,2; 1, -1) (n8; n10)
estoy afirmando que dx, dy será más o menos (x, y), por lo que (x-dx, y-dy) estará en las proximidades del origen (lo que sea 'proximidad' resulta ser).
Las dos líneas en el código que calcular estos términos son la solución a estos, pero son seleccionados para tener algunas propiedades útiles:
- El por encima de la línea media de la fórmula se mueve (x, y) para uno de (0,0), (1,1), o (2,2).
- El debajo de la línea media de la fórmula mueve (x, y) a una de (0,0), (1,0), (2,0), o (1,1).
(¿Quieres que te pruebas de estos?) Por lo tanto, la distancia a la Knight será la suma de la N7, N8, N10 y cheatsheet [x-dx, y-dy], y nuestra cheatsheet reduce a esto:
. . 4
. 2 .
0 3 2
Ahora, esto no es bastante el final de la historia. Mira el 3 en la fila inferior. Las únicas formas en que podemos llegar a esta son ya sea:
- Se inició allí, o
- Se trasladó allí, por una secuencia de 8 de la mañana y las 10 en punto se mueve. Pero si el último movimiento era un niño de 8 horas (la que tiene derecho a ser, ya que podemos hacer nuestros movimientos en cualquier orden), entonces tenemos que haber pasado por (3,1), cuya distancia es en realidad 2 (como pueda ver desde el cheatsheet original). Así que lo que debemos hacer es volver pista uno ocho movimiento, ahorrando dos movimientos en total.
Hay una optimización similares que se tuvo con el 4 en la parte superior derecha. Aparte de a partir de ahí, la única manera de llegar es mediante un movimiento de ocho (4,3). EseNo es en la cheatsheet, pero si lo fuera allí, su distancia sería 3, ya que podríamos tener de 7 a o'clocked (3,1) en lugar, que tiene una distancia de sólo 2. Por lo tanto, debemos volver la pista uno 8 en punto movimiento y, a continuación, ir hacia delante un 7-en punto.
Por lo tanto, tenemos que añadir un número más a la cheatsheet:
. . 4
. 2 . 2
0 3 2
(Nota: hay toda una carga de back-tracking optimizaciones a partir de (0,1) y (0,2), pero desde el solucionador no nos llevará allí, que no tiene que preocuparse acerca de ellos.)
Así que aquí es, pues, algo de código Python para evaluar lo siguiente:
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]
Por cierto, si quieres conocer una ruta real, entonces este algoritmo proporciona eso también: es simplemente una sucesión de N7-7 en punto se mueve, seguido por (o intercalados con) n8-8 en punto se mueve, n10-10 en punto se mueve, y cualquiera que sea la danza es dictado por el cheatsheet (que, a su vez, puede estar en una cheatsheet).
Ahora: ¿Cómo demostrar que esto es correcto. No es suficiente sólo para comparar estos resultados con una tabla de respuestas correctas, ya que el problema en sí no tiene límites. Sin embargo, podemos decir que, si la distancia de un s plaza de Caballero es d, entonces si {m} es el conjunto de movimientos legales de s, distancia de la del Caballero (s + m) debe ser o D-1 o D + 1 para todo m. (¿Necesita una prueba de esto?) Por otra parte, debe haber al menos uno de esos cuadrados cuya distancia es D-1, a menos que s es el origen. Por lo tanto, podemos probar la corrección, mostrando esta propiedad se mantiene para todas las plazas. Así:
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")
Como alternativa, podemos demostrar la exactitud de cualquier uno s cuadrados por perseguir la ruta de s cuesta abajo hacia el origen. En primer lugar, cheque s razonable de que el anterior, a continuación, seleccione cualquiera s + m que tal distancia (s + m) == d-1. Repita hasta llegar al origen.
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.
No he estudiado gráficos yet..as por el problema de la aplicación a través de matrices simplemente, no podía derivar cualquier solución que no sea esta. Me trataron las posiciones no como filas y columnas (la notación de ajedrez habitual), pero como los índices de matriz. Para su información, esto es sólo un tablero de ajedrez 8 * 8. Cualquier consejo mejora es siempre bienvenida.
* Los comentarios deben ser suficientes para su comprensión de la lógica. Sin embargo, siempre se puede pedir.
* A cuadros en DEV-C ++ 4.9.9.2 compilador (El derramamiento de sangre Software).
Creo que esto podría también ayudar ..
NumWays(x,y)=1+min(NumWays(x+-2,y-+1),NumWays(x+-1,y+-2));
y el uso de programación dinámica para obtener la solución.
P.S:. Es un poco utiliza los BFS sin tener que tomarse la molestia de declarar los nodos y los bordes de la gráfica
Aquí hay una solución para este problema en particular implementado en Perl. Se mostrará uno de los caminos más cortos -. Que puede haber más de uno en algunos casos
No hizo uso de cualquiera de los algoritmos descritos anteriormente -., Pero que sería bueno para compararlo con otras soluciones
#!/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));
}
}
Sólo código de rubí jsFiddle de respuesta de Graeme Pyle anterior , rayado todo el código extra y convertida restante al rubí sólo para obtener una solución por su algoritmo, que parece trabajar. Aún a pesar de las pruebas:
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)
Sólo intención es salvar a alguien algún tiempo la conversión de código si alguien necesita código completo.
aquí está la versión de PHP de mayo de Julio de función
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];
}
Aquí está mi programa. Esto no es una solución perfecta. Hay un montón de cambios para hacer en la función de la recursividad. Pero este resultado final es perfecto. He intentado optimizar un poco.
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;
}
}
Esta es una versión basada en el código C Mustafa Serdar Şanlı que funciona para un tablero finit:
#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));
}
}
Prueba aquí con la prueba en contra de una solución recursiva
