Algoritmo de gráfico que involucra ajedrez: posibles caminos en k movimientos

Question

Estoy tratando de resolver un problema de algoritmo que involucra al ajedrez.

Supongamos que tengo un rey en A8 y quiero moverlo a H1 (solo con movimientos permitidos). ¿Cómo puedo saber cuántas posibilidades (caminos) hay haciendo exactamente cualquier movimiento k dado? (por ejemplo, ¿Cuántas rutas/posibilidades hay si quiero mover el rey de la A8 a H1 con 15 movimientos?)

Una solución trivial es verlo como un problema gráfico y utilizar cualquier ruta de búsqueda de conteo algoritmo estándar cada movimiento tiene un costo 1. Entonces, digamos que quiero mover mi rey de A8 a H1 en 10 movimientos. Simplemente buscaría todas las rutas que sumen hasta 10.

Mi pregunta es, si hay otras maneras más inteligentes y eficientes de hacer esto? También me preguntaba si podría haber algo más "matemático" y sencillo para encontrar este número y no tan "algorítmico" y "de fuerza bruta".

Answer 1

Este es un problema directo de programación O (N^3).

asignar simplemente una matriz 3D como sigue:

Let Z [x] [y] [k] sea el número de movimientos de k pasos para llegar al destino desde la posición (x, y) a bordo.

Los casos base son:

foreach x in 0 to 7, 
    foreach y in 0 to 7, 
     Z[x][y][0] = 0 // forall x,y: 0 ways to reach H1 from 
         // anywhere else with 0 steps 

Z[7][7][0] = 1 // 1 way to reach H1 from H1 with 0 steps 

El caso recursivo es:

foreach k in 1 to K, 
    foreach x in 0 to 7, 
     foreach y in 0 to 7, 
      Z[x][y][k+1] = Z[x-1][y][k] 
       + Z[x+1][y][k] 
       + Z[x][y-1][k] 
       + Z[x][y+1][k] 
       + ...; // only include positions in 
        // the summation that are on the board 
        // and that a king can make 

Su respuesta es entonces:

return Z[0][0][K]; // number of ways to reach H1(7,7) from A8(0,0) with K moves 

(No es una forma más rápida de hacer esto en O (n^2) descomponiendo los movimientos en dos conjuntos de movimientos horizontales y verticales y luego combinando estos y multiplicando por el número de i nterleavings.)

Ver esta pregunta ya responder: No of ways to walk M steps in a grid

Answer 2

.......E <-end 
........ 
........ 
........ 
........ 
........ 
........ 
S....... <-start 

Desafortunadamente no puede usar "ningún algoritmo de búsqueda de ruta estándar" porque sus rutas pueden no ser las más cortas. Tendría que utilizar específicamente una búsqueda ingenua que considere todas las rutas (por ejemplo, profundidad primero o ancho de primer plano).

Sin embargo, debido a que no se preocupan de cómo que tienes a una ficha, se puede utilizar una técnica llamada programación dinámica. Para cada lugar (i, j), el número de maneras de llegar allí en n se mueve (vamos a llamarlo maneras _{i, j} (n)) es:

maneras _{i, j} (n) = maneras _{i-1, j} (n-1) + maneras _{i + 1, j} (n-1) + maneras _{i, j-1} (n-1) + maneras _{i, j + 1} (n-1) + formas _{i + 1, j + 1} (n-1) + formas _{i-1, j + 1} (n-1) + formas _{i + 1, j-1} (n-1) + maneras _{i-1, j-1} (n-1)

es decir, el rey puede pasar de cualquiera de los cuadrados adyacentes en 1 mover:

maneras _{i, j} (n) = suma _{vecinos (i, j)} (formas _vecino (n-1))

de este modo se haría, por ejemplo, en python:

SIZE = 8 

cache = {} 
def ways(pos, n): 
    r,c = pos # row,column 
    if not (0<=r<SIZE and 0<=c<SIZE): 
     # off edge of board: no ways to get here 
     return 0 
    elif n==0: 
     # starting position: only one way to get here 
     return 1 if (r,c)==(0,0) else 0 
    else: 
     args = (pos,n) 
     if not args in cache: 
      cache[args] = ways((r-1,c), n-1) + ways((r+1,c), n-1) + ways((r,c-1), n-1) + ways((r,c+1), n-1) + ways((r-1,c-1), n-1) + ways((r+1,c-1), n-1) + ways((r+1,c-1), n-1) + ways((r+1,c+1), n-1) 
     return cache[args] 

Demostración:

>>> ways((7,7), 15) 
1074445298 

