Where can the knight be in N moves?

Question

This is Hole-3 from The Autumn Tournament of APL CodeGolf. I am the original author of the problem there, and thus allowed to re-post it here.

---

Given:

1. a number of turns (please state if no movements is 0, otherwise we'll assume it is called 1) and

2. a list of one or more starting positions (in any form, e.g. 0 or 1 indexed coordinates or 64 consecutive numbers/characters or A1–H8 – state which), on an 8-by-8 chessboard,

return (in any order) the list of unique positions (in the same format as the input) that knight(s) can be at after the given number of turns.

• Each knight must move with every turn, but you do not have to worry about multiple knights occupying the same square.

• A knight can only move to the positions marked with X relative to its current position, marked with ♞:
  

Examples (1-indexed coordinates)

1 move from [[1,1]]: [[2,3],[3,2]]

2 moves from [[1,1]]: [[1,1],[1,3],[1,5],[2,4],[3,1],[3,5],[4,2],[4,4],[5,1],[5,3]]

1 move from [[1,1],[5,7]]: [[2,3],[3,2],[3,6],[3,8],[4,5],[6,5],[7,6],[7,8]]

2 moves from [[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]]

0 moves from [[3,4]]: [[3,4]]

Answer 1

Wolfram Language (Mathematica), 45 bytes

Because the other solution is incorrect (see Martin's comment below), so I decide to post my solution:

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

Try it online!

Ultimate infix notation...

Takes 2 input, the first one is a list of numbers in range [1,64] describe the starting positions of the knight, the second one is the number of steps.

This solution relies on the extreme convenience of Mathematica builtin functions:

• AdjacencyList may takes a list of vertices on its right side, and return a list of vertices adjacent to any of those, already removed duplicates and sorted.
• KnightTourGraph is a builtin. Not surprise.
• Nest takes arguments in order Nest[f, expr, n], which we can splat the ## over its right side as Nest[f, ##].
• And finally, Mathematica parse a~b~c~d~e as (a~b~c)~d~e, so no square bracket is necessary. Without infix notation and flatten ##, it would be Nest[AdjacencyList[KnightTourGraph[8, 8], #] &, #, #2]&.

Answer 2

JavaScript (ES7), 99 bytes

Input/output format: squares indices in [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

Test cases

This snippet includes two helper functions to translate from and to the format provided by the 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)))

How?

A move from (x,y) to (X,Y) is a valid knight move if we have either:

• |x-X| = 1 and |y-Y| = 2, or
• |x-X| = 2 and |y-Y| = 1

By squaring instead of using absolute values, this can be expressed as:

• (x-X)² = 1 and (y-Y)² = 4, or
• (x-X)² = 4 and (y-Y)² = 1

Because 1 and 4 are the only perfect squares that give 5 when XOR'd together, we have a valid knight move if:

(x-X)² XOR (y-Y)² XOR 5 = 0

We apply this formula to each square p = 8y + x on the board and each knight square P = 8Y + X to deduce the new possible knight target squares, and recursively repeat this process n times.

Answer 3

Octave , 69 bytes

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

Online Demo!

The input/output is the configuration of the board at start/end as a binary 8*8 matrix.

Explanation:

For n steps repeat morphological dilation of the board with the following mask:

01010
10001
00100
10001
01010

Answer 4

Retina, 147 102 bytes

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

Try it online! Takes input as an 8x8 board of :s with the knights marked with Ns, with a digit for the number of turns on the next line (it makes no sense to have more than 9 turns, but if you insist I can support it for an extra byte). Note that the output contains additional white space. Edit: Saved 45 bytes thanks to @MartinEnder. Explanation: The first stage converts the number of turns to unary, but using tab characters, so that they don't get matched later by accident, while the second stage adds some spaces to the right of the board to stop the regexes from wrapping across the edge. The third stage replaces all Ns and :s that are a knight's move away from an N with an n while the fourth stage deletes any remaining Ns, changes the ns to Ns, and subtracts 1 from the move count. This repeats until the move count is zero.

Answer 5

Jelly, 29 bytes

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

Try it online!

0-indexed coordinates. Almost certain this is suboptimal.

-1 byte thanks to user202729

Explanation

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

Answer 6

05AB1E, 27 25 bytes

Thanks to Emigna for saving 2 bytes!

Uses 1-indexed coordinates.

Code:

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

Uses the 05AB1E encoding. Try it online!

Explanation:

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

This gives us the following array:

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

Which are the deltas of the moves of the knight.

            δ+             #   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

Answer 7

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

Try it online!

Input / Output format

The input/output is represented as bits in a long (64 bits): set bits mean a horse is present, unset bits mean no horse. Example:

// [[0, 0]]
0b00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001L

Explanations

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

Credits

• 19 bytes saved thanks to Nevay!
• Reused the (X-x)²+(Y-y)²==5 trick from Arnauld's JavaScript answer
• 1 more byte saved thanks to Nevay in the new algorithm!
• 7 more bytes saved thanks to Nevay again by switching from int[] to 64-bits long.

Answer 8

Jelly, 29 28 bytes

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

Try it online!

Number of turns is through STDIN, and squares is an argument.

This ties @HyperNeutrino's Jelly solution, but with a different approach.

Now beating @HyperNeutrino by 1 whole byte!

Any suggestions to knock off some bytes are wanted!

Link 1 (The chessboard)

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

Link 2 (Move generation)

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

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

Answer 9

Husk, 18 bytes

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

Uses 1-based indexing of squares and steps. Try it online!

Explanation

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.

Answer 10

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

Have to use a named lambda for the recursion. Not sure if that's disqualifying. Pass in starting positions as 0-indexed square number list. 0 counts as no moves.

Answer 11

R, 145 183 134 bytes

This is the result of Giuseppe's excellent golfing of my initial not-too-golfy algo (see comment below)

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

Try it online!

Input and output are 1...64 based. Takes a vector of position using the 1...64 notation. Maps it to a 1:576 notation, that is a super-board made of nine boards. In this notation, at each iteration, each knight should be able to move by +/- 22,26,47,49 Return future positions back in the 1...64 notation, excluding those that fall off the central board. The TIO example displays the result using an 8x8 matrix.