20
\$\begingroup\$

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 , so the shortest code in bytes wins
\$\endgroup\$
4
  • \$\begingroup\$ Sandbox \$\endgroup\$
    – pxeger
    Jun 14 '21 at 6:50
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – user100690
    Jun 14 '21 at 7:25
  • \$\begingroup\$ @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 \$\endgroup\$
    – pxeger
    Jun 14 '21 at 7:27
  • \$\begingroup\$ I'll remember that in the future; haven't really edited others' posts before without suggesting. \$\endgroup\$
    – user100690
    Jun 14 '21 at 7:28

13 Answers 13

6
\$\begingroup\$

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.

\$\endgroup\$
0
5
\$\begingroup\$

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

\$\endgroup\$
5
\$\begingroup\$

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…

\$\endgroup\$
1
  • 1
    \$\begingroup\$ It's especially unfortunate considering that one of said other list functions is p itself... \$\endgroup\$ Jan 10 at 4:21
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ TIL you can nest {} expressions in format specifiers \$\endgroup\$
    – pxeger
    Jan 7 at 9:49
3
\$\begingroup\$

Haskell, 132 119 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

\$\endgroup\$
1
2
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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 \$\endgroup\$
    – ovs
    Jun 14 '21 at 14:33
  • \$\begingroup\$ @ovs You're totally right. I didn't thought of that. Thanks :) \$\endgroup\$
    – Jakque
    Jun 14 '21 at 14:45
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 46 bytes

FLθFLθF⊗¬⁼ικF²⊞υEθ⁺ν⁺×⁼ξι⊗∨λ±¹×⁼ξκ∨μ±¹IΦυ⁼ι﹪ι⁸

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:

FLθ

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

FLθ

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

F⊗¬⁼ικ

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

F²

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

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

Calculate the coordinates of the move.

IΦυ⁼ι﹪ι⁸

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

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
4
  • \$\begingroup\$ 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) \$\endgroup\$
    – Jakque
    Jun 18 '21 at 8:12
  • \$\begingroup\$ 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 \$\endgroup\$
    – Jakque
    Jun 18 '21 at 8:17
  • \$\begingroup\$ edit : [[i,j//i]for i in[-2,-1,1,2]for j in[2,-2]] is even shorter by 4 bytes \$\endgroup\$
    – Jakque
    Jun 18 '21 at 8:49
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ Jun 18 '21 at 13:21
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.