# Generalised multi-dimensional chess knight's moves

Multi-dimensional chess is an extension of normal chess that is played on an 8x8x8x8... "board".

In normal 2D chess, a knight's move is a movement by a vector of $$\ \begin{bmatrix} \pm 2 \\ \pm 1 \end{bmatrix} \$$ or $$\ \begin{bmatrix} \pm 1 \\ \pm 2 \end{bmatrix} \$$, as long as it doesn't cause the knight to go outside the $$\ 8 \$$ by $$\ 8 \$$ bounds.

In $$\ N \$$-dimensional chess, a knight's move is a vector of

$$\begin{bmatrix} \vdots \\ \pm 2 \\ \vdots \\ \pm 1 \\ \vdots \end{bmatrix} \text{or} \begin{bmatrix} \vdots \\ \pm 1 \\ \vdots \\ \pm 2 \\ \vdots \end{bmatrix}$$

where $$\ \begin{bmatrix} \vdots \end{bmatrix} \$$ is any number of $$\ 0 \$$s (such that the vectors are $$\ N \$$ in rank), again as long as it doesn't go outside the $$\ 8^N \$$ bounds.

Given a coordinate vector of length $$\ N \$$, output all possible coordinate vectors that are a knight's move away on an unobstructed $$\ 8^N \$$ chess board.

You should assume the input vector will always be at least 2-dimensional (i.e., $$\ N \ge 2 \$$), and always within the bounds of the board.

## Test-cases

Using 1-indexed coordinates (0-indexed available here)

Input            Output
[1, 8]           [2, 6], [3, 7]
[4, 5]           [5, 7], [3, 7], [3, 3], [5, 3], [6, 6], [2, 6], [2, 4], [6, 4]
[6, 5, 2]        [7, 7, 2], [5, 7, 2], [5, 3, 2], [7, 3, 2], [8, 6, 2], [4, 6, 2], [4, 4, 2], [8, 4, 2], [7, 5, 4], [5, 5, 4], [8, 5, 3], [4, 5, 3], [4, 5, 1], [8, 5, 1], [6, 6, 4], [6, 4, 4], [6, 7, 3], [6, 3, 3], [6, 3, 1], [6, 7, 1]
[5, 1, 3]        [6, 3, 3], [4, 3, 3], [7, 2, 3], [3, 2, 3], [6, 1, 5], [4, 1, 5], [4, 1, 1], [6, 1, 1], [7, 1, 4], [3, 1, 4], [3, 1, 2], [7, 1, 2], [5, 2, 5], [5, 2, 1], [5, 3, 4], [5, 3, 2]
[8, 8, 8]        [7, 6, 8], [6, 7, 8], [7, 8, 6], [6, 8, 7], [8, 7, 6], [8, 6, 7]
[1, 1, 1, 1]     [2, 3, 1, 1], [3, 2, 1, 1], [2, 1, 3, 1], [3, 1, 2, 1], [2, 1, 1, 3], [3, 1, 1, 2], [1, 2, 3, 1], [1, 3, 2, 1], [1, 2, 1, 3], [1, 3, 1, 2], [1, 1, 2, 3], [1, 1, 3, 2]
[7, 3, 8, 2]     [8, 5, 8, 2], [6, 5, 8, 2], [6, 1, 8, 2], [8, 1, 8, 2], [5, 4, 8, 2], [5, 2, 8, 2], [6, 3, 6, 2], [8, 3, 6, 2], [5, 3, 7, 2], [8, 3, 8, 4], [6, 3, 8, 4], [5, 3, 8, 3], [5, 3, 8, 1], [7, 2, 6, 2], [7, 4, 6, 2], [7, 1, 7, 2], [7, 5, 7, 2], [7, 4, 8, 4], [7, 2, 8, 4], [7, 5, 8, 3], [7, 1, 8, 3], [7, 1, 8, 1], [7, 5, 8, 1], [7, 3, 7, 4], [7, 3, 6, 3], [7, 3, 6, 1]
[8, 4, 7, 8, 4]  [7, 6, 7, 8, 4], [7, 2, 7, 8, 4], [6, 5, 7, 8, 4], [6, 3, 7, 8, 4], [7, 4, 5, 8, 4], [6, 4, 8, 8, 4], [6, 4, 6, 8, 4], [7, 4, 7, 6, 4], [6, 4, 7, 7, 4], [7, 4, 7, 8, 6], [7, 4, 7, 8, 2], [6, 4, 7, 8, 5], [6, 4, 7, 8, 3], [8, 3, 5, 8, 4], [8, 5, 5, 8, 4], [8, 6, 8, 8, 4], [8, 2, 8, 8, 4], [8, 2, 6, 8, 4], [8, 6, 6, 8, 4], [8, 3, 7, 6, 4], [8, 5, 7, 6, 4], [8, 2, 7, 7, 4], [8, 6, 7, 7, 4], [8, 5, 7, 8, 6], [8, 3, 7, 8, 6], [8, 3, 7, 8, 2], [8, 5, 7, 8, 2], [8, 6, 7, 8, 5], [8, 2, 7, 8, 5], [8, 2, 7, 8, 3], [8, 6, 7, 8, 3], [8, 4, 6, 6, 4], [8, 4, 8, 6, 4], [8, 4, 5, 7, 4], [8, 4, 8, 8, 6], [8, 4, 6, 8, 6], [8, 4, 6, 8, 2], [8, 4, 8, 8, 2], [8, 4, 5, 8, 5], [8, 4, 5, 8, 3], [8, 4, 7, 7, 6], [8, 4, 7, 7, 2], [8, 4, 7, 6, 5], [8, 4, 7, 6, 3]
[3, 4, 2, 5, 7, 3, 2, 2, 4, 3, 6, 4, 5, 7, 5, 8, 8, 8, 7, 8, 3, 7, 5, 8, 7]  https://gist.github.com/pxeger/8a44daec42d34d9507d7ca6431e2a9fc


