# Where can the knight be in N moves?

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

• Can chess spaces be inputted and outputted by numbering 0-63 instead of [rank, file]? – Dave Oct 18 '17 at 12:24
• @Dave Sure, why not? Just be consistent with I/O. – Adám Oct 18 '17 at 12:26
• I swear I read this HNQ as "Where the knight be in Ni moves" – Sidney Oct 18 '17 at 15:23
• Pun alert: the notation for knight is N. – Joshua Oct 18 '17 at 15:54
• Can we use 1-based indexing on the number of steps? E.g. [[1,1]], 2 -> [[2,3],[3,2]] – Zgarb Oct 18 '17 at 17:15

# 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]&.
• I don't think there is anything wrong with outgolfing an existing solution. – Adám Oct 18 '17 at 12:58
• Does this work with multiple starting positions? – Adám Oct 18 '17 at 12:58
• Amazing! Now I need to figure out how ti read this... – Dave Oct 18 '17 at 13:17
• This would probably be 17 bytes in the hypothetical Mthmca golfing language. – Michael Stern Oct 18 '17 at 17:02

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

# 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


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

• This is most impressive. Definitely not the right tool for the job! – Adám Oct 18 '17 at 14:09

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

• 0-indexed Jelly? – Adám Oct 18 '17 at 12:21
• @Adám Makes the filtering easier :P – HyperNeutrino Oct 18 '17 at 12:22
• I expect Jelly to be able to do this in under 15 bytes, due to the current record holder in APL does it in 24 characters. – Adám Oct 18 '17 at 12:23
• When you have >= 3 \$, it is likely that you can move it to the previous link and refer back with Ç. – user202729 Oct 18 '17 at 12:23
• @user202729 Oh yeah true, thanks. – HyperNeutrino Oct 18 '17 at 12:24

# 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

• You can use •eĆ•SÍü‚ instead of Ƶ‡4в2ô<D(« to save 2 bytes. – Emigna Oct 18 '17 at 13:49
• @Emigna Ahh, that's clever, thanks! – Adnan Oct 18 '17 at 13:55

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

# 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.
• 169 bytes: (m,p)->{for(;m-->0;){int i=64,a[]=p,x,y,u[]={1,3,5,9,15,19,21,23};for(p=new int[i];i-->0;)for(int z:u)if((((x=i/8+z/5-2)|(y=i%8+z%5-2))&-8)==0)p[x*8+y]|=a[i];}return p;} – Nevay Oct 18 '17 at 21:35
• -1 byte: (m,p)->{for(int i,j,a[],x;m-->0;)for(a=p,p=new int[i=64];i-->0;)for(j=64;j-->0;)p[j]|=(x=i%8-j%8)*x+(x=i/8-j/8)*x==5?a[i]:0;return p;} – Nevay Oct 20 '17 at 22:48
• Thank you @Nevay! Adding code to remove parenthesis/blocks is always nice! ;-) – Olivier Grégoire Oct 21 '17 at 10:31
• -7 bytes by replacing int[] with long: (m,p)->{for(long i,j,a;m-->0;)for(a=p,p=i=0;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;} – Nevay Oct 21 '17 at 12:53
• Cheers, I didn't even think about doing such! Nice job, @Nevay ;-) – Olivier Grégoire Oct 21 '17 at 13:20

# 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


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


# R, 145183 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.

• This seems to fail on the first test case (it returns 4 coordinates instead of 2). – Zgarb Oct 19 '17 at 11:32
• Thank you for pointing it out Zgarb, I think I fixed the issue now – NofP Oct 19 '17 at 14:26
• 154 bytes – Giuseppe Oct 19 '17 at 15:37
• or 148 bytes if you take it in [0...63] notation instead. – Giuseppe Oct 19 '17 at 15:40
• 134 bytes, [1..64]` for input and output. +1, though, this is an excellent answer. – Giuseppe Oct 19 '17 at 21:23