El camino más corto del caballero en el tablero de ajedrez

He estado practicando para una próxima competencia de programación y me he encontrado con una pregunta que me desconcierta por completo. Sin embargo, siento que es un concepto que debería aprender ahora en lugar de cruzar los dedos y que nunca surge.

Básicamente, se trata de una pieza de caballo en un tablero de ajedrez. Se le dan dos entradas: ubicación inicial y ubicación final. El objetivo es calcular e imprimir el camino más corto que el caballero puede tomar para llegar a la ubicación de destino.

Nunca me he ocupado de cosas que se parezcan al camino más corto y ni siquiera sé por dónde empezar. ¿Qué lógica utilizo para abordar esto?

PD: Si tiene alguna relevancia, quieren que complementes los movimientos normales del caballo permitiéndole también moverse a las cuatro esquinas del cuadrado formado por los (potencialmente) ocho movimientos que un caballo puede hacer, dado que el centro del cuadrado es la ubicación del caballero.

Aquí tiene un gráfico, donde todos los movimientos disponibles están conectados (valor = 1) y los movimientos no disponibles están desconectados (valor = 0), la matriz dispersa sería como:

(a1,b3)=1,
(a1,c2)=1,
  .....

Y la ruta más corta de dos puntos en un gráfico se puede encontrar usando http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Pseudocódigo de la página wikipedia:

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[]

EDITAR:

1. como idiota, dijo que usar http://en.wikipedia.org/wiki/A*_algorithm puede ser más rápido.
2. la forma más rápida es precalcular todas las distancias y guardarlas en una matriz completa de 8x8. bueno, yo llamaría a eso trampa, y funciona solo porque el problema es pequeño. Pero a veces las competiciones comprobarán qué tan rápido se ejecuta su programa.
3. El punto principal es que si se está preparando para una competencia de programación, debe conocer los algoritmos comunes, incluido el de Dijkstra. Un buen punto de partida es leer el Introduction to AlgorithmsISBN 0-262-03384-4. O puede probar wikipedia, http://en.wikipedia.org/wiki/List_of_algorithms

EDITAR: Vea la respuesta de Simon , donde arregló la fórmula presentada aquí.

De hecho, existe una fórmula O (1)

Esta es una imagen que hice para visualizarla (los cuadrados que un caballero puede alcanzar en el N- ^ésimo movimiento están pintados con el mismo color).

¿Puedes notar el patrón aquí?

Aunque 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 pasar de un cuadrado ( 0 , 0 )a otro.( x , y )

Pero aquí está 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 hizo el día 1 de SACO 2007
y las soluciones están aquí

Aquí hay una solución O (1) correcta, pero para el caso en el que el 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 notar los patrones que surgen cuando dibuja el tablero. En el diagrama a continuación, el número en el cuadrado es el número mínimo de movimientos necesarios para llegar a ese cuadrado (puede usar la búsqueda primero en amplitud para encontrar esto):

Debido a que la solución es simétrica entre los ejes y las diagonales, solo dibujé el caso x> = 0 y y> = x.

El bloque de la parte inferior izquierda es la posición inicial y los números en los bloques representan el número mínimo de movimientos para llegar a esos bloques.

Hay 3 patrones para notar:

• Los grupos verticales azules crecientes de 4
• Las diagonales rojas "primarias" (van de arriba a la izquierda a abajo a la derecha, como una barra invertida)
• Las diagonales verdes "secundarias" (la misma orientación que la roja)

(Asegúrese de ver ambos conjuntos de diagonales de arriba a la izquierda a abajo a la derecha. Tienen un recuento de movimientos constante. Las diagonales de abajo a la izquierda y arriba a la derecha son mucho más complejas).

Puede derivar fórmulas para cada uno. Los bloques amarillos son casos especiales. Entonces 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);

}

siendo los más difíciles 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);

}

Vea el violín para los otros casos.

¿Quizás hay patrones más simples o más elegantes que me perdí? Si es así, me encantaría verlos. En particular, noto algunos patrones diagonales en los casos verticales azules, pero no los he explorado. Independientemente, esta solución aún satisface la restricción O (1).

Problema muy interesante con el que me encontré recientemente. Después de buscar algunas soluciones, intenté recuperar la fórmula analítica ( O(1) time and space complexity) dada en las soluciones del Día 1 de SACO 2007 .

En primer lugar, quiero agradecer a Graeme Pyle por una visualización muy agradable que me ayudó a arreglar la fórmula.

Por alguna razón (tal vez por simplificación o belleza o simplemente por un error) movieron el minussigno al flooroperador, como resultado, obtuvieron una fórmula incorrecta floor(-a) != -floor(a) for any a.

Aquí está 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 todos los pares (x, y) (después de aplicar ejes y simetría diagonal) excepto los casos de esquina (1,0) y (2,2), que no cumplen con el patrón y están codificados 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: jQuery se usa solo para ilustración, para el código, consulte la distancefunción.

Sí, Dijkstra y BFS te darán la respuesta, pero creo que el contexto ajedrecístico de este problema proporciona un conocimiento que puede producir una solución mucho más rápida que un algoritmo genérico de ruta más corta, especialmente en un tablero de ajedrez infinito.

