El gráfico de un caballero en un tablero N-por-N

20

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

donde un caballero puede moverse


Un gráfico de caballero es un gráfico que representa todos los movimientos legales de la pieza de ajedrez de caballero en un tablero de ajedrez. Cada vértice de este gráfico representa un cuadrado del tablero de ajedrez, y cada borde conecta dos cuadrados que se separan el uno del otro.

El gráfico se ve así para una placa estándar de 8 por 8.

ingrese la descripción de la imagen aquí


Desafío:

Dado un entero N , donde 3 ≤ N ≤ 8 , genera una matriz N-por-N que representa un tablero, donde se muestra el número de movimientos posibles desde cada posición. Para N = 8 , la salida será una matriz que muestra los valores de cada vértice en el gráfico anterior.

El formato de salida es flexible. La lista de listas o incluso una lista aplanada, etc., son formatos aceptados.


Conjunto completo de casos de prueba:

--- N = 3 ---
2 2 2
2 0 2
2 2 2
--- N = 4 ---
2 3 3 2
3 4 4 3
3 4 4 3
2 3 3 2
--- N = 5 ---
2 3 4 3 2
3 4 6 4 3
4 6 8 6 4
3 4 6 4 3
2 3 4 3 2
--- N = 6 ---
2 3 4 4 3 2
3 4 6 6 4 3
4 6 8 8 6 4
4 6 8 8 6 4
3 4 6 6 4 3
2 3 4 4 3 2
--- N = 7 ---
2 3 4 4 4 3 2
3 4 6 6 6 4 3
4 6 8 8 8 6 4
4 6 8 8 8 6 4
4 6 8 8 8 6 4
3 4 6 6 6 4 3
2 3 4 4 4 3 2
--- N = 8 ---
2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2

Este es el por lo que gana la solución más corta en cada idioma. ¡Se alientan las explicaciones!

Stewie Griffin
fuente
1
Desafío relacionado para consultar el número de movimientos de caballeros desde un cuadrado en un tablero de 8 * 8.
xnor
¿Puede la salida ser una lista plana de n * n elementos?
xnor
13
¡Esto es literalmente solo casos extremos! :)
Jonathan Allan

Respuestas:

13

MATL , 17 16 bytes

t&l[2K0]B2:&ZvZ+

Pruébalo en línea!

(-1 byte gracias a @Luis Mendo.)

K

K=(0 010 010 010 00 00 010 00 00 00 00 010 00 00 010 010 010 0)

(En relación con el centro de la matriz, cada 1 es un movimiento válido de caballero).

t&l- Forme una matriz nxn de todos los 1 (donde n es la entrada). Deja que esto sea M.

[2K0] - Empuje una matriz que contenga [2, 4, 0] en la pila

B - Convierta todo a binario, relleno con 0s según sea necesario

0 1 0
1 0 0
0 0 0

2:&Zv- Refleje eso en ambas dimensiones, sin repetir la fila / columna final ("indexación de rango simétrico"). Esto nos da la matriz requerida K.

0 1 0 1 0
1 0 0 0 1
0 0 0 0 0
1 0 0 0 1
0 1 0 1 0

Z+- Realice una convolución 2D de K sobre la matriz anterior M ( conv2(M, K, 'same')), sumando los 1 en objetivos de movimiento de caballero legales para cada posición

La matriz de resultados se muestra implícitamente.

sundar - Restablece a Monica
fuente
puede codificar la matriz de convolución como 11043370BP5epero eso no es más corto ...
Giuseppe
8

JavaScript (ES6), 88 bytes

Devuelve una cadena.

n=>(g=k=>--k?[n>3?'-2344-6-6'[(h=k=>k*2<n?~k:k-n)(k%n)*h(k/n|0)]||8:k-4&&2]+g(k):2)(n*n)

Pruébalo en línea!

¿Cómo?

norte=3

20 0

(22220 02222)

3<norte8

(X,y)0 0X<norte0 0y<norteyoX,y

yoX,y=min(X+1,norte-X)×min(y+1,norte-y)

norte=8

(1234 44 432124 46 6886 64 4236 69 912129 96 634 4812dieciséisdieciséis1284 44 4812dieciséisdieciséis1284 436 69 912129 96 6324 46 6886 64 421234 44 4321)

T

T=[0 0,2,3,4 4,4 4,0 0,6 6,0 0,6 6]

0 0

(X,y)

{T(yoX,y)Si yoX,y88de otra manera

JavaScript (ES7), 107 bytes

Una implementación ingenua que realmente intenta todos los movimientos.

n=>[...10**n-1+''].map((_,y,a)=>a.map((k,x)=>~[...b=i='01344310'].map(v=>k-=!a[x-v+2]|!a[y-b[i++&7]+2])+k))

Pruébalo en línea!

Arnauld
fuente
6

Gelatina ,  23 22 14  10 bytes

²ḶdðạP€ċ2)

