Um gráfico de cavaleiro em um tabuleiro N-por-N

20

No xadrez, um cavaleiro só pode se mover para as posições marcadas com X em relação à sua posição atual, marcadas com ♞:

onde um cavaleiro pode se mover


Um gráfico do cavaleiro é um gráfico que representa todos os movimentos legais da peça de xadrez do cavaleiro em um tabuleiro de xadrez. Cada vértice deste gráfico representa um quadrado do tabuleiro de xadrez, e cada aresta conecta dois quadrados que são separados por um cavaleiro.

O gráfico é assim para uma placa 8 por 8 padrão.

insira a descrição da imagem aqui


Desafio:

Dado um número inteiro N , onde 3 ≤ N ≤ 8 , produz uma matriz N por N que representa uma placa, onde é mostrado o número de movimentos possíveis de cada posição. Para N = 8 , a saída será uma matriz que mostra os valores de cada vértice no gráfico acima.

O formato de saída é flexível. Lista de listas ou mesmo uma lista achatada etc. são formatos aceitos.


Conjunto completo de casos de teste:

--- 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

Isso é e a solução mais curta em cada idioma vence. As explicações são incentivadas!

Stewie Griffin
fonte
1
Desafio relacionado para consultar o número de movimentos de cavaleiros de um quadrado em um tabuleiro 8 * 8.
Xnor
A saída pode ser uma lista simples de n * n elementos?
Xnor
13
Isso é literalmente apenas casos extremos! :)
Jonathan Allan

Respostas:

13

MATL , 17 16 bytes

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

Experimente online!

(-1 byte graças a @Luis Mendo.)

K

K=(0101010001000001000101010)

(Em relação ao centro da matriz, cada 1 é um movimento válido de cavaleiro.)

t&l- Forme uma matriz nxn de todos os 1s (onde n é a entrada). Que seja M.

[2K0] - Empurre uma matriz contendo [2, 4, 0] na pilha

B - Converta tudo em binário, preenchendo com 0s conforme necessário

0 1 0
1 0 0
0 0 0

2:&Zv- Espelhe isso nas duas dimensões, sem repetir a linha / coluna final ("indexação simétrica da faixa"). Isso nos dá a matriz K. necessária

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+- Realize convolução 2D de K sobre a matriz anterior M ( conv2(M, K, 'same')), somando os 1s nos alvos de movimento do cavaleiro legal para cada posição

A matriz de resultados é exibida implicitamente.

sundar - Restabelecer Monica
fonte
você pode codificar a matriz de convolução como 11043370BP5emas isso não é mais curta ...
Giuseppe
12

Python 2 , 81 bytes

lambda n:[sum(2==abs((i/n-k/n)*(i%n-k%n))for k in range(n*n))for i in range(n*n)]

Experimente online!

KSab
fonte
8

JavaScript (ES6), 88 bytes

Retorna uma string.

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)

Experimente online!

Quão?

n=3

20

(222202222)

3<n8

(x,y)0x<n0y<nix,y

ix,y=min(x+1,nx)×min(y+1,ny)

Para , isso fornece:n=8

(1234432124688642369121296348121616128448121616128436912129632468864212344321)

A tabela de pesquisa é definida como:T

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

onde representa um slot não utilizado.0

Definimos cada célula para:(x,y)

{T(ix,y)if ix,y88otherwise

JavaScript (ES7), 107 bytes

Uma implementação ingênua que realmente tenta todos os movimentos.

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))

Experimente online!

Arnauld
fonte
6

Geléia ,  23 22 14  10 bytes

²ḶdðạP€ċ2)

Um link monádico que produz uma lista simples - usa a idéia usada pela primeira vez pelo KSab em sua resposta em Python - os movimentos do cavaleiro têm "lados" 1 e 2, os únicos fatores de 2.

Experimente online! (o rodapé chama apenas o link do programa e formata o resultado como uma grade)

Como alternativa, também para 10 bytes, ²Ḷdðạ²§ċ5)(os movimentos do cavaleiro são todos os movimentos possíveis com a distância )5

Quão?

²Ḷ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]

Anterior 22 byter

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

