In chess, a knight can only move to the positions marked with X relative to its current position, marked with ♞:

where a knight can move


A Knight's Graph is a graph that represents all legal moves of the knight chess piece on a chessboard. Each vertex of this graph represents a square of the chessboard, and each edge connects two squares that are a knight's move apart from each other.

The graph looks like this for a standard 8-by-8 board.

enter image description here


Challenge:

Given an integer N, where 3 ≤ N ≤ 8, output an N-by-N matrix representing a board, where the number of possible moves from each position is shown. For N = 8, the output will be a matrix showing the values of each vertex in the graph above.

The output format is flexible. List of lists or even a flattened list etc. are accepted formats.


Complete set of test cases:

--- N = 3 ---
2 2 2
2 0 2
2 2 2
--- N = 4 ---
2 3 3 2
3 4 4 3
3 4 4 3
2 3 3 2
--- N = 5 ---
2 3 4 3 2
3 4 6 4 3
4 6 8 6 4
3 4 6 4 3
2 3 4 3 2
--- N = 6 ---
2 3 4 4 3 2
3 4 6 6 4 3
4 6 8 8 6 4
4 6 8 8 6 4
3 4 6 6 4 3
2 3 4 4 3 2
--- N = 7 ---
2 3 4 4 4 3 2
3 4 6 6 6 4 3
4 6 8 8 8 6 4
4 6 8 8 8 6 4
4 6 8 8 8 6 4
3 4 6 6 6 4 3
2 3 4 4 4 3 2
--- N = 8 ---
2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2

This is so the shortest solution in each language wins. Explanations are encouraged!

  • 1
    Related challenge to query the number of knight moves from a square on an 8*8 board. – xnor Aug 11 at 16:16
  • Can the output be a flat list of n*n elements? – xnor Aug 11 at 16:29
  • 13
    This is literally just edge-cases! :) – Jonathan Allan Aug 11 at 17:58

11 Answers 11

MATL, 17 16 bytes

t&l[2K0]B2:&ZvZ+

Try it online!

(-1 byte thanks to @Luis Mendo.)

The main part of the code is creating a matrix \$ K \$ for convolution:

$$ \mathbf{K} = \begin{pmatrix}0&1&0&1&0\\1&0&0&0&1\\0&0&0&0&0\\1&0&0&0&1\\0&1&0&1&0\end{pmatrix} $$

(Relative to the centre of the matrix, each 1 is a valid knight's move.)

t&l - Form a nxn matrix of all 1s (where n is the input). Let this be M.

[2K0] - Push an array containing [2, 4, 0] on stack

B - Convert all to binary, padding with 0s as needed

0 1 0
1 0 0
0 0 0

2:&Zv - Mirror that on both dimensions, without repeating the final row/column ("symmetric range indexing"). This gives us the required matrix K.

0 1 0 1 0
1 0 0 0 1
0 0 0 0 0
1 0 0 0 1
0 1 0 1 0

Z+ - Perform 2D convolution of K over the earlier matrix M (conv2(M, K, 'same')), summing up the 1s at legal knight move targets for each position

Result matrix is displayed implicitly.

  • you can encode the convolution matrix as 11043370BP5e but that's not any shorter... – Giuseppe Aug 11 at 21:38

Python 2, 81 bytes

lambda n:[sum(2==abs((i/n-k/n)*(i%n-k%n))for k in range(n*n))for i in range(n*n)]

Try it online!

JavaScript (ES6), 88 bytes

Returns a string.

n=>(g=k=>--k?[n>3?'-2344-6-6'[(h=k=>k*2<n?~k:k-n)(k%n)*h(k/n|0)]||8:k-4&&2]+g(k):2)(n*n)

Try it online!

How?

Special case: \$n=3\$

We fill each cell with \$2\$, except the center one which is set to \$0\$:

$$\pmatrix{2 & 2 & 2\\ 2 & 0 & 2\\ 2 & 2 & 2}$$

Other cases: \$3<n\le 8\$

For each cell \$(x,y)\$ with \$0\le x<n\$ and \$0\le y<n\$, we compute a lookup index \$i_{x,y}\$ defined as:

$$i_{x,y}=\min(x+1,n-x)\times \min(y+1,n-y)$$

For \$n=8\$, this gives:

$$\pmatrix{1 & 2 & 3 & 4 & 4 & 3 & 2 & 1\\ 2 & 4 & 6 & 8 & 8 & 6 & 4 & 2\\ 3 & 6 & 9 & 12 & 12 & 9 & 6 & 3\\ 4 & 8 & 12 & 16 & 16 & 12 & 8 & 4\\ 4 & 8 & 12 & 16 & 16 & 12 & 8 & 4\\ 3 & 6 & 9 & 12 & 12 & 9 & 6 & 3\\ 2 & 4 & 6 & 8 & 8 & 6 & 4 & 2\\ 1 & 2 & 3 & 4 & 4 & 3 & 2 & 1}$$

The lookup table \$T\$ is defined as:

$$T = [0,2,3,4,4,0,6,0,6]$$

where \$0\$ represents an unused slot.

We set each cell \$(x,y)\$ to:

$$\begin{cases}T(i_{x,y})&\text{if }i_{x,y} \le 8\\8&\text{otherwise}\end{cases}$$


JavaScript (ES7), 107 bytes

A naive implementation which actually tries all moves.

n=>[...10**n-1+''].map((_,y,a)=>a.map((k,x)=>~[...b=i='01344310'].map(v=>k-=!a[x-v+2]|!a[y-b[i++&7]+2])+k))

Try it online!

Jelly,  23 22 14  10 bytes

²ḶdðạP€ċ2)

