Generalised multi-dimensional chess knight's moves

Question

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.

Task

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 code-golf, so the shortest code in bytes wins

Answer 1

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.

Answer 2

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<j<N\$ 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$$

Answer 3

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…

Answer 4

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

Answer 5

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.

Answer 6

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.

Answer 7

Haskell, 132 119 118 Bytes

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

Answer 8

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

Answer 9

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\$.

Answer 10

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.

Answer 11

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.

Answer 12

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!

Answer 13

Haskell, 66 bytes

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

Try it online!

Essentially a port of G B and dingledooper's Ruby answer.