Para simplificar, describamos el tablero de ajedrez como el plano (x, y). El objetivo es encontrar la ruta más corta de (x0, y0) a (x1, y1) utilizando solo los pasos candidatos (+ -1, + -2), (+ -2, + -1) y (+ -2 , + -2), como se describe en el PS de la pregunta

Aquí está la nueva observación: dibuje un cuadrado con esquinas (x-4, y-4), (x-4, y + 4), (x + 4, y-4), (x + 4, y + 4) . Este conjunto (llámelo S4) contiene 32 puntos. El camino más corto desde cualquiera de estos 32 puntos hasta (x, y) requiere exactamente dos movimientos .

El camino más corto desde cualquiera de los 24 puntos del conjunto S3 (definido de manera similar) a (x, y) requiere al menos dos movimientos .

Por lo tanto, si | x1-x0 |> 4 o | y1-y0 |> 4, la ruta más corta de (x0, y0) a (x1, y1) es exactamente dos movimientos mayor que la ruta más corta de (x0, y0) a S4. Y el último problema se puede resolver rápidamente con una iteración sencilla.

Sea N = max (| x1-x0 |, | y1-y0 |). Si N> = 4, entonces la ruta más corta de (x0, y0) a (x1, y1) tiene pasos ceil (N / 2) .

