Jugada de caballero de ajedrez en un tablero de 8x8

Question

Recientemente he mostrado cierto interés en el ajedrez, y me pregunto si hay una solución para el siguiente problema:

En un tablero de ajedrez de 8x8, etiquetando las celdas con números del 1 al 8, ¿hay alguna manera de encontrar los movimientos mínimos que un caballero debe hacer para llegar a un destino determinado? Por ejemplo, en esta configuración:

  1  2  3  4  5  6  7  8
1
2
3
4
5
6
7
8

Si la posición de inicio es la célula $(1, 1)$ y el destino es $(5, 1)$ podemos ir allí con sólo dos movimientos. El primero en $(3, 2)$ y luego en $(5, 1)$ . No hay restricciones que se noten, podemos suponer que hay un tablero de ajedrez de 8x8 en blanco con sólo una noche en él. Sólo quiero saber que si la posición de partida es $(x_1, y_1)$ y el destino es $(x_2, y_2)$ ¿cuántos movimientos se requieren para ir allí (el mínimo)? ¿Alguien tiene experiencia en esto?

Answer 1

Siguiendo la sugerencia de @BarakManos:

Paso 1: Construir un gráfico en el que cada casilla del tablero de ajedrez sea un vértice.

Paso 2: Colocar una arista entre vértices exactamente cuando hay un solo movimiento de caballo de una casilla a otra.

Paso 3: El algoritmo de Dijkstra es un algoritmo para encontrar la longitud de un camino entre dos vértices (cuadrados). Es muy clásico en teoría de grafos, estructuras de datos y algoritmos.

Answer 2

En realidad hay pocas restricciones que se deban al borde del tablero. Una de ellas (o el único caso) es el movimiento de A1 a B2, por ejemplo. Normalmente se necesitarían dos movimientos para mover un paso en diagonal, pero aquí esa solución te movería del tablero. En su lugar, tendrías que moverte primero a C2 o B3 y luego es un movimiento de un paso a lo largo de la fila o del archivo que son tres pasos.

Entonces, debería ser bastante sencillo sólo probar las soluciones. La razón por la que no se obtienen tantas restricciones de las aristas es que habrá soluciones similares por simetría que evitarían la restricción de las aristas.

Escribí un programa utilizando el siguiente algoritmo:

1. Crear una matriz de cuadrados
2. Escriba cero en una matriz, luego para cada $j\in\mathbb N$ :
3. Para cada casilla con valor $j$ poner $j+1$ en todas las casillas vacías alcanzables por un salto de caballo. Repita la operación para las sucesivas $j$ 's hasta que se llene el tablero.

Bueno, esto es algo parecido al algoritmo de Dijkstra (excepto que en este caso las distancias son todas una). Mi programa confirmó que en un tablero de ajedrez normal el único caso en que las aristas son una restricción es el caso mencionado.

Answer 3

Dijkstra es exagerado aquí.
Construir el gráfico como se ha dicho en otras respuestas, ya que el peso de las aristas se suman uno, se puede encontrar el camino más corto en un gráfico simple utilizando Búsqueda en primer lugar de la amplitud en O(V+E) en lugar de O(E + VlogV) como en Dijkstra.
Si quiere encontrar todos los caminos más cortos de todas las celdas a todas las demás, puede utilizar Floyd-Warshall ya que sus vértices en el gráfico son 64, esto se puede calcular en O(n^3).
Debo añadir que entre Dijkstra, BFS y Floyd-Warshall , Floyd-Warshall es el más fácil de aplicar . y es factible utilizarlo hasta un tablero de 10*10.

---

En este video puede encontrar más información sobre la búsqueda del camino más corto mediante BFS
Y en esta wiki puedes aprender sobre el algoritmo Floyd-Warshall.

Answer 4

Un poco tarde para contestar, pero he creado un código y lo he implementado para ver los resultados:

0 3 2 3 2 3 4 5
3 4 1 2 3 4 3 4 
2 1 4 3 2 3 4 5 
3 2 3 2 3 4 3 4 
2 3 2 3 4 3 4 5 
3 4 3 4 3 4 5 4 
4 3 4 3 4 5 4 5
5 4 5 4 5 4 5 6

El caballo está en la posición 0 del tablero de 8 por 8, y tarda como máximo 6 movimientos en llegar a cualquier parte (la esquina opuesta).

La simetría de un tablero de ajedrez es de 8 pliegues, ya que puede reflejarse a lo largo de cualquier diagonal a dos posiciones únicas, o girar 90 grados a cuatro posiciones únicas. Esto significa que hay 8 rebanadas del tablero. He decidido publicar las otras 9 posiciones que son distintas bajo esta transformación, para que el intercambio de pilas tenga la información real sobre esto para el futuro. Bajo estas permutaciones y simetrías, se puede averiguar cuál es la distancia del caballo a cualquier posición del tablero.

Son los siguientes:

Posiciones de borde:

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

Siguiente fila:

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

En el centro:

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

Lo siento si esto no es muy bonito. Todo lo que tienes que hacer para poner el caballo en otra posición es girar tu tablero o voltear los números a lo largo de una diagonal. Tenga en cuenta que, como la mayoría de los jugadores de ajedrez ya saben, los caballos son mucho más poderosos en el centro del tablero.