Um programa completo (devido a ³).

Experimente online! (o rodapé chama apenas o link do programa e formata o resultado como uma grade)

Encontra todos os movimentos e conta aqueles que pousam no tabuleiro, provavelmente definitivamente vencíveis pelo cálculo (talvez vencível, alterando a lógica "pousar no tabuleiro").

Jonathan Allan
fonte
4

APL (Dyalog Classic) , 18 bytes

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

Experimente online!

entrada avaliada N

2⍴⎕ duas cópias de N

⍳2⍴⎕ os índices de uma matriz N × N - uma matriz de vetores comprimento-2

∘.-⍨ subtraia cada par de índices um do outro, obtenha uma matriz N × N × N × N

| valor absoluto

×/¨ produto cada

2=onde estão os 2s? retornar uma matriz booleana (0/1)

Observe que um cavaleiro se move ± 1 em um eixo e ± 2 no outro, então o valor absoluto do produto dessas etapas é 2. Como 2 não pode ser fatorado de nenhuma outra maneira, isso é válido apenas para movimentos de cavaleiros.

+/+/ soma ao longo da última dimensão, duas vezes

ngn
fonte
3

RAD , 51 46 39 bytes

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

Experimente online!

Quão?

Conta o número de movimentos de cavaleiro válidos para cada quadrado, vendo quais movimentos de cavaleiro cairiam no tabuleiro:

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

Braquilog , 65 40 33 bytes

Isso divide para N maior que 9. Então, eu estou feliz que N pode ser apenas ir para 8 =)

⟦₅⟨∋≡∋⟩ᶠ;?z{{hQ&t⟦₅↰₁;Qz-ᵐ×ȧ2}ᶜ}ᵐ
  • -25 bytes mudando para a fórmula do KSab
  • -7 bytes achatando a matriz graças ao sundar

Experimente online!


Braquilog , 44 36 bytes

Este também funciona para números superiores a 9

gP&⟦₅⟨∋≡∋⟩ᶠ;z{{hQ&t⟦₅↰₁;Qz-ᵐ×ȧ2}ᶜ}ᵐ
  • -8 bytes achatando a matriz graças ao sundar

Experimente online!

Kroppeb
fonte
1
Você pode usar ⟨∋≡∋⟩desde o início para gerar também as coordenadas da matriz e salvar 7 bytes no geral (a saída é uma lista simples, permitida pelo OP): Experimente online!
sundar - Restabelece Monica
2

Retina , 161 bytes

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

Experimente online! O link inclui casos de teste. Explicação:

.+
*

Converta para unário.

L$`_
$=

Liste o valor uma vez para cada um _no valor, ou seja, crie um quadrado.

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

Começando no _meio da regex, tente combinar o contexto suficiente para determinar se cada um dos oito movimentos do cavaleiro é possível. Cada padrão captura um único caractere se a correspondência for bem-sucedida. Tentei usar grupos nomeados para que o número de capturas fosse igual ao resultado desejado, mas que custasse 15 bytes.

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

Concatene todas as capturas bem-sucedidas e faça a diferença.

Neil
fonte
2

Wolfram Language (Mathematica) , 34 bytes

Mais um Mathematica embutido.

VertexDegree@KnightTourGraph[#,#]&

Retorna uma lista nivelada.

Experimente online!

alefalpha
fonte
Na verdade, fiz um comentário sob o desafio com esta resposta (embora não sintaxe correta, pois não conheço o WL). Eu o removi depois de um tempo, pois achei que alguém poderia querer publicá-lo como uma resposta real.
Stewie Griffin
2

Python 2 , 114 103 92 bytes

lambda n:[sum((d*c>d)+(d*c>c)for d in(y%n,n-y%n-1)for c in(y/n,n-y/n-1))for y in range(n*n)]

Experimente online!

ovs
fonte
1

C (gcc) , 133 125 bytes

Esta solução deve funcionar em qualquer placa de tamanho.

#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);}

Experimente online!

Curtis Bechtel
fonte
@ceilingcat Claro, obrigado! Mas não vejo o que a segunda sugestão muda.
Curtis Bechtel