To jest Hole-3 z jesiennego turnieju APL CodeGolf . Jestem oryginalnym autorem problemu i dlatego mogę go ponownie opublikować tutaj.

Dany:

1. liczba zwojów (proszę podać, jeśli żaden ruch nie wynosi 0, w przeciwnym razie założymy, że nazywa się to 1) i

2. lista jednej lub więcej pozycji początkowych (w dowolnej formie, np. 0 lub 1 indeksowanych współrzędnych lub 64 kolejnych liczb / znaków lub A1 – H8 - stan, który), na szachownicy 8 na 8,

zwróć (w dowolnej kolejności) listę unikalnych pozycji (w tym samym formacie co dane wejściowe), w których rycerze mogą znajdować się po określonej liczbie tur.

• Każdy rycerz musi się poruszać z każdą turą, ale nie musisz się martwić, że wielu rycerzy zajmuje ten sam kwadrat.

• Rycerz może poruszać się tylko na pozycje oznaczone X w stosunku do swojej aktualnej pozycji, oznaczonej with:
  

Przykłady (współrzędne 1-indeksowane)

1przenieść z [[1,1]]: [[2,3],[3,2]]

2przenosi z [[1,1]]: [[1,1],[1,3],[1,5],[2,4],[3,1],[3,5],[4,2],[4,4],[5,1],[5,3]]

1przenieść z [[1,1],[5,7]]: [[2,3],[3,2],[3,6],[3,8],[4,5],[6,5],[7,6],[7,8]]

2przenosi z [[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]]

0przenosi z [[3,4]]: [[3,4]]

Wolfram Language (Mathematica) , 45 bajtów

Ponieważ inne rozwiązanie jest niepoprawne (patrz komentarz Martina poniżej), więc postanawiam opublikować moje rozwiązanie:

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

Wypróbuj online!

Ostateczna notacja infix ...

Przyjmuje 2 dane wejściowe, pierwsza to lista liczb w zasięgu [1,64]opisująca początkowe pozycje rycerza, druga to liczba kroków.

To rozwiązanie opiera się na wyjątkowej wygody wbudowanych funkcji Mathematica:

• AdjacencyListmoże pobrać listę wierzchołków po prawej stronie i zwrócić listę wierzchołków sąsiadujących z dowolnymi z nich, już usunięte duplikaty i posortowane .
• KnightTourGraphjest wbudowany. Nic dziwnego.
• Nestporządkuje argumenty Nest[f, expr, n], które możemy przelać na ##prawą stronę jako Nest[f, ##].
• I na koniec, parsuj Mathematica a~b~c~d~ejako (a~b~c)~d~e, więc nawias kwadratowy nie jest konieczny. Bez notacji infix i spłaszczenia ##byłoby Nest[AdjacencyList[KnightTourGraph[8, 8], #] &, #, #2]&.

JavaScript (ES7), 99 bajtów

Format wejściowy / wyjściowy: wskaźniki kwadratów w [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

Przypadki testowe

Ten fragment zawiera dwie funkcje pomocnicze do tłumaczenia zi do formatu dostarczonego przez 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)))

W jaki sposób?

Ruch z (x, y) do (X, Y) jest prawidłowym ruchem rycerza, jeśli mamy:

• | xX | = 1 i | yY | = 2 lub
• | xX | = 2 i | yY | = 1

Kwadrat zamiast wartości bezwzględnych można wyrazić jako:

• (xX) ² = 1 i (yY) ² = 4 lub
• (xX) ² = 4 i (yY) ² = 1

Ponieważ 1 i 4 to jedyne idealne kwadraty, które dają 5, gdy XOR razem, mamy ważny ruch rycerza, jeśli:

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

Stosujemy tę formułę do każdego kwadratu p = 8y + x na planszy i każdego kwadratu rycerza P = 8Y + X, aby wydedukować nowe możliwe kwadraty docelowe rycerza i powtarzamy ten proces n razy.

Oktawa, 69 bajtów

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

Demo online!

Wejście / wyjście to konfiguracja płytki na początku / końcu jako binarna matryca 8 * 8.

Wyjaśnienie:

Dla nkroków powtórz morfologiczne rozszerzenie planszy za pomocą następującej maski:

01010
10001
00100
10001
01010

Siatkówka , 147 102 bajtów

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