## Rules

• Your code does not need to practically handle very high $$\ N \$$, but it must work in theory for all $$\ N \$$
• You may use 0-indexed ($$\ [0, 7] \$$) or 1-indexed ($$\ [1, 8] \$$) input and output, but this must be consistent
• You may optionally take a second input, an integer $$\ N \$$, which is the length of the vector and the number of dimensions
• You may use any standard I/O method
• Standard loopholes are forbidden
• This is , so the shortest code in bytes wins
• Sandbox Jun 14, 2021 at 6:50
• You may roll back my edit if not suitable. I'm not sure when I'm supposed to edit other people's posts as it's my first time editing with the privilege.
– user100690
Jun 14, 2021 at 7:25
• @ophact I just rolled back that one because I don't think it makes the test-cases any clearer. I mainly edit posts to fix typos and formatting or occasionally tweak wording. See codegolf.stackexchange.com/help/editing Jun 14, 2021 at 7:27
• I'll remember that in the future; haven't really edited others' posts before without suggesting.
– user100690
Jun 14, 2021 at 7:28

# Ruby, 93 81 bytes

->a,n{w=*1..8;w.product(*[w]*~-n).select{|r|r.zip(a).sum{|x,y|(x-y).abs*8/3}==7}}


Try it online!

### Quickly explained - old version

Generate all possible positions as vectors of N numbers between 1 and 8, then check the differences between each vector and the starting position, the sorted array of absolute values of the components must be [<bunch of 0s ...>, 1, 2]

### And then:

(Thanks @dingledooper): If we multiply the differences by 8 and divide them by 3, the vector becomes [<bunch of 0s>, 2, 5] and its sum is unequivocally 7, no other combination of numbers can produce the same sum, so we can simplify the check a lot and shave off 12 bytes.

# JavaScript (V8), 114 bytes

0-indexed. Prints all valid vectors.

v=>v.map((x,i)=>v.map((y,j)=>j>i&&(g=n=>n--&&g(n,(V=[...v],x-(V[i]=n&7))**2+(y-(V[j]=n>>3))**2-5||print(V)))(64)))


Try it online!

### How?

Let $$\v\$$ be the input vector of length $$\N\$$.

For each pair $$\(i,j),\:0\le i and each value $$\n\in[0\dots 63]\$$, we compute:

$$X=n \bmod 8\\ Y=\lfloor n/8 \rfloor\\ V=[v_0,\:\dots,v_{i-1},\:X,\:v_{i+1},\:\dots,v_{j-1},\:Y,\:v_{j+1},\:\dots,\:v_{N-1}]$$

We print the output vector $$\V\$$ if:

$$(v_i-X)^2+(v_j-Y)^2=5$$

# Jelly, 13 bytes

8RṗLạṢ¹ƇØ½ƑʋƇ


Try it online!

## Explanation

8RṗLạṢ¹ƇØ½ƑʋƇ   Main monadic link
8R              Range from 1 to 8
ṗ             To the Cartesian power of
L              the length of the input
Ƈ   Filter by
ʋ    (
ạ             Absolute difference with the input
Ṣ            Sort
Ƈ          Filter by
¹             identity
Ø½Ƒ       Equals [1,2]?
ʋ    )


