chess - por - Pregunta de ajedrez de camino más corto de Knight
ranking mundial ajedrez (16)
He estado practicando para una próxima competencia de programación y me he topado con una pregunta en la que estoy completamente desconcertado. Sin embargo, siento que es un concepto que debería aprender ahora en lugar de cruzar los dedos para que nunca surja.
Básicamente, se trata de una pieza de caballero en un tablero de ajedrez. 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 he tratado con las cosas más cortas del camino, y ni siquiera sé por dónde empezar. ¿Qué lógica utilizo para abordar esto?
PD: si tiene alguna relevancia, quieren que completes la habilidad de movimiento normal del Caballero permitiéndole también moverse a las cuatro esquinas del cuadrado que crean las rutas de movimiento de un Caballero si están en el centro del tablero.
Solución de los primeros principios en Python
Primero encontré este problema en una prueba de codificación. Me dieron 30 minutos para resolverlo. ¡Me llevó mucho más tiempo llegar a este resultado! El problema era: cuántos movimientos le toma a un caballo pasar de 0,0 a x, y usando solo movimientos legales de Caballero. xey fueron más o menos ilimitados (por lo que no estamos hablando aquí de un simple tablero de ajedrez 8x8).
Querían una solución O (1). Quería una solución donde el programa claramente resolviera el problema (es decir, quería algo más obviamente que el patrón de Graeme, los patrones tienen la costumbre de romper donde no estás mirando), y realmente quería no tener que depender de un fórmula sin par, como en la solución de Mustafa
Entonces, aquí está mi solución, por lo que vale. Comienza, como han hecho otros, al notar que la solución es simétrica respecto de los ejes y las diagonales, por lo que solo debemos resolver 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 las cercanías del origen. Llegaremos a lo que en realidad significa ''vicinty'' a su debido tiempo, pero por ahora, vamos a escribir algunas soluciones en una hoja de trucos (origen en la parte inferior izquierda):
2 1 4 3
3 2 1 2
0 3 2 3
Entonces, dados x, y en la grilla, podemos leer el número de movimientos hacia el origen.
Si hemos comenzado fuera de la grilla, tenemos que volver a trabajar en ello. 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 abrirse camino hacia la hoja de trucos usando una serie de movimientos de las 8 en punto (es decir: (-2, -1) movimientos). 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 de las 7 en punto, y si está por debajo de la línea media, necesitaremos una sucesión de 8 en punto y 10 o ''reloj se mueve. Dos cosas a tener en cuenta aquí:
- Estas secuencias son probadamente las trayectorias más cortas. (¿Quieres que lo pruebe, o es obvio?)
- Solo nos importa la cantidad de movimientos. Podemos mezclar y combinar los movimientos en cualquier orden.
Entonces, veamos los movimientos de arriba de la línea media. Lo que estamos reclamando es que:
(dx; dy) = (2,1; 1,2) (n8; n7) (notación de matriz, sin composición matemática - columna de vector (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)
Estoy afirmando que dx, dy será aproximadamente (x, y), entonces (x-dx, y-dy) estará cerca del origen (cualquiera que sea la ''vecindad'').
Las dos líneas en el 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 debajo de la línea media se mueve (x, y) a uno de (0,0), (1,0), (2,0) o (1,1).
(¿Le gustaría obtener pruebas de esto?) Entonces, la distancia del Caballero será la suma de n7, n8, n10 y hoja de trucos [x-dx, y-dy], y nuestra hoja de trucos se reduce a esto:
. . 4
. 2 .
0 3 2
Ahora, este no es el final de la historia. Mira el 3 en la fila inferior. Las únicas formas en que podemos alcanzar esto son:
- Empezamos allí, o
- Nos mudamos allí, por una secuencia de movimientos de las 8 en punto y de las 10 en punto. Pero si el último movimiento fue un reloj de las 8 (que tiene derecho a ser, ya que podemos hacer nuestros movimientos en cualquier orden), entonces debemos haber pasado (3,1), cuya distancia es en realidad 2 (como se puede ver de la hoja de trucos original). Entonces, lo que debemos hacer es retroceder un movimiento de las 8 en punto, salvando dos movimientos en total.
Hay una optimización similar que se puede tener con el 4 en la parte superior derecha. Además de comenzar allí, la única manera de llegar a eso es mediante un movimiento de 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 (3,1), que tiene una distancia de solo 2. Entonces, deberíamos retroceder una Se mueve a las 8 en punto, y luego avanza un 7 en punto.
Entonces, necesitamos agregar un número más a la hoja de trampa:
. . 4
. 2 . 2
0 3 2
(Nota: hay una gran cantidad de optimizaciones de retroceso desde (0,1) y (0,2) pero dado que el solucionador nunca nos llevará allí, no tenemos que preocuparnos por ellos).
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 quieres saber una ruta real, entonces este algoritmo también lo proporciona: es simplemente una sucesión de n7 movimientos de las 7 en punto, seguidos por (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 probar que esto es correcto. No es suficiente comparar estos resultados con una tabla de respuestas correctas, porque el problema en sí no tiene límites. Pero podemos decir que, si la distancia del caballero de un cuadrado s es d, entonces si {m} es el conjunto de movimientos legales de s, la distancia del caballero 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 es d-1, a menos que s sea el origen. Por lo tanto, podemos demostrar la corrección 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 corrección de cualquier cuadrado s persiguiendo la ruta desde s hacia abajo hasta el origen. En primer lugar, compruebe s por razonabilidad como arriba, luego seleccione cualquier s + m tal que la distancia (s + m) == d-1. Repite hasta llegar al origen.
Howzat?
Aquí hay una solución correcta de O (1), pero para el caso donde el caballero se mueve como un caballero de ajedrez solamente, y en un tablero de ajedrez infinito:
https://jsfiddle.net/graemian/5qgvr1ba/11/
La clave para encontrar esto es observar los patrones que surgen cuando dibujas el tablero. En el siguiente diagrama, 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 de amplitud para encontrarlo):
Debido a que la solución es simétrica a través de los ejes y las diagonales, solo he dibujado el caso x> = 0 y y> = x.
El bloque inferior izquierdo 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 incrementales de 4
- Las diagonales rojas "primarias" (se ejecutan arriba a la izquierda a abajo a la derecha, como una barra invertida)
- Las diagonales verdes "secundarias" (la misma orientación que el rojo)
(Asegúrese de ver ambos conjuntos de diagonales como arriba a la izquierda a abajo a la derecha. Tienen un conteo de movimiento constante. Las diagonales superior-izquierda arriba-derecha son mucho más complejas).
Puedes 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);
}
Ver el violín para los otros casos.
Tal vez hay patrones más simples o más elegantes que me perdí? Si es así, me encantaría verlos. En particular, observo algunos patrones diagonales en las cajas verticales azules, pero no los he explorado. De todos modos, esta solución aún satisface la restricción O (1).
Aquí hay una solución para este problema en particular implementado en Perl. Mostrará uno de los caminos más cortos: podría haber más de uno en algunos casos.
No usé 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__
Aquí tienes 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 el camino más corto 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:
- como idiota, dijo que usar el http://en.wikipedia.org/wiki/A*_algorithm puede ser más rápido.
- la manera más rápida es precalcular todas las distancias y guardarla en una matriz completa de 8x8. bueno, yo llamaría a eso trampa, y solo funciona porque el problema es pequeño. Pero a veces las competiciones verifican qué tan rápido se ejecuta su programa.
- El punto principal es que si se está preparando para una competencia de programación, debe conocer algoritmos comunes, incluido el de Dijkstra. Un buen punto de partida es leer
Introduction to AlgorithmsISBN 0-262-03384-4. O puede intentar wikipedia, http://en.wikipedia.org/wiki/List_of_algorithms
Creo que esto también podría ayudarte ...
NumWays(x,y)=1+min(NumWays(x+-2,y-+1),NumWays(x+-1,y+-2));
y usar la 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.
La respuesta O (1) anterior [ https://.com/a/8778592/4288232 de Mustafa Serdar Şanlı] no funciona realmente. (Marque (1,1) o (3,2) o (4,4), a un lado para los casos de borde obvio de (1,0) o (2,2)).
A continuación se muestra una solución mucho más fea (Python), que funciona (con "pruebas" añadidas):
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 tienes que hacer es pensar en los movimientos posibles del caballo como un gráfico, donde cada posición en el tablero es un nodo y lo posible se mueve a otra posición como un borde. No es necesario el algoritmo de dijkstra, ya que cada borde tiene el mismo peso o distancia (todos son igual de fáciles o cortos de hacer). Puede hacer una búsqueda BFS desde su punto de partida hasta llegar a la posición final.
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 ) que figura en las here día 1 de SACO 2007 .
En primer lugar, quiero agradecer a Graeme Pyle por su muy buena visualización que me ayudó a corregir la fórmula.
Por alguna razón (tal vez por simplificación o belleza o simplemente por un error) movieron el signo minus al operador de floor , como resultado obtuvieron el floor(-a) != -floor(a) for any a fórmula equivocado 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 casos de esquina (1,0) y (2,2), que no son conformes al patrón y 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: El jQuery se usa solo para la ilustración, para el código ver la función de distance .
Sí, Dijkstra y BFS obtendrán la respuesta, pero creo que el contexto de ajedrez de este problema proporciona conocimientos que pueden ofrecer una solución que es 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 desde (x0, y0) a (x1, y1) utilizando solo los pasos candidatos (+ -1, + -2), (+ -2, + -1) y (+ -2) , + -2), como se describe en la pregunta PS
Aquí está la nueva observación: dibuja un cuadrado con esquinas (x-4, y-4), (x-4, y + 4), (x + 4, y-4), (x + 4, y + 4) . Este conjunto (llámalo S4) contiene 32 puntos. El camino más corto desde cualquiera de estos 32 puntos a (x, y) requiere exactamente dos movimientos .
El camino más corto 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 o | y1-y0 |> 4, la ruta más corta desde (x0, y0) a (x1, y1) es exactamente dos movimientos mayores que la ruta más corta desde (x0, y0) hasta S4. Y el último problema se puede resolver rápidamente con iteración directa.
Deje N = max (| x1-x0 |, | y1-y0 |). Si N> = 4, entonces la ruta más corta desde (x0, y0) a (x1, y1) tiene pasos de ceil (N / 2) .
Solo el código ruby de la respuesta jsfiddle de Graeme Pyle , rayado todo el código extra y convertido restante en ruby solo para obtener una solución por su algoritmo, parece funcionar. Todavía estoy probando:
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)
Only intention is to save someone some time converting code if anyone needs full code.
EDITAR: Ver la respuesta de Simon , donde arregló la fórmula presentada aquí.
En realidad, hay una fórmula O (1)
Esta es una imagen que hice para visualizarla (los cuadrados que un caballero puede alcanzar en el N ° 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 la cantidad de movimientos necesarios para ir del cuadrado ( 0 , 0 ) al cuadrado ( 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 fue hecha en SACO 2007 Día 1
Y las soluciones están here
Here is a C version based on Mustafa Serdar Şanlı code that works for a finit board:
#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));
}
}
Test it here with proof against a recursive solution
here''s the PHP version of Jules May''s function
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. Esta no es una solución perfecta. Hay muchos cambios que hacer en la función de recursión. Pero este resultado final es perfecto. Traté de 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;
}
}
/*
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 matrices simples, no podría derivar otra solución que no sea esta. Traté las posiciones no como rangos y archivos (la notación de ajedrez habitual), sino como índices de matriz. FYI, esto es solo para un tablero de ajedrez 8 * 8. Cualquier consejo de mejora siempre es bienvenido.
* Los comentarios deberían ser suficientes para su comprensión de la lógica. Sin embargo, siempre puedes preguntar.
* Comprobado el compilador DEV-C ++ 4.9.9.2 (Bloodshed Software).
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 */
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));
}
}