Un enlace monádico que produce una lista plana, utiliza la idea que utilizó KSab por primera vez en su respuesta de Python , los movimientos de los caballeros tienen "lados" 1 y 2, los únicos factores de 2.

Pruébalo en línea! (el pie de página llama al único enlace del programa y luego formatea el resultado como una cuadrícula)

²Ḷdðạ²§ċ5)5 5

¿Cómo?

²ḶdðạP€ċ2) - Link: integer, n (any non-negative) e.g. 8
²          - square n                                 64
 Ḷ         - lowered range                            [0,    1,    2,    3,    4,    5,    6,    7,    8,    9,    10,   11,   12,   13,   14,   15,   16,   17,   18,   19,   20,   21,   22,   23,   24,   25,   26,   27,   28,   29,   30,   31,   32,   33,   34,   35,   36,   37,   38,   39,   40,   41,   42,   43,   44,   45,   46,   47,   48,   49,   50,   51,   52,   53,   54,   55,   56,   57,   58,   59,   60,   61,   62,   63]
  d        - divmod (vectorises) i.e. x->[x//n,x%n]   [[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[2,0],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[2,7],[3,0],[3,1],[3,2],[3,3],[3,4],[3,5],[3,6],[3,7],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[4,6],[4,7],[5,0],[5,1],[5,2],[5,3],[5,4],[5,5],[5,6],[5,7],[6,0],[6,1],[6,2],[6,3],[6,4],[6,5],[6,6],[6,7],[7,0],[7,1],[7,2],[7,3],[7,4],[7,5],[7,6],[7,7]]
   ð     ) - new dyadic chain for each - call that L ( & e.g. R = [1,2] representing the "2nd row, 3rd column" ...-^ )
    ạ      -   absolute difference (vectorises)       [[1,2],[1,1],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[0,2],[0,1],[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[1,2],[1,1],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[2,2],[2,1],[2,0],[2,1],[2,2],[2,3],[2,4],[2,5],[3,2],[3,1],[3,0],[3,1],[3,2],[3,3],[3,4],[3,5],[4,2],[4,1],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[5,2],[5,1],[5,0],[5,1],[5,2],[5,3],[5,4],[5,5],[6,2],[6,1],[6,0],[6,1],[6,2],[6,3],[6,4],[6,5]]
     P€    -   product of €ach                        [2,    1,    0,    1,    2,    3,    4,    5,    0,    0,    0,    0,    0,    0,    0,    0,    2,    1,    0,    1,    2,    3,    4,    5,    4,    2,    0,    2,    4,    6,    8,    10,   6,    3,    0,    3,    6,    9,    12,   15,   8,    4,    0,    4,    8,    12,   16,   20,   10,   5,    0,    5,    10,   15,   20,   25,   12,   6,    0,    6,    12,   18,   24,   30]
       ċ2  -   count 2s                          6:    ^-...1                  ^-...2                                                                  ^-...3                  ^-...4                        ^-...5      ^-...6
           - )                                                                                                     v-...that goes here
           -   ->                                  -> [2,    3,    4,    4,    4,    4,    3,    2,    3,    4,    6,    6,    6,    6,    4,    3,    4,    6,    8,    8,    8,    8,    6,    4,    4,    6,    8,    8,    8,    8,    6,    4,    4,    6,    8,    8,    8,    8,    6,    4,    4,    6,    8,    8,    8,    8,    6,    4,    3,    4,    6,    6,    6,    6,    4,    3,    2,    3,    4,    4,    4,    4,    3,    2]

22 byter anterior

2RżN$Œp;U$+,ḟ€³R¤Ẉ¬Sðþ

Un programa completo (debido a ³).

Pruébalo en línea! (el pie de página llama al único enlace del programa y luego formatea el resultado como una cuadrícula)

Encuentra todos los movimientos y cuenta aquellos que aterrizan en el tablero probablemente definitivamente superables mediante el cálculo (tal vez superable al cambiar la lógica de "aterrizar en el tablero").

Jonathan Allan
fuente
4

APL (Dyalog Classic) , 18 bytes

+/+/2=×/¨|∘.-⍨⍳2⍴⎕

Pruébalo en línea!

entrada evaluada N

2⍴⎕ dos copias de N

⍳2⍴⎕ Los índices de una matriz N × N - una matriz de vectores de longitud 2

∘.-⍨ restar cada par de índices entre sí, obtener una matriz N × N × N × N

| valor absoluto

×/¨ producto cada

2=donde estan los 2s devolver una matriz booleana (0/1)