A monadic link yielding a flat list - uses the idea first used by KSab in their Python answer - knight's moves have "sides" 1 and 2, the only factors of 2.

Try it online! (footer calls the program's only Link and then formats the result as a grid)

Alternatively, also for 10 bytes, ²Ḷdðạ²§ċ5) (knight's moves are all of the possible moves with distance \$\sqrt{5}\$)

How?

²ḶdðạP€ċ2) - Link: integer, n (any non-negative) e.g. 8
²          - square n                                 64
 Ḷ         - lowered range                            [0,    1,    2,    3,    4,    5,    6,    7,    8,    9,    10,   11,   12,   13,   14,   15,   16,   17,   18,   19,   20,   21,   22,   23,   24,   25,   26,   27,   28,   29,   30,   31,   32,   33,   34,   35,   36,   37,   38,   39,   40,   41,   42,   43,   44,   45,   46,   47,   48,   49,   50,   51,   52,   53,   54,   55,   56,   57,   58,   59,   60,   61,   62,   63]
  d        - divmod (vectorises) i.e. x->[x//n,x%n]   [[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[2,0],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[2,7],[3,0],[3,1],[3,2],[3,3],[3,4],[3,5],[3,6],[3,7],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[4,6],[4,7],[5,0],[5,1],[5,2],[5,3],[5,4],[5,5],[5,6],[5,7],[6,0],[6,1],[6,2],[6,3],[6,4],[6,5],[6,6],[6,7],[7,0],[7,1],[7,2],[7,3],[7,4],[7,5],[7,6],[7,7]]
   ð     ) - new dyadic chain for each - call that L ( & e.g. R = [1,2] representing the "2nd row, 3rd column" ...-^ )
    ạ      -   absolute difference (vectorises)       [[1,2],[1,1],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[0,2],[0,1],[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[1,2],[1,1],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[2,2],[2,1],[2,0],[2,1],[2,2],[2,3],[2,4],[2,5],[3,2],[3,1],[3,0],[3,1],[3,2],[3,3],[3,4],[3,5],[4,2],[4,1],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[5,2],[5,1],[5,0],[5,1],[5,2],[5,3],[5,4],[5,5],[6,2],[6,1],[6,0],[6,1],[6,2],[6,3],[6,4],[6,5]]
     P€    -   product of €ach                        [2,    1,    0,    1,    2,    3,    4,    5,    0,    0,    0,    0,    0,    0,    0,    0,    2,    1,    0,    1,    2,    3,    4,    5,    4,    2,    0,    2,    4,    6,    8,    10,   6,    3,    0,    3,    6,    9,    12,   15,   8,    4,    0,    4,    8,    12,   16,   20,   10,   5,    0,    5,    10,   15,   20,   25,   12,   6,    0,    6,    12,   18,   24,   30]
       ċ2  -   count 2s                          6:    ^-...1                  ^-...2                                                                  ^-...3                  ^-...4                        ^-...5      ^-...6
           - )                                                                                                     v-...that goes here
           -   ->                                  -> [2,    3,    4,    4,    4,    4,    3,    2,    3,    4,    6,    6,    6,    6,    4,    3,    4,    6,    8,    8,    8,    8,    6,    4,    4,    6,    8,    8,    8,    8,    6,    4,    4,    6,    8,    8,    8,    8,    6,    4,    4,    6,    8,    8,    8,    8,    6,    4,    3,    4,    6,    6,    6,    6,    4,    3,    2,    3,    4,    4,    4,    4,    3,    2]

Previous 22 byter

2RżN$Œp;U$+,ḟ€³R¤Ẉ¬Sðþ

A full program (due to ³).

