# A knight's graph on an N-by-N board

In chess, a knight can only move to the positions marked with X relative to its current position, marked with ♞: 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. ### 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!

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

# 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 '18 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

{+/(⍵∘+¨(⊖,⊢)(⊢,-)(⍳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, 6540 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!

• 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 - Reinstate Monica Aug 12 '18 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 '18 at 9:26

# Python 2, 114103 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 '18 at 20:00