Este es el hoyo 3 del Torneo de otoño de APL CodeGolf . Soy el autor original del problema allí y, por lo tanto, me permite volver a publicarlo aquí.

Dado:

1. un número de turnos (indique si ningún movimiento es 0, de lo contrario asumiremos que se llama 1) y

2. una lista de una o más posiciones iniciales (en cualquier forma, por ejemplo, 0 o 1 coordenadas indexadas o 64 números / caracteres consecutivos o A1 – H8 - indica cuál), en un tablero de ajedrez de 8 por 8,

devolver (en cualquier orden) la lista de posiciones únicas (en el mismo formato que la entrada) en las que pueden estar los caballeros después del número dado de turnos.

• Cada caballero debe moverse con cada turno, pero no tiene que preocuparse de que múltiples caballeros ocupen el mismo cuadrado.

• Un caballero solo puede moverse a las posiciones marcadas con X en relación con su posición actual, marcadas con ♞:
  

Ejemplos (coordenadas indexadas 1)

1pasar de [[1,1]]: [[2,3],[3,2]]

2se mueve desde [[1,1]]: [[1,1],[1,3],[1,5],[2,4],[3,1],[3,5],[4,2],[4,4],[5,1],[5,3]]

1pasar de [[1,1],[5,7]]: [[2,3],[3,2],[3,6],[3,8],[4,5],[6,5],[7,6],[7,8]]

2se mueve desde [[1,1],[5,7]]: [[1,1],[1,3],[1,5],[1,7],[2,4],[2,6],[2,8],[3,1],[3,3],[3,5],[3,7],[4,2],[4,4],[4,6],[4,8],[5,1],[5,3],[5,5],[5,7],[6,4],[6,6],[6,8],[7,3],[7,7],[8,4],[8,6],[8,8]]

0se mueve desde [[3,4]]: [[3,4]]

Wolfram Language (Mathematica) , 45 bytes

Como la otra solución es incorrecta (vea el comentario de Martin a continuación), decido publicar mi solución:

8~KnightTourGraph~8~AdjacencyList~#&~Nest~##&

Pruébalo en línea!

Notación de infijo definitiva ...

Toma 2 entradas, la primera es una lista de números dentro del rango que [1,64]describe las posiciones iniciales del caballero, la segunda es el número de pasos.

Esta solución se basa en la extrema comodidad de las funciones incorporadas de Mathematica:

• AdjacencyListmay toma una lista de vértices en su lado derecho y devuelve una lista de vértices adyacentes a cualquiera de ellos, ya eliminados, duplicados y ordenados .
• KnightTourGraphEs un incorporado. No es sorpresa
• Nesttoma los argumentos en orden Nest[f, expr, n], que podemos salpicar ##sobre su lado derecho como Nest[f, ##].
• Y, por último, Mathematica analiza a~b~c~d~ecomo (a~b~c)~d~e, por lo que no es necesario un corchete. Sin notación infija y aplanar ##, sería Nest[AdjacencyList[KnightTourGraph[8, 8], #] &, #, #2]&.

JavaScript (ES7), 99 bytes

Formato de entrada / salida: índices cuadrados en [0 ... 63] .

f=(a,n)=>n--?f([...Array(64).keys()].filter(p=>!a.every(P=>(p%8-P%8)**2^((p>>3)-(P>>3))**2^5)),n):a

Casos de prueba

Este fragmento incluye dos funciones auxiliares para traducir desde y hacia el formato proporcionado por el OP.

f=(a,n)=>n--?f([...Array(64).keys()].filter(p=>!a.every(P=>(p%8-P%8)**2^((p>>3)-(P>>3))**2^5)),n):a

c2s = a => a.map(c => (c[0] - 1) * 8 + c[1] - 1)
s2c = a => JSON.stringify(a.map(s => [(s >> 3) + 1, s % 8 + 1]))

console.log(s2c(f(c2s([[1,1]]), 1)))
console.log(s2c(f(c2s([[1,1]]), 2)))
console.log(s2c(f(c2s([[1,1],[5,7]]), 1)))
console.log(s2c(f(c2s([[1,1],[5,7]]), 2)))
console.log(s2c(f(c2s([[3,4]]), 0)))

¿Cómo?

Un movimiento de (x, y) a (X, Y) es un movimiento de caballero válido si tenemos:

• | xX | = 1 y | aa | = 2 o
• | xX | = 2 y | aa | = 1

Al cuadrar en lugar de usar valores absolutos, esto se puede expresar como:

• (xX) ² = 1 y (yY) ² = 4 , o
• (xX) ² = 4 y (yY) ² = 1

Como 1 y 4 son los únicos cuadrados perfectos que dan 5 cuando se hacen XOR juntos, tenemos un movimiento válido de caballero si:

(xX) ² XOR (yY) ² XOR 5 = 0