Tenga en cuenta que un caballero se mueve ± 1 en un eje y ± 2 en el otro, por lo que el valor absoluto del producto de esos pasos es 2. Como 2 no puede factorizarse de ninguna otra manera, esto es válido solo para movimientos de caballero.

+/+/ suma a lo largo de la última dimensión, dos veces

ngn
fuente
3

RAD , 51 46 39 bytes

{+/(⍵∘+¨(⊖,⊢)(⊢,-)(⍳2)(1¯2))∊,W}¨¨W←⍳⍵⍵

Pruébalo en línea!

¿Cómo?

Cuenta el número de movimientos de caballero válidos para cada casilla al ver qué movimientos de caballero aterrizarían en el tablero:

{+/(⍵∘+¨(⊖,⊢)(⊢,-)(⍳2)(1¯2))∊,W}¨¨W←⍳⍵⍵
 +/                                     - The number of ...
                            ∊,W         - ... in-bounds ...
        (⊖,⊢)(⊢,-)(⍳2)(1¯2)             - ... knight movements ...
   (⍵∘+¨                   )            - ... from ...
{                              }¨¨W←⍳⍵⍵ - ... each square
Zacharý
fuente
3

Brachylog , 65 40 33 bytes

Esto se descompone para N mayor que 9. Entonces estoy feliz de que N solo pueda ir a 8 =)

⟦₅⟨∋≡∋⟩ᶠ;?z{{hQ&t⟦₅↰₁;Qz-ᵐ×ȧ2}ᶜ}ᵐ
  • -25 bytes cambiando a la fórmula de KSab
  • -7 bytes al aplanar la matriz gracias a sundar

Pruébalo en línea!


Brachylog , 44 36 bytes

Este también funciona para un número superior a 9

gP&⟦₅⟨∋≡∋⟩ᶠ;z{{hQ&t⟦₅↰₁;Qz-ᵐ×ȧ2}ᶜ}ᵐ
  • -8 bytes al aplanar la matriz gracias a sundar

Pruébalo en línea!

Kroppeb
fuente
1
También puede usar desde el ⟨∋≡∋⟩principio para generar las coordenadas de la matriz y guardar 7 bytes en general (la salida es una lista plana, que está permitida por OP): ¡ Pruébelo en línea!
sundar - Restablecer Monica
2

Retina , 161 bytes

.+
*
L$`_
$=
(?<=(¶)_+¶_+)?(?=(?<=(¶)_*¶_*)__)?(?<=(¶)__+)?(?=(?<=(¶)_*)___)?_(?=(?<=___)_*(¶))?(?=__+(¶))?(?=(?<=__)_*¶_*(¶))?(?=_+¶_+(¶))?
$.($1$2$3$4$5$6$7$8)

Pruébalo en línea! El enlace incluye casos de prueba. Explicación:

.+
*

Convierte a unario.

L$`_
$=

Liste el valor una vez para cada _valor, es decir, cree un cuadrado.

(?<=(¶)_+¶_+)?
(?=(?<=(¶)_*¶_*)__)?
(?<=(¶)__+)?
(?=(?<=(¶)_*)___)?
_
(?=(?<=___)_*(¶))?
(?=__+(¶))?
(?=(?<=__)_*¶_*(¶))?
(?=_+¶_+(¶))?

Comenzando _en el medio de la expresión regular, intente hacer coincidir el contexto suficiente para determinar si es posible cada uno de los movimientos de los ocho caballeros. Cada patrón captura un solo personaje si la coincidencia tiene éxito. Intenté usar grupos con nombre para que el número de capturas sea directamente igual al resultado deseado, pero eso costó 15 bytes.

$.($1$2$3$4$5$6$7$8)

Concatene todas las capturas exitosas y tome la longitud.

Neil
fuente
2

Wolfram Language (Mathematica) , 34 bytes

Sin embargo, otro Mathematica incorporado.

VertexDegree@KnightTourGraph[#,#]&

Devuelve una lista aplanada.

Pruébalo en línea!

alephalpha
fuente
Realmente hice un comentario bajo el desafío con esta respuesta (aunque no es la sintaxis correcta ya que no sé WL). Lo eliminé después de un rato, ya que pensé que alguien más podría publicarlo como una respuesta real.
Stewie Griffin
1

C (gcc) , 133125 bytes

Esta solución debería funcionar en tableros de cualquier tamaño.

#define T(x,y)(x<3?x:2)*(y<3?y:2)/2+
a,b;f(i){for(a=i--;a--;)for(b=i+1;b--;)printf("%i ",T(a,b)T(i-a,b)T(a,i-b)T(i-a,i-b)0);}

Pruébalo en línea!

Curtis Bechtel
fuente
@ceilingcat Por supuesto, gracias! Pero no veo qué cambia la segunda sugerencia
Curtis Bechtel