It's a shame that ṗ doesn't automatically convert the left argument to a range, like other list functions…

• It's especially unfortunate considering that one of said other list functions is p itself... Jan 10, 2022 at 4:21

# 05AB1E, 12 bytes

Takes N as first input and the current position as second input.

8LIãʒα0K{2LQ


Try it online!

8L            # push the range [1 .. 8]
Iã          # all N-tuples of integers in [1 .. 8]
ʒ         # only keep those for which ...
α        # ... the element-wise absolute difference to the current position
0K      # ... without zeros
{     # ... sorted ascending
2L   # ... and [1, 2]
Q  # ... are equal


# Wolfram Language (Mathematica), 47 bytes

Array[#~Norm~1#.#&@*List,0#+8,1-#]~Position~15&


Try it online!

Returns a list of coordinates. The product of the taxicab distance and the squared Euclidean distance can only be 15 on knight's moves.

Array[           &@*List,0#+8    ]                  for the whole chessboard
,1-#                   offset so the input location is 0:
#~Norm~1                                          taxicab distance times
#.#                                       squared Euclidean distance
~Position~15&     find 15s


### Wolfram Language (Mathematica), 64 55 bytes

x/.Solve[0<x<9&&!#-2<x<#+2,x∈#~Sphere~√5,Integers]&


Try it online!

Returns a list of coordinates. x/. could be omitted (-3 bytes) for a slightly uglier output format (a list of {x->coord}s).

x/.Solve[                 ,             ,Integers]& integer coordinates which are
x∈#~Sphere~√5            √5 away from the input,
0<x<9                                      inside the chess board,
&&!#-2<x<#+2                          and 2 away on some dimension.



# Python, 115 bytes

lambda p,N:[i for i in[[*map(int,f"{j:0{N}o}")]for j in range(8**N)]if~-sum((k-l)**(2*N)for k,l in zip(i,p))==4**N]

Attempt This Online!

#### Old Python, 116 bytes

lambda p,N:[i for i in[[*map(int,f"{j:0{N}o}")]for j in range(8**N)]if 4**N+1==sum((k-l)**(2*N)for k,l in zip(i,p))]

Attempt This Online!

Takes the 0-based list and its length as inputs. Uses octal representation as a poor-man's itertools.product to generate all squares and then filters out the bad ones using a high-p Minkowski distance.

• TIL you can nest {} expressions in format specifiers Jan 7, 2022 at 9:49

e!(o:x)=[z|o==0,z<-[e:x,-e:x]]++map(o:)(e!x)
_!_=[]
k p=filter(all(elem[0..7]))$zipWith(+)p<$>([0<\$p]>>=(1!)>>=(2!))


Try it Online!

-13 bytes thanks to Wheat Wizard

-1 byte thanks to pxeger

• This can easily be shortened to 119 Jan 9, 2022 at 14:30
• _![]=[] can be shortened to just _!_=[] May 28, 2022 at 8:51

# Python 3.8 (pre-release), 134 119 bytes

lambda v,d:[i for i in product(*[range(8)]*d)if[1,2]==sorted(abs(x-y)for x,y in zip(i,v)if x-y)]
from itertools import*


Try it online!

• Generate all possible coordinates.
• Then, compute he list of the absolute difference between our vector and the coordinate.
• Remove all 0 in this list an verify that the remaining contains exactly 1 and 2

Thanks to @ovs for -15 bytes

• You can shorten the condition a bit by removing all zeros from the absolute differences and then checking for equality with [1,2]: 119 bytes
– ovs
Jun 14, 2021 at 14:33
• @ovs You're totally right. I didn't thought of that. Thanks :) Jun 14, 2021 at 14:45

# Pari/GP, 66 bytes

a->forvec(b=[[1,8]|i<-a],norml2(a-b)==5&&normlp(a-b)==2&&print(b))


Try it online!

For input $$\a\$$, find all coordinate vectors $$\b\$$ on the chessboard such that the $$\l_2\$$ distance (Euclidean distance) between $$\a\$$ and $$\b\$$ is $$\\sqrt{5}\$$, and the $$\l_\infty\$$ distance (Chebyshev distance) between $$\a\$$ and $$\b\$$ is $$\2\$$.

# JavaScript (V8), 96 bytes

a=>{for(i=a>>2;++i<a*4;)/[09]/.test(i)|[...a].map((n,j)=>s+=((i+'')[j]-n)**2,s=0)^s^5||print(i)}


Try it online!

Input is a string, for example, [6, 5, 2] is inputed as "652". Output each answer per line to stdout.

# Python 2, 104 bytes

lambda a:[i for i in range(a/4,a*4)if sum((q in'90')*6+(int(p)-int(q))**2for p,q in zip(a,i*10))==5]


Try it online!

Input [6, 5, 2] as an integer 652. Output list of integers.

# Charcoal, 46 bytes

ＦＬθＦＬθＦ⊗¬⁼ικＦ²⊞υＥθ⁺ν⁺×⁼ξι⊗∨λ±¹×⁼ξκ∨μ±¹ＩΦυ⁼ι﹪ι⁸


Try it online! Link is to verbose version of code. 0-indexed. Outputs using Charcoal's default array output of each element on its own line with separate results double-spaced from each other. Explanation:

ＦＬθ


Loop over the possible N dimensions for the 2-step part of the knight's move.

ＦＬθ


Loop over the possible N dimensions for the 1-step part of the knight's move.

Ｆ⊗¬⁼ικ


Loop over 2-step moves toward or away from the origin, but only if different dimensions were chosen.

Ｆ²


Loop over 1-step moves toward or away from the origin.

⊞υＥθ⁺ν⁺×⁼ξι⊗∨λ±¹×⁼ξκ∨μ±¹


Calculate the coordinates of the move.

ＩΦυ⁼ι﹪ι⁸


Output only those coordinates which stay within the bounds of the board.

# Python 3, 230 210 bytes

v=lambda n:sum([[m.insert(i,0)or m for m in v(n-1)]for i in range(n)],[])if n>2else[[i,j//i]for i in[-2,-1,1,2]for j in[2,-2]]
k=lambda*l:[p for p in[[*map(sum,zip(l,m))]for m in v(len(l))]if min(p)>0<9>max(p)]


Thanks to Jakque for the -20

Try it online!

Python 3 solution that does not use any external modules and calculates the possible moves by recursivly generating all possible moves before filtering out impossible ones.

The original (non-golfed) code that I wrote:

def moves(n): # n is the number of dimensions
out = []
if n > 2: # If higher then base dimension
for i in range(n): # For each possible location that the 0 can be
temp = [move for move in moves(n-1)] # Generate the previous dimension's move list
for j in range(len(temp)): # Insert 0 in the same location for all moves
temp[j].insert(i, 0)
out.extend(temp) # Add to master move list
else: # Base case, if n = 2
out = [[1, 2], [1, -2], [-1, 2], [-1, -2],
[2, 1], [2, -1], [-2, 1], [-2, -1]]

return out

def knights_moves(*loc):
n = len(loc) # count dimensions

# Debug
print(f"n: {n} n-out: {len(moves(n))}")

pos_list = []
for move in moves(n): # Iterate through every move
pos_list.append([a+b for a, b in zip(loc, move)]) # Add move elementwise with original location

filtered = [pos for pos in pos_list if min(pos) > 0 and max(pos) < 9] # Check if the move ins

return filtered


Any suggestions/tips or questions are very welcome!

• There is a small error in your code : & is not exaclty a and operator, it is a bitwise operator, meaning it will do a and operation on each digit of the integer. For example 6 & 3 = 0b110 & 0b11 = 0b10 = 2. Here you do the operation 0&max(p) wich is equal to 0. The code don't check if max is bellow 9. Hopefully there is a fix : min(pos)>0<9>max(pos). Since 0 is always bellow 9, this is equivalent to min(pos)>0 and 9>max(pos) Jun 18, 2021 at 8:12
• also n>2 else => n>2else saves 1 byte, [[1,2],[1,-2],[-1,2],[-1,-2],[2,1],[2,-1],[-2,1],[-2,-1]] =>[[i,j]for i in[-2,-1,1,2]for j in[3-i*i,i*i-3]] (not the same order , but all the elements are here) saves 10 bytes and finnaly [a+b for a,b in zip(l,m)] => [*map(sum,zip(l,m))] saves 5 bytes Jun 18, 2021 at 8:17
• edit : [[i,j//i]for i in[-2,-1,1,2]for j in[2,-2]] is even shorter by 4 bytes Jun 18, 2021 at 8:49
• thanks Jakque, I'll add those in the morning, I did try some way of having the base case moves but my best effort was still the same length as the original Jun 18, 2021 at 13:21

f a=[x|x<-mapM(\_->[1..8])a,sum[n^2*9div4|n<-zipWith(-)a x]==11]