La respuesta O (1) anterior [ https://stackoverflow.com/a/8778592/4288232 por Mustafa Serdar Şanlı] no funciona realmente. (Marque (1,1) o (3,2) o (4,4), aparte de los casos extremos obvios de (1,0) o (2,2)).

A continuación se muestra una solución mucho más fea (python), que funciona (con "pruebas" agregadas):

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 debes hacer es pensar en los posibles movimientos del caballo como un gráfico, donde cada posición en el tablero es un nodo y los posibles movimientos a otra posición como un borde. No es necesario el algoritmo de dijkstra, porque cada borde tiene el mismo peso o distancia (todos son tan fáciles o cortos de hacer). Puede hacer una búsqueda BFS desde su punto de partida hasta llegar a la posición final.

Solución de los primeros principios en Python

Encontré este problema por primera vez en una prueba de codilidad. Me dieron 30 minutos para resolverlo, ¡me tomó mucho más tiempo llegar a este resultado! El problema era: ¿cuántos movimientos se necesitan para que un caballo pase de 0,0 a x, y usando solo los movimientos legales del caballo? xey eran más o menos ilimitados (por lo que no estamos hablando aquí de un tablero de ajedrez simple de 8x8).

Querían una solución O (1). Quería una solución en la que el programa resolviera claramente el problema (es decir, quería algo más obviamente correcto que el patrón de Graeme; los patrones tienen el hábito de romperse donde no estás mirando), y realmente quería no tener que depender de un fórmula indiscutible, como en la solución de Mustafa

Entonces, aquí está mi solución, por lo que vale. Comience, como lo han hecho otros, notando que la solución es simétrica con respecto a los ejes y las diagonales, por lo que solo necesitamos resolver para 0> = y> = x. Para simplificar la explicación (y el código) voy a revertir el problema: el caballo comienza en x, y, y apunta a 0,0.

Supongamos que reducimos el problema a la vecindad del origen. Llegaremos a lo que realmente significa 'vicinty' a su debido tiempo, pero por ahora, escribamos algunas soluciones en una hoja de referencia (el origen en la parte inferior izquierda):

2 1 4 3
3 2 1 2
0 3 2 3

Entonces, dados x, y en la cuadrícula, podemos leer el número de movimientos al origen.

Si hemos comenzado fuera de la red, tenemos que volver a ella. Introducimos la 'línea media', que es la línea representada por y = x / 2. Cualquier caballo en x, y en esa línea puede regresar a la hoja de trucos usando una serie de movimientos de las 8 en punto (es decir: movimientos (-2, -1)). Si x, y se encuentra por encima de la línea media, entonces necesitaremos una sucesión de movimientos de las 8 en punto y las 7 en punto, y si está por debajo de la línea media, necesitaremos una sucesión de las 8 en punto y las 10 en punto. El reloj se mueve. Dos cosas a tener en cuenta aquí:

• Estas secuencias son probablemente los caminos más cortos. (¿Quieres que lo pruebe o es obvio?)
• Solo nos preocupamos por la cantidad de tales movimientos. Podemos mezclar y combinar los movimientos en cualquier orden.

Entonces, veamos los movimientos por encima de la línea media. Lo que afirmamos es que:

• (dx; dy) = (2,1; 1,2) (n8; n7) (notación matricial, sin composición tipográfica matemática - el vector de columna (dx; dy) es igual a la matriz cuadrada multiplicada por el vector de columna (n8; n7) - el número de movimientos de las 8 en punto y el número de movimientos de las 7 en punto), y de manera similar;

• (dx; dy) = (2,2; 1, -1) (n8; n10)

Afirmo que dx, dy será aproximadamente (x, y), por lo que (x-dx, y-dy) estará en la vecindad del origen (cualquier 'vecindad' que resulte ser).

Las dos líneas del código que calculan estos términos son la solución a estos, pero se seleccionan para tener algunas propiedades útiles:

• La fórmula de la línea media anterior mueve (x, y) a uno de (0,0), (1,1) o (2,2).
• La fórmula por debajo de la línea media mueve (x, y) a uno de (0,0), (1,0), (2,0) o (1,1).

(¿Le gustaría tener pruebas de esto?) Entonces, la distancia del Caballero será la suma de n7, n8, n10 y la hoja de referencia [x-dx, y-dy], y nuestra hoja de referencia se reduce a esto:

. . 4
. 2 .
0 3 2

Ahora bien, este no es el final de la historia. Mira el 3 en la fila inferior. Las únicas formas en que podemos lograr esto son:

• Empezamos ahí, o
• Nos mudamos allí, por una secuencia de movimientos de las 8 en punto y las 10 en punto. Pero si el último movimiento fue a las 8 en punto (que tiene derecho a ser, ya que podemos hacer nuestros movimientos en cualquier orden), entonces debemos haber pasado por (3,1), cuya distancia es en realidad 2 (como puedes ver de la hoja de referencia original). Entonces, lo que debemos hacer es retroceder un movimiento de las 8 en punto, ahorrando dos movimientos en total.

Hay una optimización similar con el 4 en la parte superior derecha. Aparte de comenzar allí, la única forma de llegar es moviendo las 8 en punto desde (4,3). Eso no está en la hoja de trucos, pero si estuviera allí, su distancia sería 3, porque podríamos tener las 7 en punto a (3,1), que tiene una distancia de solo 2. Entonces, deberíamos retroceder uno Mueva las 8 en punto, y luego avance una 7 en punto.

Entonces, necesitamos agregar un número más a la hoja de referencia:

. . 4
. 2 . 2
0 3 2

(Nota: hay una gran cantidad de optimizaciones de retroceso de (0,1) y (0,2), pero como el solucionador nunca nos llevará allí, no tenemos que preocuparnos por ellas).

Entonces, aquí hay un código de Python para evaluar esto:

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 desea conocer una ruta real, este algoritmo también lo proporciona: es simplemente una sucesión de n7 movimientos de las 7 en punto, seguidos de (o intercalados con) n8 movimientos de las 8 en punto, n10 10- se mueve en punto, y cualquier baile es dictado por la hoja de trucos (que, en sí misma, puede estar en una hoja de trucos).

Ahora: Cómo demostrar que esto es correcto. No es suficiente comparar estos resultados con una tabla de respuestas correctas, porque el problema en sí es ilimitado. Pero podemos decir que, si la distancia del Caballo de un cuadrado s es d, entonces si {m} es el conjunto de movimientos legales de s, la distancia del Caballo de (s + m) debe ser d-1 o d + 1 para todos m. (¿Necesita una prueba de esto?) Además, debe haber al menos uno de esos cuadrados cuya distancia sea d-1, a menos que s sea el origen. Entonces, podemos demostrar la exactitud mostrando que esta propiedad se cumple para cada cuadrado. 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")

Alternativamente, podemos probar la exactitud de cualquier cuadrado s siguiendo la ruta desde s cuesta abajo hasta el origen. Primero, verifique que s sea razonable como se indicó anteriormente, luego seleccione cualquier s + m tal que la distancia (s + m) == d-1. Repetir 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.

Todavía no he estudiado gráficos ... según el problema de implementarlo a través de simplemente matrices, no pude derivar ninguna otra solución que esta. Traté las posiciones no como rangos y archivos (la notación habitual de ajedrez), sino como índices de matriz. FYI, esto es solo para un tablero de ajedrez de 8 * 8. Cualquier consejo de mejora es siempre bienvenido.

* Los comentarios deberían ser suficientes para su comprensión de la lógica. Sin embargo, siempre puede preguntar.

* Comprobado en el compilador DEV-C ++ 4.9.9.2 (Software Bloodshed).

Creo que esto también podría ayudarte ...

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.

PD: Utiliza un poco el BFS sin tener que tomarse la molestia de declarar los nodos y los bordes del gráfico.

Aquí hay una solución para este problema particular implementada en Perl. Mostrará uno de los caminos más cortos; puede haber más de uno en algunos casos.

No utilicé ninguno de los algoritmos descritos anteriormente, pero sería bueno 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));
    }
}

Solo código ruby ​​de del jsfiddle de la respuesta Graeme Pyle arriba , seccionado todo el código adicional y convertido a ruby ​​solo para obtener una solución mediante su algoritmo, parece funcionar. Aún probando sin embargo:

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)

La única intención es ahorrarle tiempo a alguien convirtiendo código si alguien necesita código completo.

aquí está la versión PHP de la función de Jules May

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. Ésta no es una solución perfecta. Hay muchos cambios que realizar en la función de recursividad. Pero este resultado final es perfecto. Intenté 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;
    }

}

Aquí hay una versión C basada en el código Mustafa Serdar Şanlı que funciona para una placa finita:

#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));
    }
}

Pruébelo aquí con prueba contra una solución recursiva