La técnica anterior se denomina memoization, y es más fácil de escribir que la programación dinámica, ya que no es necesario que pensar realmente en el orden en que se hacen las cosas.Se puede ver la caché de crecer mientras llevamos a cabo una serie de consultas cada vez más grandes:

>>> cache 
{} 
>>> ways((1,0), 1) 
1 
>>> cache 
{((1, 0), 1): 1} 
>>> ways((1,1), 2) 
2 
>>> cache 
{((0, 1), 1): 1, ((1, 2), 1): 0, ((1, 0), 1): 1, ((0, 0), 1): 0, ((2, 0), 1): 0, ((2, 1), 1): 0, ((1, 1), 2): 2, ((2, 2), 1): 0} 
>>> ways((2,1), 3) 
5 
>>> cache 
{((1, 2), 1): 0, ((2, 3), 1): 0, ((2, 0), 2): 1, ((1, 1), 1): 1, ((3, 1), 1): 0, ((4, 0), 1): 0, ((1, 0), 1): 1, ((3, 0), 1): 0, ((0, 0), 1): 0, ((2, 0), 1): 0, ((2, 1), 1): 0, ((4, 1), 1): 0, ((2, 2), 2): 1, ((3, 3), 1): 0, ((0, 1), 1): 1, ((3, 0), 2): 0, ((3, 2), 2): 0, ((3, 2), 1): 0, ((1, 0), 2): 1, ((4, 2), 1): 0, ((4, 3), 1): 0, ((3, 1), 2): 0, ((1, 1), 2): 2, ((2, 2), 1): 0, ((2, 1), 3): 5} 

(en Python, se puede también utilizar un decorador @cached o @memoized para evitar tener que escribir el código completo en el último else: bloque. Otros idiomas tienen otras formas de realizar automáticamente la memorización.)

Lo anterior era un enfoque de arriba hacia abajo. A veces puede producir pilas muy grandes (su pila crecerá con n). Si quieres ser súper eficiente para evitar el trabajo innecesario, puedes hacer un acercamiento ascendente, donde simulas todas las posiciones que el rey podría tener, para 1 paso, 2 pasos, 3 pasos, ...:

SIZE = 8 
def ways(n): 
    grid = [[0 for row in range(8)] for col in range(8)] 
    grid[0][0] = 1 

    def inGrid(r,c):    
     return all(0<=coord<SIZE for coord in (r,c)) 
    def adjacentSum(pos, grid): 
     r,c = pos 
     total = 0 
     for neighbor in [(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)]: 
      delta_r,delta_c = neighbor 
      (r2,c2) = (r+delta_r,c+delta_c) 
      if inGrid(r2,c2): 
       total += grid[r2][c2] 
     return total 

    for _ in range(n): 
     grid = [[adjacentSum((r,c), grid) for r in range(8)] for c in range(8)] 
     # careful: grid must be replaced atomically, not element-by-element 

    from pprint import pprint 
    pprint(grid) 
    return grid 

demostración:

>>> ways(0) 
[[1, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0]] 

>>> ways(1) 
[[0, 1, 0, 0, 0, 0, 0, 0], 
[1, 1, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0]] 

>>> ways(2) 
[[3, 2, 2, 0, 0, 0, 0, 0], 
[2, 2, 2, 0, 0, 0, 0, 0], 
[2, 2, 1, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0]] 

>>> ways(3) 
[[6, 11, 6, 4, 0, 0, 0, 0], 
[11, 16, 9, 5, 0, 0, 0, 0], 
[6, 9, 6, 3, 0, 0, 0, 0], 
[4, 5, 3, 1, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0]] 

>>> ways(4) 
[[38, 48, 45, 20, 9, 0, 0, 0], 
[48, 64, 60, 28, 12, 0, 0, 0], 
[45, 60, 51, 24, 9, 0, 0, 0], 
[20, 28, 24, 12, 4, 0, 0, 0], 
[9, 12, 9, 4, 1, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0]] 

Answer 3

usted podría utilizar una matriz de adyacencia. Si multiplicas esa matriz consigo mismo, obtienes la cantidad de caminos de Punto a Punto. Ejemplo:

Graph: Gráfico de K3 completo: A < -> B < -> C < -> A

Matrix:

[0 ; 1 ; 1] 
[1 ; 0 ; 1] 
[1 ; 1 ; 0] 

Caminos para la longitud 2: M * M

[2 ; 1 ; 1] 
[1 ; 2 ; 1] 
[1 ; 1 ; 2] 

La longitud 3 sería entonces M * M * M

[2 ; 3 ; 3] 
[3 ; 2 ; 3] 
[3 ; 3 ; 2]