Wypróbuj online! Pobiera dane jako tablica 8x8 :s z rycerzami oznaczonymi Ns, z cyfrą liczby zwojów w następnym wierszu (nie ma sensu mieć więcej niż 9 zwojów, ale jeśli nalegasz, mogę je wesprzeć dodatkową bajt). Zauważ, że dane wyjściowe zawierają dodatkowe białe znaki. Edycja: Zapisano 45 bajtów dzięki @MartinEnder. Objaśnienie: Pierwszy etap konwertuje liczbę zwojów na jednoargumentowe, ale przy użyciu znaków tabulacji, dzięki czemu nie zostaną one przypadkowo dopasowane później, podczas gdy drugi etap dodaje pewne spacje po prawej stronie planszy, aby zapobiec zawijaniu wyrażeń regularnych krawędź. Trzeci etap zastępuje wszystkie NS i :S, które są ruch rycerski od Nze związkiem na czwarty etap usuwa wszelkie pozostałe NS, zmienians do Ns i odejmuje 1 od liczby ruchów. To się powtarza, aż liczba ruchów wyniesie zero.

Galaretka , 29 bajtów

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

Wypróbuj online!

Współrzędne 0-indeksowane. Niemal pewne, że jest to nieoptymalne.

-1 bajt dzięki użytkownikowi 202729

Wyjaśnienie

+þ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 bajtów

Dzięki Emigna za uratowanie 2 bajtów!

Wykorzystuje współrzędne 1-indeksowane.

Kod:

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

Wykorzystuje kodowanie 05AB1E . Wypróbuj online!

Wyjaśnienie:

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

To daje nam następującą tablicę:

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

Które są deltami ruchów rycerza.

            δ+             #   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 bajtów

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

Muszę użyć nazwanej lambda do rekurencji. Nie jestem pewien, czy to dyskwalifikuje. Przechodzić w pozycjach początkowych jako lista numerów kwadratowych z indeksowaniem 0 0 liczy się jako brak ruchów.

Java (OpenJDK 8) , 124 bajty

(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;}

Wypróbuj online!

Format wejścia / wyjścia

Dane wejściowe / wyjściowe są reprezentowane jako bity w long(64 bity): ustawione bity oznaczają, że koń jest obecny, a bity nie ustawione oznaczają brak konia. Przykład:

// [[0, 0]]
0b00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001L

Objaśnienia

(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;
}

Kredyty

• 19 bajtów zaoszczędzonych dzięki Nevay!
• Ponownie wykorzystał (X-x)²+(Y-y)²==5sztuczkę z odpowiedzi JavaScript Arnaulda
• Jeszcze 1 bajt zapisany dzięki Nevayowi w nowym algorytmie!
• Jeszcze 7 bajtów zaoszczędzonych dzięki Nevayowi, przechodząc z int[]64-bitowych long.

Galaretka , 29 28 bajtów

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

Wypróbuj online!

Liczba zwojów przechodzi przez STDIN, a kwadraty to argument.

To wiąże rozwiązanie Jelly @ HyperNeutrino, ale z innym podejściem.

Teraz bije @HyperNeutrino o 1 cały bajt!

Potrzebne są wszelkie sugestie dotyczące usunięcia niektórych bajtów!

Link 1 (szachownica)

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

Link 2 (Przenieś generację)

“¦Ʋƈ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)

Link 3 (sprawdzanie kwadratu)

ÇƓ¡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

Łuska , 18 bajtów

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

Wykorzystuje indeksowanie kwadratów i kroków na podstawie 1. Wypróbuj online!

Wyjaśnienie

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 bajtów

Jest to wynik doskonałego grania przez Giuseppe mojego początkowego niezbyt golfowego algo (patrz komentarz poniżej)

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

Wypróbuj online!

Wejścia i wyjścia są oparte na 1 ... 64. Przyjmuje wektor pozycji za pomocą notacji 1 ... 64. Odwzorowuje to na notację 1: 576, czyli super-tablica złożona z dziewięciu tablic. W tej notacji, przy każdej iteracji, każdy rycerz powinien być w stanie poruszać się o +/- 22,26,47,49. Zwrócić przyszłe pozycje z powrotem w notacji 1 ... 64, z wyjątkiem tych, które spadną z planszy. Przykład TIO wyświetla wynik przy użyciu matrycy 8x8.