Aplicamos esta fórmula a cada cuadrado p = 8y + x en el tablero y a cada cuadrado de caballero P = 8Y + X para deducir los nuevos cuadrados posibles de objetivo de caballero, y repetimos este proceso de manera recursiva n veces.

Octava, 69 bytes

function a=f(a,n,b=~a)for k=1:n;a=b&imdilate(a,de2bi(")0#0)"-31));end

Demo en línea!

La entrada / salida es la configuración de la placa al inicio / final como una matriz binaria 8 * 8.

Explicación:

Para los npasos, repita la dilatación morfológica del tablero con la siguiente máscara:

01010
10001
00100
10001
01010

Retina , 147 102 bytes

.$
$*	
¶
 ¶
{s`((?<=N(....|.{11}|.{13})?.{7})|(?=.{8}(....|.{11}|.{13})?N))\S(?=.*	)
n
Ts`	Nn`_:N`.*¶	

Pruébalo en línea! Toma la entrada como una tabla de 8x8 de :s con los caballeros marcados con Ns, con un dígito para el número de vueltas en la siguiente línea (no tiene sentido tener más de 9 vueltas, pero si insiste, puedo apoyarlo por un extra byte). Tenga en cuenta que la salida contiene espacio en blanco adicional. Editar: Guardado 45 bytes gracias a @MartinEnder. Explicación: La primera etapa convierte el número de turnos a unario, pero usando caracteres de tabulación, para que no se emparejen más tarde por accidente, mientras que la segunda etapa agrega algunos espacios a la derecha del tablero para evitar que las expresiones regulares se envuelvan el borde. La tercera etapa reemplaza todos Nlos :sys que se alejan de un caballero Ncon un ntiempo, mientras que la cuarta etapa elimina cualquier Ns restante , cambia elnsaNs, y resta 1 del conteo de movimientos. Esto se repite hasta que el conteo de movimientos es cero.

Jalea , 29 bytes

+þ1,2Œ!×þ1,-p`¤¤Ẏ¤Ẏ⁼%8$$ÐfQµ¡

Pruébalo en línea!

Coordenadas indexadas a 0. Casi seguro que esto es subóptimo.

-1 byte gracias al usuario202729

Explicación

+þ1,2Œ!×þ1,-p`¤¤Ẏ¤Ẏ⁼%8$$ÐfQµ¡  Main Link
+þ                             Addition Table (all pairs using + as combining function) with
  1,2Œ!×þ1,-p`¤¤Ẏ¤             All knight moves:
  1,2                          [1, 2]
     Œ!                        All permutations ([1, 2], [2, 1])
       ×þ                      Product Table (all pairs using × as combining function) with
         1,-p`¤                [1, 1], [1, -1], [-1, 1], [-1, -1]
         1,-                   [1, -1]
            p`                 Cartestian Product with itself
               ¤               All knight moves (in a nested array) as a nilad
                Ẏ¤             Tighten (flatten once); all knight moves in a (semi-)flat array
                        Ðf     Keep elements where
                   ⁼%8$$       The element equals itself modulo 8 (discard all elements out of the range)
                          Q    Remove Duplicates
                           µ   Start new monadic chain (essentially, terminates previous chain)
                            ¡  Repeat n times; n is implicitly the second input (right argument)

05AB1E , 27 25 bytes

¡Gracias a Emigna por guardar 2 bytes!

Utiliza coordenadas indexadas 1.

Código:

F•eĆ•SÍü‚Dí«δ+€`Ùʒ{`9‹*0›

Utiliza la codificación 05AB1E . Pruébalo en línea!

Explicación:

F                          # Do the following <input_1> times..
 •eĆ•SÍ                    #   Push [-1, -2, 1, 2, -1]
       ü‚                  #   Pairwise pairing: [[-1, -2], [-2, 1], [1, 2], [2, -1]]
         D                 #   Duplicate the array
          í                #   Reverse each element
           «               #   Concatenate to the previous array

Esto nos da la siguiente matriz:

[[-1, -2], [-2, 1], [1, 2], [2, -1], [-2, -1], [1, -2], [2, 1], [-1, 2]]

Cuáles son los deltas de los movimientos del caballero.

            δ+             #   Addition vectorized on both sides
              €`           #   Flatten each element
                Ù          #   Uniquify
                 ʒ         #   Keep elements which..
                  {`9‹     #     Has a maximum element smaller than 9
                      *0›  #     And a minimum element larger than 0

Python 3, 105 bytes

p=lambda g,i:i and list(set(p([x+y for x in g for y in[6,10,15,17,-6,-10,-15,-17]if 0<=x+y<64],i-1)))or g

Tiene que usar una lambda con nombre para la recursión. No estoy seguro si eso es descalificador. Pase en posiciones iniciales como lista de números cuadrados indexados a 0. 0 cuenta como sin movimientos.

Java (OpenJDK 8) , 124 bytes

(m,p)->{for(;m-->0;)for(long a=p,i=p=0,j;i<64;i++)for(j=64;j-->0;)p|=(p=i%8-j%8)*p+(p=i/8-j/8)*p==5?(a>>i&1)<<j:0;return p;}

Pruébalo en línea!

Formato de entrada / salida

La entrada / salida se representa como bits en a long(64 bits): los bits establecidos significan que hay un caballo, los bits no establecidos significan que no hay caballo. Ejemplo:

// [[0, 0]]
0b00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001L

Explicaciones

(m, p) -> {                          // Lambda. No currying because m and p are modified
 for(;m-->0;)                        // For each move
  for(long a=p,i=p=0,j;i<64;i++)     // Declare variables, move p to a, create a new p and loop on bits of a.
   for(j=64;j-->0;)                  // Loop on bits of p.
    p |=                             // Assign to p a value.
     (p=i%8-j%8)*p+(p=i/8-j/8)*p==5  // If i -> j is a valid horse move, see Arnauld's JavaScript answer for full explanations
      ? (a>>i&1)<<j                  // Assign the presence of the horse (i-th bit of a) to the resulting board (j-th bit of p).
      : 0;                           // Else it's not a valid horse move
 return p;
}

Créditos

• ¡19 bytes guardados gracias a Nevay!
• Reutilizó el (X-x)²+(Y-y)²==5truco de la respuesta de JavaScript de Arnauld
• ¡1 byte más guardado gracias a Nevay en el nuevo algoritmo!
• 7 bytes más guardados gracias a Nevay nuevamente al cambiar de int[]64 bits long.

Jalea , 29 28 bytes

8Rp`
“¦Ʋƈ2’D_2ṡ2+€µẎ
ÇƓ¡f1£Q

Pruébalo en línea!

El número de turnos es a través de STDIN, y los cuadrados son un argumento.

Esto vincula la solución Jelly de @ HyperNeutrino, pero con un enfoque diferente.

¡Ahora venciendo a @HyperNeutrino por 1 byte entero!

¡Se necesitan sugerencias para eliminar algunos bytes!

Enlace 1 (El tablero de ajedrez)

8Rp`
8R   = The list [1,2,3,4,5,6,7,8]
  p` = cartesian multiplied with itself (this results in the chessboard)

Enlace 2 (generación de movimiento)

“¦Ʋƈ2’D_2ṡ2+€µẎ
“¦Ʋƈ2’          = the number 103414301
      D         = converted into a list of digits
       _2       = subtract two from each element
         ṡ2     = overlapping pairs
           +€   = add to the list of squares
             µ  = Make sure the next part isn't treated as a right argument
              Ẏ = Tighten the list (Reducing the depth by one)

Enlace 3 (verificación cuadrada)

ÇƓ¡f1£Q
ÇƓ¡     = Repeat link #2 the requested amount of times
   f1£  = Remove everything not a member of link #1 (not on the chess board)
      Q = Make sure squares don't appear more than once

Casco , 18 bytes

u!¡ṁö`fΠR2ḣ8=5ṁ□z-

Utiliza la indexación basada en 1 de cuadrados y pasos. Pruébalo en línea!

Explicación

u!¡ṁö`fΠR2ḣ8=5ṁ□z-  Implicit inputs, say P=[[1,1],[5,7]] and n=2
  ¡                 Iterate on P:
   ṁö               Map the following function, then concatenate:
                     Argument is a pair, say p=[5,7].
          ḣ8         The range [1,2,..,8]
       ΠR2           Repeat twice, take cartesian product: [[1,1],[1,2],..,[8,8]]
     `f              Filter with this predicate:
                      Argument is a pair, say q=[3,8].
                z-    Zip p and q with difference: [-2,1]
              ṁ□      Sum of squares: 5
            =5        Is it 5? Yes, so [3,8] is kept.
 !                  Take n'th step of the iteration.
u                   Remove duplicates, implicitly print.

R , 145 183 134 bytes

Este es el resultado del excelente juego de golf de Giuseppe de mi algo inicial no demasiado golfista (vea el comentario a continuación)

function(x,n){x=x%/%8*24+x%%8
t=c(49,47,26,22)
t=c(t,-t)
for(i in 1:n)x=intersect(v<-outer(1:8,0:7*24,"+"),outer(x,t,"+"))
match(x,v)}

Pruébalo en línea!

La entrada y la salida están basadas en 1 ... 64. Toma un vector de posición usando la notación 1 ... 64. Lo asigna a una notación de 1: 576, que es un súper tablero compuesto de nueve tableros. En esta notación, en cada iteración, cada caballero debería poder moverse en +/- 22,26,47,49 Devolver posiciones futuras de nuevo en la notación 1 ... 64, excluyendo aquellas que caen del tablero central. El ejemplo TIO muestra el resultado usando una matriz de 8x8.