Try it online! (footer calls the program's only Link and then formats the result as a grid)

Finds all moves and counts those which land on the board probably definitely beatable by calculating (maybe beatable by changing the "land on the board" logic).

APL (Dyalog Classic), 18 bytes

+/+/2=×/¨|∘.-⍨⍳2⍴⎕

Try it online!

evaluated input N

2⍴⎕ two copies of N

⍳2⍴⎕ the indices of an N×N matrix - a matrix of length-2 vectors

∘.-⍨ subtract each pair of indices from each other pair, get an N×N×N×N array

| absolute value

×/¨ product each

2= where are the 2s? return a boolean (0/1) matrix

Note that a knight moves ±1 on one axis and ±2 on the other, so the absolute value of the product of those steps is 2. As 2 can't be factored in any other way, this is valid only for knight moves.

+/+/ sum along the last dimension, twice

RAD, 51 46 39 bytes

{+/(⍵∘+¨(⊖,⊢)(⊢,-)(⍳2)(1¯2))∊,W}¨¨W←⍳⍵⍵

Try it online!

How?

Counts the number of valid knight moves for each square by seeing which knight moves would land on the board:

{+/(⍵∘+¨(⊖,⊢)(⊢,-)(⍳2)(1¯2))∊,W}¨¨W←⍳⍵⍵
 +/                                     - The number of ...
                            ∊,W         - ... in-bounds ...
        (⊖,⊢)(⊢,-)(⍳2)(1¯2)             - ... knight movements ...
   (⍵∘+¨                   )            - ... from ...
{                              }¨¨W←⍳⍵⍵ - ... each square

Brachylog, 65 40 33 bytes

This breaks down for N bigger then 9. So I'm happy N can be only go to 8 =)

⟦₅⟨∋≡∋⟩ᶠ;?z{{hQ&t⟦₅↰₁;Qz-ᵐ×ȧ2}ᶜ}ᵐ
  • -25 bytes by switching to KSab's formula
  • -7 bytes by flattening the array thanks to sundar

Try it online!


Brachylog, 44 36 bytes

This one also works for number higher then 9

gP&⟦₅⟨∋≡∋⟩ᶠ;z{{hQ&t⟦₅↰₁;Qz-ᵐ×ȧ2}ᶜ}ᵐ
  • -8 bytes by flattening the array thanks to sundar

Try it online!

  • 1
    You can use the ⟨∋≡∋⟩ early on to generate the matrix coordinates too, and save 7 bytes overall (output is a flat list, which is allowed by OP): Try it online! – sundar Aug 12 at 12:04

Retina, 161 bytes

.+
*
L$`_
$=
(?<=(¶)_+¶_+)?(?=(?<=(¶)_*¶_*)__)?(?<=(¶)__+)?(?=(?<=(¶)_*)___)?_(?=(?<=___)_*(¶))?(?=__+(¶))?(?=(?<=__)_*¶_*(¶))?(?=_+¶_+(¶))?
$.($1$2$3$4$5$6$7$8)

Try it online! Link includes test cases. Explanation:

.+
*

Convert to unary.

L$`_
$=

List the value once for each _ in the value, i.e. create a square.

(?<=(¶)_+¶_+)?
(?=(?<=(¶)_*¶_*)__)?
(?<=(¶)__+)?
(?=(?<=(¶)_*)___)?
_
(?=(?<=___)_*(¶))?
(?=__+(¶))?
(?=(?<=__)_*¶_*(¶))?
(?=_+¶_+(¶))?

Starting at the _ in the middle of the regex, try to match enough context to determine whether each of the eight knight's moves is possible. Each pattern captures a single character if the match succeeds. I tried using named groups so that the number of captures directly equals the desired result but that cost 15 bytes.

$.($1$2$3$4$5$6$7$8)

Concatenate all the successful captures and take the length.

Wolfram Language (Mathematica), 34 bytes

Yet another Mathematica built-in.

VertexDegree@KnightTourGraph[#,#]&

Returns a flattened list.

Try it online!

  • I actually made a comment under the challenge with this answer (although not correct syntax since I don't know WL). I removed it after a bit, since I figured someone else might want to post it as a real answer. – Stewie Griffin Aug 12 at 9:26

Python 2, 114 103 92 bytes

lambda n:[sum((d*c>d)+(d*c>c)for d in(y%n,n-y%n-1)for c in(y/n,n-y/n-1))for y in range(n*n)]

Try it online!

C (gcc), 133 125 bytes

This solution should work on any size board.

#define T(x,y)(x<3?x:2)*(y<3?y:2)/2+
a,b;f(i){for(a=i--;a--;)for(b=i+1;b--;)printf("%i ",T(a,b)T(i-a,b)T(a,i-b)T(i-a,i-b)0);}

Try it online!

  • @ceilingcat Of course, thanks! But I don't see what the second suggestion changes – Curtis Bechtel Aug 13 at 20:00

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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